Template Class BasicTreeImpl

Template Class BasicTreeImpl#

Nested Relationships#

Nested Types#

Inheritance Relationships#

Base Type#

Class Documentation#

template<class V>
class BasicTreeImpl : public Karana::Core::Tree<V>#

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

This class represents a generic tree structure using vertices and edges. It validates the tree properties during construction and provides methods to query parent-child relationships, check ancestry, and find paths within the tree.

Template Parameters:

V – The type of the vertex identifiers.

Public Functions

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

Constructs a tree from a list of vertices and edges.

This constructor validates that the given vertices and edges form a valid tree. A tree is considered valid if it has exactly one root, no cycles, and exactly vertices.size() - 1 edges.

Parameters:

  • vertices – The list of vertices in the tree.

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

Throws:

std::invalid_argument – If the tree properties are violated (e.g., multiple roots, cycles).

inline BasicTreeImpl(BasicTreeImpl &&other) noexcept#

Move constructor.

Parameters:

other – The BasicTreeImpl to move values from.

BasicTreeImpl(const BasicTreeImpl&) = delete#
inline virtual size_t offset(V vertex) const override#

Returns the offset of the vertex in the sorted list of vertices.

Parameters:

vertex – Input vertex

Returns:

The offset of the vertex in the sorted vertex list

inline virtual const std::vector<V> descendants(V base, const std::vector<V> &stop_at = {}) const final override#

Get a sorted list of descendant vertices.

Note that the returned list does not include the input vertex. An empty list is returned if the stop_at list contains any nodes that are the same as or ancestors of the specified node.

Parameters:

  • vertex – The vertex to get the descendants of.

  • stop_at – List of vertices whose descendants should not be included

Returns:

A sorted list of the descendants of the specified vertex.

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

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

Parameters:

other – The other Tree to check equality with.

Returns:

True if the vertices and edges are the same, otherwise false.

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

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

Parameters:

other – The other Tree to check inequality with.

Returns:

True if the vertices or edges differ, otherwise false.

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

Check if this is a strict subtree of other.

Parameters:

other – The other Tree to check if this tree is a struct subtree of.

Returns:

True if this is a strict subtree of other, otherwise false.

inline virtual bool areDisjoint(const Tree<V> &other) const noexcept override#

Check if this tree shares any vertices with the other.

Parameters:

other – The other tree to check if this tree shares any vertices with.

Returns:

true if this tree is disjoint from the other tree, false otherwise.

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

Check if this is a subtree of other.

Parameters:

other – The other Tree to if this tree is a subtree of.

Returns:

True if this is a subtree of other, otherwise false.

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

Check if this is a strict supertree of other.

Parameters:

other – The other Tree to if this tree is a strict supertree of.

Returns:

True if this is a strict supertree of other, otherwise false.

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

Check if this is a supertree of other.

Parameters:

other – The other Tree to if this tree is a supertree of.

Returns:

True if this is a supertree of other, otherwise false.

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

Checks if the vertex is in the tree.

Parameters:

vertex – The vertex to check.

Returns:

True if the vertex is in the tree, false otherwise.

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

Checks if the edge is in the tree.

Parameters:

  • parent – The parent vertex of the edge.

  • child – The child vertex of the edge.

Returns:

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

inline virtual std::optional<V> parent(const V &vertex) const override#

Returns the parent of the given vertex.

Parameters:

vertex – The vertex whose parent we want to find.

Returns:

An optional containing the parent vertex, or an empty optional if the vertex is a root.

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 V &root() const noexcept override#

Get the root vertex.

Returns:

The root vertex.

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 descendant.

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> &sortedVertices() const noexcept override#

Get a list of all vertices.

Returns:

A vector of all vertices in the tree.

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

Get a list of all vertices that are bases.

Returns:

A vector of all vertices that are bases.

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

Get a list of all leaf vertices.

Returns:

A vector of all vertices that are leaves.

inline virtual bool isAncestorOf(const V &maybe_ancestor, const V &maybe_descendant, bool strict) 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.

  • strict – If true, then a vertex cannot be the ancestor of itself. If false, then a vertex may be its own ancestor.

Returns:

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

inline virtual V lowestCommonAncestor(const V &vertex1, const V &vertex2) const override#

Finds the lowest common ancestor of two vertices.

Parameters:

  • vertex1 – The first vertex.

  • vertex2 – The second vertex.

Returns:

The lowest common ancestor of vertex1 and vertex2.

inline virtual V lowestCommonAncestor(const std::vector<V> &vertices) const override#

Finds the lowest common ancestor of a list of vertices.

Parameters:

vertices – The list of vertices.

Returns:

The lowest common ancestor.

inline virtual std::optional<bool> subpathOrientation(const V &start, const V &end, const V &subpath_start, const V &subpath_end) const override#

Checks how a subpath is oriented along a path.

Parameters:

  • start – The starting vertex of the path.

  • end – The ending vertex of the path.

  • subpath_start – The starting vertex of an the subpath.

  • subpath_end – The ending vertex of the subpath

Returns:

std::nullopt if the subpath is not fully contained in the original path std::optional(true) if the subpath is oriented along the path. std::optional(false) if the subpath is oriented opposed to the path.

inline virtual bool isOnPath(const V &start, const V &end, const V &test_vertex) const override#

Checks if a vertex lies on the path from start to end.

Parameters:

  • start – The starting vertex of the path.

  • end – The ending vertex of the path.

  • test_vertex – The vertex to check.

Returns:

True if test_vertex lies on the path between start and end, false otherwise.

inline virtual std::vector<V> path(const V &start, const V &end) const override#

Finds the path between two vertices.

Parameters:

  • start – The starting vertex of the path.

  • end – The ending vertex of the path.

Returns:

A vector containing the vertices on the path from start to end.

inline virtual std::unique_ptr<Tree<V>> descendantTree(V vertex, const std::vector<V> &stop_at = {}) const override#

Get a sub-tree with new root vertex.

An empty list is returned if the stop_at list contains any nodes that are the same as or ancestors of the specified now.

Parameters:

  • vertex – The root vertex for the new sub-tree.

  • stop_at – List of vertices whose descendants should not be included

Returns:

The new sub-tree

inline virtual std::unique_ptr<Tree<V>> spanningTree(const std::vector<V> &vertices) const override#

Finds the minimal subtree which spans the given vertices.

Parameters:

vertices – The list of vertices the tree must span.

Returns:

The minimal spanning tree.

inline virtual std::unique_ptr<Tree<V>> aggregationTree(const std::vector<V> &vertices, const std::vector<std::pair<V, V>> &cut_edges) const override#

Finds the minimal aggregation subtree for the given vertices and cut-edges.

This is really a graph method, where the cut_edges contains the edges that represent the edges that have been cut to convert the graph into a tree. In other words, the tree + cut_edges is the representation of an underlying sub-graph. For a set of vertices, the aggregation sub-graph, is the smallest sub-tree that contains these vertices, and is “path-induced” for the underlying sub-graph. A path-induced sub-graph includes all the edges from the parent sub-graph for all its node pairs, and all the cut-edge nodes that connect to these nodes. The root node of the aggregated tree is not allowed to be part of any of the cut-edges - and this is satisfied if the root edge is not a part of any of the input cut-edges. Aggregation sub-graphs are used for multibody system constraint-embedding.

Parameters:

  • vertices – The list of vertices the tree must span.

  • cut_edges – The pool of “closed-loop” edges that have been cut.

Returns:

The minimal spanning tree.

inline virtual std::vector<V> topologicalSort(const std::vector<V> &input) const override#

Topologically sort the set of vertices based on this tree structure.

The result is not unique. The result is such that no vertex in the sorted list is an ancestor of any of the earlier ones.

Parameters:

input – The input sub-set of vertices

Returns:

The sorted version of the list

inline virtual std::unique_ptr<Tree<V>> sparseSubTree(const std::vector<V> &input) const override#

Return a sub-tree of the tree with just the specified sub-set of vertices.

The sub-tree will be sparser, but with new edges such that vertex topological relationships are based on that of the original tree. A new root vertex unrelated to the current tree is created.

Parameters:

input – The input sub-set of vertices

Returns:

The new sub-tree

inline virtual const std::string dumpStringTree(const V &start, std::string_view prefix, const std::function<std::string(const V&)> &callback = nullptr) const override#

Returns a string with node info in a tree structure.

This method generates hierarchical display of the tree structure beginning with the specified start vertex. The callback argument is invoked with each vertex argument to generate the vertex’s contribution. The calling function can tailor the verbosity of the output by customizing the callback method. See the Frame::dumpFrameTree() method for an example of the use of this method.

Parameters:

  • start – The starting vertex for the vertices to include

  • prefix – The prefix for each output line

  • callback – The callback for each vertex to generate its string contribution

Returns:

A string with node info in a tree structure.

inline virtual std::vector<std::pair<V, V>> edges() const noexcept override#

Return a list of the edges in the tree.

Returns:

A vector of all edges in the tree

Contents