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>> aggregationTreeASD(const std::vector<V> &target_cutjoint, const std::vector<std::vector<V>> &cutjoints) const override#

Finds the ASD aggregation subtree induced by a target cutjoint.

Each cutjoint is represented by an unordered list of at least two distinct vertices. This convention is used to support coordinate constraints which are constraints between edges, and may thus involve 3 nodes. Loop cutjoints involve just 2 nodes, but we need to support the more general case when there can be multiple nodes. The second cutjoints list argument reflects this as well, where each element is a list of nodes for a cutjoint constraint. The target cutjoint nodes list is required to be a member of the second list - this redundancy is to avoid typo errors in the list of indices that can lead to erroneous results.

For each constraint, its candidate supernode is the minimal spanning tree of those vertices with the spanning tree’s root, their lowest common ancestor (LCA), excluded. Candidates are merged when these vertex sets partially overlap, including through transitive partial overlap. Containment alone does not cause a merge: a fully contained candidate represents a nested supernode.

The returned tree contains the merged aggregation region and the merged component’s LCA. This LCA is the root of the returned tree and is not part of the aggregation supernode; all other returned vertices define the supernode. A merge may move the returned LCA upward to the common ancestor of the LCAs belonging to the absorbed candidates.

This method is intentionally specific to BasicTreeImpl and is not part of the abstract Tree interface.

Parameters:

  • target_cutjoint – The target cutjoint whose candidate initializes the aggregation. It must occur in cutjoints, compared as an unordered set of vertices.

  • cutjoints – The complete list of cutjoints in the graph.

Throws:

std::invalid_argument – If a cutjoint contains fewer than two distinct vertices, a cutjoint refers to an unknown vertex, or the target does not occur in the complete cutjoint list.

Returns:

The aggregation region together with its LCA root.

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