#include <rooted_tree.h>

Public Member Functions
	RootedTree (NodeType root, std::vector< NodeType > parents)
	Like Create(), but data is not validated (UB on bad input).

NodeType	root () const
	The root node of this rooted tree.

NodeType	num_nodes () const
	The number of nodes in this rooted tree.

absl::Span< const NodeType >	parents () const

std::vector< NodeType >	PathToRoot (NodeType node) const

std::vector< NodeType >	PathFromRoot (NodeType node) const

double	DistanceToRoot (NodeType start, absl::Span< const double > arc_lengths) const

std::pair< double, std::vector< NodeType > >	DistanceAndPathToRoot (NodeType start, absl::Span< const double > arc_lengths) const

std::vector< NodeType >	Path (NodeType start, NodeType end, NodeType lca) const

double	Distance (NodeType start, NodeType end, NodeType lca, absl::Span< const double > arc_lengths) const

std::pair< double, std::vector< NodeType > >	DistanceAndPath (NodeType start, NodeType end, NodeType lca, absl::Span< const double > arc_lengths) const

double	DistanceOfPath (absl::Span< const NodeType > path, absl::Span< const double > arc_lengths) const

std::vector< NodeType >	TopologicalSort () const

template<typename T >
std::vector< T >	AllDistancesToRoot (absl::Span< const T > arc_lengths) const

template<typename T >
std::vector< T >	AllDistancesToRoot (absl::Span< const T > arc_lengths, absl::Span< const NodeType > topological_order) const

std::vector< NodeType >	AllDepths () const

std::vector< NodeType >	AllDepths (absl::Span< const NodeType > topological_order) const

NodeType	LowestCommonAncestorByDepth (NodeType n1, NodeType n2, absl::Span< const NodeType > depths) const

NodeType	LowestCommonAncestorBySearch (NodeType n1, NodeType n2, std::vector< bool > &visited_workspace) const

void	Evert (NodeType new_root)

Static Public Member Functions
static absl::StatusOr< RootedTree >	Create (NodeType root, std::vector< NodeType > parents, std::vector< NodeType > error_cycle=nullptr, std::vector< NodeType > topological_order=nullptr)

Static Public Attributes
static constexpr NodeType	kNullParent = static_cast<NodeType>(-1)

Detailed Description

template<typename NodeType = int32_t>
class operations_research::RootedTree< NodeType >

A tree is an undirected graph with no cycles, n nodes, and n-1 undirected edges. Consequently, a tree is connected. Given a tree on the nodes [0..n), a RootedTree picks any node to be the root, and then converts all edges into (directed) arcs pointing at the root. Each node has one outgoing edge, so we can store the adjacency list of this directed view of the graph as a single vector of integers with length equal to the number of nodes. At the root index, we store RootedTree::kNullParent=-1, and at every other index, we store the next node towards the root (the parent in the tree).

This class is templated on the NodeType, which must be an integer type, e.g., int or int32_t (signed and unsigned types both work).

The following operations are supported:

Path from node to root in O(path length to root)
Lowest Common Ancestor (LCA) of two nodes in O(path length between nodes)
Depth of all nodes in O(num nodes)
Topological sort in O(num nodes)
Path between any two nodes in O(path length between nodes)

Users can provide a vector<double> of arc lengths (indexed by source) to get:

Distance from node to root in O(path length to root)
Distance from all nodes to root in O(num nodes)
Distance between any two nodes in O(path length between nodes)

Operations on rooted trees are generally more efficient than on adjacency list representations because the entire tree is in one contiguous allocation. There is also an asymptotic advantage on path finding problems.

Two methods for finding the LCA are provided. The first requires the depth of every node ahead of time. The second requires a workspace of n bools, all starting at false. These values are modified and restored to false when the LCA computation finishes. In both cases, if the depths/workspace allocation is an O(n) precomputation, then the LCA runs in O(path length). Non-asymptotically, the depth method requires more precomputation, but the LCA is faster and does not require the user to manage mutable state (i.e., may be better for multi-threaded computation).

An operation that is missing is bulk LCA, see https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm.

Definition at line 87 of file rooted_tree.h.

Constructor & Destructor Documentation

◆ RootedTree()

template<typename NodeType = int32_t>

operations_research::RootedTree< NodeType >::RootedTree	(	NodeType	root,
		std::vector< NodeType >	parents )

inlineexplicit

Like Create(), but data is not validated (UB on bad input).

Definition at line 104 of file rooted_tree.h.

Member Function Documentation

◆ AllDepths() [1/2]

template<typename NodeType = int32_t>

std::vector< NodeType > operations_research::RootedTree< NodeType >::AllDepths ( ) const

inline

Returns the distance (arcs to move over) from every node to the root.

If you already have a topological order, prefer AllDepths(absl::Span<const NodeType>).

Definition at line 231 of file rooted_tree.h.

◆ AllDepths() [2/2]

template<typename NodeType >

std::vector< NodeType > operations_research::RootedTree< NodeType >::AllDepths ( absl::Span< const NodeType > topological_order ) const

Returns the distance (arcs to move over) from every node to the root.

topological_order must have size equal to num_nodes() and start with root(), or else we CHECK fail. It can be any topological over nodes when the orientation of the arcs from rooting the tree is reversed.

Definition at line 720 of file rooted_tree.h.

◆ AllDistancesToRoot() [1/2]

template<typename NodeType >

template<typename T >

std::vector< T > operations_research::RootedTree< NodeType >::AllDistancesToRoot ( absl::Span< const T > arc_lengths ) const

Returns the distance of every node from root(), if the edge leaving node i has length costs[i].

arc_lengths[i] is the length of the arc from node i to parents()[i]. arc_lengths must have size equal to num_nodes() or else we CHECK fail. The value of arc_lengths[root()] is unused.

If you already have a topological order, prefer AllDistances(absl::Span<const double> costs, / absl::Span<const int>& topological_order).

Definition at line 730 of file rooted_tree.h.

◆ AllDistancesToRoot() [2/2]

template<typename NodeType >

template<typename T >

std::vector< T > operations_research::RootedTree< NodeType >::AllDistancesToRoot	(	absl::Span< const T >	arc_lengths,
		absl::Span< const NodeType >	topological_order ) const

Returns the distance from every node to root().

arc_lengths[i] is the length of the arc from node i to parents()[i]. arc_lengths must have size equal to num_nodes() or else we CHECK fail. The value of arc_lengths[root()] is unused.

topological_order must have size equal to num_nodes() and start with root(), or else we CHECK fail. It can be any topological over nodes when the orientation of the arcs from rooting the tree is reversed.

Definition at line 737 of file rooted_tree.h.

◆ Create()

template<typename NodeType >

absl::StatusOr< RootedTree< NodeType > > operations_research::RootedTree< NodeType >::Create	(	NodeType	root,
		std::vector< NodeType >	parents,
		std::vector< NodeType > *	error_cycle = nullptr,
		std::vector< NodeType > *	topological_order = nullptr )

static

Like the constructor but checks that the tree is valid. Uses O(num nodes) temporary space with O(log(n)) allocations.

If the input is cyclic, an InvalidArgument error will be returned with "cycle" as a substring. Further, if error_cycle is not null, it will be cleared and then set to contain the cycle. We will not modify error cycle or return an error message containing the string cycle if there is no cycle. The cycle output will always begin with its smallest element.

Definition at line 465 of file rooted_tree.h.

◆ Distance()

template<typename NodeType >

double operations_research::RootedTree< NodeType >::Distance	(	NodeType	start,
		NodeType	end,
		NodeType	lca,
		absl::Span< const double >	arc_lengths ) const

Returns the sum of the arc lengths of the arcs in the path from start to end.

lca is the lowest common ancestor of start and end. This can be computed using LowestCommonAncestorByDepth() or LowestCommonAncestorByDepth(), both defined on this class.

arc_lengths[i] is the length of the arc from node i to parents()[i]. arc_lengths must have size equal to num_nodes() or else we CHECK fail. The value of arc_lengths[root()] is unused.

Runs in time O(number of edges connecting start to end).

Definition at line 570 of file rooted_tree.h.

◆ DistanceAndPath()

template<typename NodeType >

std::pair< double, std::vector< NodeType > > operations_research::RootedTree< NodeType >::DistanceAndPath	(	NodeType	start,
		NodeType	end,
		NodeType	lca,
		absl::Span< const double >	arc_lengths ) const

Returns the path from start to end as a vector of nodes starting with start, and the sum of the arc lengths of the arcs in the path.

lca is the lowest common ancestor of start and end. This can be computed using LowestCommonAncestorByDepth() or LowestCommonAncestorByDepth(), both defined on this class.

arc_lengths[i] is the length of the arc from node i to parents()[i]. arc_lengths must have size equal to num_nodes() or else we CHECK fail. The value of arc_lengths[root()] is unused.

Runs in time O(number of edges connecting start to end).

Definition at line 578 of file rooted_tree.h.

◆ DistanceAndPathToRoot()

template<typename NodeType >

std::pair< double, std::vector< NodeType > > operations_research::RootedTree< NodeType >::DistanceAndPathToRoot	(	NodeType	start,
		absl::Span< const double >	arc_lengths ) const

Returns the path from start to root() as a vector of nodes starting with start, and the sum of the arc lengths of the arcs in the path.

arc_lengths[i] is the length of the arc from node i to parents()[i]. arc_lengths must have size equal to num_nodes() or else we CHECK fail. The value of arc_lengths[root()] is unused.

Definition at line 533 of file rooted_tree.h.

◆ DistanceOfPath()

template<typename NodeType >

double operations_research::RootedTree< NodeType >::DistanceOfPath	(	absl::Span< const NodeType >	path,
		absl::Span< const double >	arc_lengths ) const

Given a path of nodes, returns the sum of the length of the arcs connecting them.

path must be a list of nodes in the tree where path[i+1] == parents()[path[i]].

arc_lengths[i] is the length of the arc from node i to parents()[i]. arc_lengths must have size equal to num_nodes() or else we CHECK fail. The value of arc_lengths[root()] is unused.

Definition at line 587 of file rooted_tree.h.

◆ DistanceToRoot()

template<typename NodeType >

double operations_research::RootedTree< NodeType >::DistanceToRoot	(	NodeType	start,
		absl::Span< const double >	arc_lengths ) const

Returns the sum of the arc lengths of the arcs in the path from start to root().

arc_lengths[i] is the length of the arc from node i to parents()[i]. arc_lengths must have size equal to num_nodes() or else we CHECK fail. The value of arc_lengths[root()] is unused.

Definition at line 526 of file rooted_tree.h.

◆ Evert()

template<typename NodeType >

void operations_research::RootedTree< NodeType >::Evert ( NodeType new_root )

Modifies the tree in place to change the root. Runs in O(path length from root() to new_root).

Definition at line 688 of file rooted_tree.h.

◆ LowestCommonAncestorByDepth()

template<typename NodeType >

NodeType operations_research::RootedTree< NodeType >::LowestCommonAncestorByDepth	(	NodeType	n1,
		NodeType	n2,
		absl::Span< const NodeType >	depths ) const

Returns the lowest common ancestor of n1 and n2.

depths must have size equal to num_nodes(), or else we CHECK fail. Values must be the distance of each node to the root in arcs (see AllDepths()).

Definition at line 606 of file rooted_tree.h.

◆ LowestCommonAncestorBySearch()

template<typename NodeType >

NodeType operations_research::RootedTree< NodeType >::LowestCommonAncestorBySearch	(	NodeType	n1,
		NodeType	n2,
		std::vector< bool > &	visited_workspace ) const

Returns the lowest common ancestor of n1 and n2.

visited_workspace must be a vector with num_nodes() size, or else we CHECK fail. All values of visited_workspace should be false. It will be modified and then restored to its starting state.

Definition at line 636 of file rooted_tree.h.

◆ num_nodes()

template<typename NodeType = int32_t>

NodeType operations_research::RootedTree< NodeType >::num_nodes ( ) const

inline

The number of nodes in this rooted tree.

Definition at line 111 of file rooted_tree.h.

◆ parents()

template<typename NodeType = int32_t>

absl::Span< const NodeType > operations_research::RootedTree< NodeType >::parents ( ) const

inline

A vector that holds the parent of each non root node, and kNullParent at the root.

Definition at line 115 of file rooted_tree.h.

◆ Path()

template<typename NodeType >

std::vector< NodeType > operations_research::RootedTree< NodeType >::Path	(	NodeType	start,
		NodeType	end,
		NodeType	lca ) const

Returns the path from start to end as a vector of nodes starting with start and ending with end.

lca is the lowest common ancestor of start and end. This can be computed using LowestCommonAncestorByDepth() or LowestCommonAncestorByDepth(), both defined on this class.

Runs in time O(path length).

Definition at line 547 of file rooted_tree.h.

◆ PathFromRoot()

template<typename NodeType >

std::vector< NodeType > operations_research::RootedTree< NodeType >::PathFromRoot ( NodeType node ) const

Returns the path from root() to node as a vector of nodes starting with node.

Definition at line 508 of file rooted_tree.h.

◆ PathToRoot()

template<typename NodeType >

std::vector< NodeType > operations_research::RootedTree< NodeType >::PathToRoot ( NodeType node ) const

Returns the path from node to root() as a vector of nodes starting with node.

Definition at line 497 of file rooted_tree.h.

◆ root()

template<typename NodeType = int32_t>

NodeType operations_research::RootedTree< NodeType >::root ( ) const

inline

The root node of this rooted tree.

Definition at line 108 of file rooted_tree.h.

◆ TopologicalSort()

template<typename NodeType >

std::vector< NodeType > operations_research::RootedTree< NodeType >::TopologicalSort ( ) const

Returns a topological ordering of the nodes where the root is first and every other node appears after its parent.

Definition at line 516 of file rooted_tree.h.

Member Data Documentation

◆ kNullParent

template<typename NodeType = int32_t>

NodeType operations_research::RootedTree< NodeType >::kNullParent = static_cast<NodeType>(-1)

staticconstexpr

Definition at line 89 of file rooted_tree.h.

The documentation for this class was generated from the following file:

ortools/graph/rooted_tree.h

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ RootedTree()

Member Function Documentation

◆ AllDepths() [1/2]

◆ AllDepths() [2/2]

◆ AllDistancesToRoot() [1/2]

◆ AllDistancesToRoot() [2/2]

◆ Create()

◆ Distance()

◆ DistanceAndPath()

◆ DistanceAndPathToRoot()

◆ DistanceOfPath()

◆ DistanceToRoot()

◆ Evert()

◆ LowestCommonAncestorByDepth()

◆ LowestCommonAncestorBySearch()

◆ num_nodes()

◆ parents()

◆ Path()

◆ PathFromRoot()

◆ PathToRoot()

◆ root()

◆ TopologicalSort()

Member Data Documentation

◆ kNullParent