Detailed Description

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

Definition at line 87 of file rooted_tree.h.

#include <rooted_tree.h>

Public Member Functions
	RootedTree (NodeType root, std::vector< NodeType > parents)
NodeType	root () const
NodeType	num_nodes () const
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)

Constructor & Destructor Documentation

◆ RootedTree()

template<typename NodeType = int32_t>

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

inlineexplicit

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

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

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

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

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

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

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

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

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

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

Definition at line 526 of file rooted_tree.h.

◆ Evert()

template<typename NodeType>

void operations_research::RootedTree< NodeType >::Evert ( NodeType 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

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

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

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

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

Definition at line 547 of file rooted_tree.h.

◆ PathFromRoot()

template<typename NodeType>

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

Definition at line 508 of file rooted_tree.h.

◆ PathToRoot()

template<typename NodeType>

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

Definition at line 497 of file rooted_tree.h.

◆ root()

template<typename NodeType = int32_t>

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

inline

Definition at line 108 of file rooted_tree.h.

◆ TopologicalSort()

template<typename NodeType>

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

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

Detailed Description

Public Member Functions

Static Public Member Functions

Static Public Attributes

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