Template Class Tree

Template Class Tree#

Inheritance Relationships#

Derived Type#

Class Documentation#

template<class V>
class Tree#

A generic tree class.

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

Template Parameters:

V – The type of the vertices in the tree.

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

Public Functions

inline virtual ~Tree()#

Destructor.

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

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.

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

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.

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

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.

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

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.

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

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.

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

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.

virtual bool areDisjoint(const Tree<V> &other) const noexcept = 0#

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 there are no shared vertices

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

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.

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

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.

virtual std::optional<V> parent(const V &vertex) const = 0#

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.

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

Checks if the given vertex is a root.

Parameters:

vertex – The vertex to check.

Returns:

True if the vertex is a root, false otherwise.

virtual const V &root() const noexcept = 0#

Get the root vertex.

Returns:

The root vertex.

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 int depth(const V &vertex) const = 0#

Gets the distance from root of the given vertex.

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

Returns:

The height of the tree.

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

Gets the max distance to any descendant of the vertex.

Parameters:

vertex – The vertex to check the height of.

Returns:

The height of the vertex.

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

Checks if the given vertex is a leaf.

Parameters:

vertex – The vertex to check.

Returns:

True if the vertex is a leaf, false otherwise.

virtual const std::vector<V> descendants(V vertex, const std::vector<V> &stop_at = {}) const = 0#

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 desendants of the specified vertex.

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

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

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

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 for trees. 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 tree in sorted order.

virtual std::vector<std::pair<V, V>> edges() const noexcept = 0#

Return a list of the edges in the tree.

Returns:

A vector of all edges in the tree

virtual size_t offset(V vertex) const = 0#

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

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

Get a list of all base vertices.

A base vertex is an immediate child of the root vertex.

Returns:

A vector of all base vertices in the tree.

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

Get a list of all leaf vertices.

A base vertex is one with no children.

Returns:

A vector of all leaf vertices in the tree.

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

Checks if maybe_ancestor is an ancestor of maybe_descendant.

Note that a vertex can be its own ancestor only when strict is false.

Parameters:

  • maybe_ancestor – The potential ancestor vertex.

  • maybe_descendant – The potential descendant vertex.

  • strict – The potential descendant vertex.

Returns:

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

virtual V lowestCommonAncestor(const V &vertex1, const V &vertex2) const = 0#

Finds the lowest common ancestor of two vertices.

Note that this method returns the node if the node arguments are the same.

Parameters:

  • vertex1 – The first vertex.

  • vertex2 – The second vertex.

Returns:

The lowest common ancestor.

virtual V lowestCommonAncestor(const std::vector<V> &vertices) const = 0#

Finds the lowest common ancestor of a list of vertices.

Parameters:

vertices – The list of vertices.

Returns:

The lowest common ancestor.

virtual bool isOnPath(const V &start, const V &end, const V &test_vertex) const = 0#

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.

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

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.

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

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.

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

Finds the minimal subtree which spans the given vertices.

Parameters:

vertices – The list of vertices the tree must span.

Returns:

The minimal spanning tree.

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

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 underly 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-induces sub-graph of a graph, includes all the edges from the parent sub-graph for all its node pairs. Aggregation sub-graphs are used for multibody system constraint-embedding.

Parameters:

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

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

Returns:

The minimal spanning tree.

virtual std::vector<V> topologicalSort(const std::vector<V> &input) const = 0#

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

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

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 topologoical 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

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

Returns a string with node info in a tree structure.

This method generates hierarchical display of the tree structure beginnig 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 customing 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 contrbution

Returns:

A string with node info in a tree structure.

Contents