Template Class BasicDAGImpl

• Defined in File BasicDAGImpl.h

Nested Relationships

Nested Types

• Struct BasicDAGImpl::Node

Inheritance Relationships

Base Type

• public Karana::Core::DAG< V > (Template Class DAG)

Class Documentation

template<class V>
class BasicDAGImpl : public Karana::Core::DAG<V>

A DAG implementation that validates structure and provides various DAG-related operations.

This class represents a generic DAG structure using vertices and edges. It validates the DAG properties during construction and provides DAG-related queries and algorithms.

Template Parameters:

V – The type of the vertex identifiers.

Public Functions

inline BasicDAGImpl(const std::vector<V> &vertices, const std::vector<std::pair<V, V>> &edges)

Constructs a DAG from a list of vertices and edges.

This constructor validates that the given vertices and edges form a valid DAG. A DAG is considered valid if it has no cycles.

Parameters:

• vertices – The list of vertices in the DAG.

• edges – The list of edges, where each edge is a pair of child and parent vertices.

Throws:

std::invalid_argument – If the DAG properties are violated (e.g. cycles).

inline virtual bool operator==(const DAG<V> &other) const noexcept override

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.

inline virtual bool operator!=(const DAG<V> &other) const noexcept override

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.

inline virtual bool operator<(const DAG<V> &other) const noexcept override

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.

inline virtual bool operator<=(const DAG<V> &other) const noexcept override

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.

inline virtual bool operator>(const DAG<V> &other) const noexcept override

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.

inline virtual bool operator>=(const DAG<V> &other) const noexcept override

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.

inline virtual bool hasVertex(const V &vertex) const noexcept override

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.

inline virtual bool hasEdge(const V &parent, const V &child) const noexcept override

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.

inline virtual std::vector<V> parents(const V &vertex) const override

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.

inline virtual bool isRoot(const V &vertex) const override

Checks if the given vertex is a root.

Parameters:

vertex – The vertex to check.

Returns:

True if the vertex is a root, false otherwise.

inline virtual const std::vector<V> &roots() const noexcept override

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.

inline virtual std::vector<V> children(const V &vertex) const override

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.

inline virtual int depth(const V &vertex) const override

Gets the distance from root of the given vertex.

Parameters:

vertex – The vertex to check the depth of.

Returns:

The depth of the given vertex.

inline virtual int height() const noexcept override

Gets the max distance from any vertex to a descendent.

Returns:

The height of the tree.

inline virtual int height(const V &vertex) const override

Gets the max distance to any descendant of the vertex.

Parameters:

vertex – The vertex to check the height of.

Returns:

The height of the given vertex.

inline virtual bool isLeaf(const V &vertex) const override

Checks if the given vertex is a leaf.

Parameters:

vertex – The vertex to check.

Returns:

True if the vertex is a leaf, false otherwise.

inline virtual const std::vector<V> &leaves() const noexcept override

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.

inline virtual const std::vector<V> &sortedVertices() const noexcept override

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 graph in sorted order.

inline virtual bool isAncestor(const V &maybe_ancestor, const V &maybe_descendant) const override

Checks if maybe_ancestor is an ancestor of maybe_descendant.

Parameters:

• maybe_ancestor – The potential ancestor vertex.

• maybe_descendant – The potential descendant vertex.

Returns:

True if maybe_ancestor is an ancestor of maybe_descendant, false otherwise.