Template Class DAG

Template Class DAG#

Defined in File DAG.h

Inheritance Relationships#

Derived Type#

public Karana::Core::BasicDAGImpl< V > (Template Class BasicDAGImpl)

Class Documentation#

template<class V> class DAG#

A generic directed acyclic graph class.

This class provides a generic interface for working with DAG-like structures. It defines common operations like finding parents, children, ancestors.

Template Parameters:: V – The type of the vertices in the graph.

Subclassed by Karana::Core::BasicDAGImpl< V >

Public Functions

inline virtual ~DAG()#: Destructor.

virtual bool operator==(const DAG<V> &other) const noexcept = 0#

Check if the DAGs contain the same nodes and edges in any order.

Parameters:: other – The DAG to check equality against.
Returns:: True if the vertices and edges are the same, otherwise false.

virtual bool operator!=(const DAG<V> &other) const noexcept = 0#

Check if the DAGs do not contain the same nodes and edges.

Parameters:: other – The DAG to check inequality against.
Returns:: True if the vertices or edges differ, otherwise false.

virtual bool operator<(const DAG<V> &other) const noexcept = 0#

Check if this is a strict SubGraph of other.

Parameters:: other – The DAG to check if this a strict SubGraph of.
Returns:: True if this is a strict SubGraph of other, otherwise false.

virtual bool operator<=(const DAG<V> &other) const noexcept = 0#

Check if this is a SubGraph of other.

Parameters:: other – The DAG to check if this a SubGraph of.
Returns:: True if this is a SubGraph of other, otherwise false.

virtual bool operator>(const DAG<V> &other) const noexcept = 0#

Check if this is a strict supergraph of other.

Parameters:: other – The DAG to check if this a strict supergraph of.
Returns:: True if this is a strict supergraph of other, otherwise false.

virtual bool operator>=(const DAG<V> &other) const noexcept = 0#

Check if this is a supergraph of other.

Parameters:: other – The DAG to check if this a supergraph of.
Returns:: True if this is a supergraph of other, otherwise false.

virtual bool hasVertex(const V &vertex) const noexcept = 0#

Checks if the vertex is in the graph.

Parameters:: vertex – The vertex to check.
Returns:: True if the vertex is in the graph, false otherwise.

virtual bool hasEdge(const V &parent, const V &child) const noexcept = 0#

Checks if the edge is in the graph.

Parameters:

parent – The parent vertex of the edge.
child – The child vertex of the edge.

Returns:

True if the edge is in the graph, false otherwise.

virtual std::vector<V> parents(const V &vertex) const = 0#

Returns the parents of the given vertex.

Parameters:: vertex – The vertex whose parent we want to find.
Returns:: A vector containing the parents of the vertex.

virtual bool isRoot(const V &vertex) const = 0#

Checks if the given vertex is a root (has no parents).

Parameters:: vertex – The vertex to check.
Returns:: True if the vertex is a root, false otherwise.

virtual const std::vector<V> &roots() const noexcept = 0#

Get a list of all root vertices.

A root vertex is one with no parents.

Returns:: A vector of all root vertices in the DAG.

virtual std::vector<V> children(const V &vertex) const = 0#

Returns the children of the given vertex.

Parameters:: vertex – The vertex whose children we want to find.
Returns:: A vector containing the children of the vertex.

virtual bool isLeaf(const V &vertex) const = 0#

Checks if the given vertex is a leaf (has no children).

Parameters:: vertex – The vertex to check.
Returns:: True if the vertex is a leaf, false otherwise.

virtual const std::vector<V> &leaves() const noexcept = 0#

Get a list of all leaf vertices.

A leaf vertex is one with no children.

Returns:: A vector of all leaf vertices in the DAG.

virtual int depth(const V &vertex) const = 0#

Gets the max distance to any root….

Parameters:: vertex – The vertex to check the depth of.
Returns:: The depth of the vertex.

virtual int height() const noexcept = 0#

Gets the max distance from any vertex to a leaf.

Returns:: The height of the DAG.

virtual int height(const V &vertex) const = 0#

Gets the max distance to any leaf.

Parameters:: vertex – The vertex to check the height of.
Returns:: The height of the vertex.

virtual const std::vector<V> &sortedVertices() const noexcept = 0#

Get a topologically sorted list of all vertices.

The sorting order is not unique since only partial ordering is possible. The only guarantee is that a child vertex will not appear before a parent vertex in the sorted list.

Returns:: A vector of all vertices in the DAG in sorted order.

virtual bool isAncestor(const V &maybe_ancestor, const V &maybe_descendant) const = 0#

Checks if maybe_ancestor is an ancestor of maybe_descendant.