operations_research::PathTree< NodeIndex, kNilNode > Class Template Reference

#include <shortest_paths.h>

Public Member Functions
	PathTree ()
void	Initialize (absl::Span< const NodeIndex > paths, absl::Span< const NodeIndex > destinations)
NodeIndex	GetParent (NodeIndex node) const
void	GetPath (NodeIndex from, NodeIndex to, std::vector< NodeIndex > *path) const

Detailed Description

template<class NodeIndex, NodeIndex kNilNode>
class operations_research::PathTree< NodeIndex, kNilNode >

Class designed to store the tree of paths from a root node to a set of nodes in a very compact way (over performance). Memory consumption is in O(n) (n being the size of the tree) where node indices are "very" non-contiguous (extremely sparse node indices). It keeps node-sorted arrays of node and parent pairs, which can be accessed in O(log(n)) with a binary search. The creation of the tree is done in O(n*log(n)) time.

Note

this class uses temporary memory for each call to Initialize which is only an issue for massive parallel calls; in practice for shortest paths computation, the number of threads calling Initialize is very small compared to the total number of trees created.

Definition at line 357 of file shortest_paths.h.

Constructor & Destructor Documentation

PathTree()

template<class NodeIndex, NodeIndex kNilNode>

operations_research::PathTree< NodeIndex, kNilNode >::PathTree ( )

inline

Definition at line 359 of file shortest_paths.h.

Member Function Documentation

GetParent()

template<class NodeIndex, NodeIndex kNilNode>

NodeIndex operations_research::PathTree< NodeIndex, kNilNode >::GetParent

(

NodeIndex

node

)

const

Returns the parent (predecessor) of node in the tree in O(log(path_tree_size)), where path_tree_size is the size of nodes_.

Definition at line 421 of file shortest_paths.h.

GetPath()

template<class NodeIndex, NodeIndex kNilNode>

void operations_research::PathTree< NodeIndex, kNilNode >::GetPath	(	NodeIndex	from,
		NodeIndex	to,
		std::vector< NodeIndex > *	path ) const

Returns the path from node from to node to in the tree in O(log(path_tree_size) + path_size), where path_tree_size is the size of nodes_ and path_size is the size of the resulting path.

from and to are not connected.

Definition at line 433 of file shortest_paths.h.

Initialize()

template<class NodeIndex, NodeIndex kNilNode>

void operations_research::PathTree< NodeIndex, kNilNode >::Initialize	(	absl::Span< const NodeIndex >	paths,
		absl::Span< const NodeIndex >	destinations )

Initializes the tree from a non-sparse representation of the path tree represented by paths. The tree is reduced to the subtree in which nodes in destinations are the leafs.

Definition at line 383 of file shortest_paths.h.

---

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

• ortools/graph/shortest_paths.h