#include <shortest_paths.h>

Public Member Functions
	PathContainer ()

	PathContainer (const PathContainer &)=delete
	This type is neither copyable nor movable.

PathContainer &	operator= (const PathContainer &)=delete

	~PathContainer ()

PathDistance	GetDistance (NodeIndex from, NodeIndex to) const

NodeIndex	GetPenultimateNodeInPath (NodeIndex from, NodeIndex to) const

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

PathContainerImpl *	GetImplementation () const
	For internal use only. Returns the internal container implementation.

Static Public Member Functions
static void	BuildPathDistanceContainer (PathContainer *path_container)
	Builds a path container which only stores distances between path nodes.

static void	BuildInMemoryCompactPathContainer (PathContainer *path_container)

Detailed Description

Container class storing paths and distances along the paths. It is used in shortest path computation functions to store resulting shortest paths. Usage example iterating on the path between nodes from and to: PathContainer path_container; PathContainer::BuildInMemoryCompactPathContainer(&path_container); ... fill up container ... const NodeIndex from =...; NodeIndex to =...; while (to != from) { LOG(INFO) << to; to = path_container.GetPenultimateNodeInPath(from, to); }

Definition at line 99 of file shortest_paths.h.

Constructor & Destructor Documentation

◆ PathContainer() [1/2]

operations_research::PathContainer::PathContainer ( )

Definition at line 451 of file shortest_paths.cc.

◆ PathContainer() [2/2]

operations_research::PathContainer::PathContainer ( const PathContainer & )

delete

This type is neither copyable nor movable.

◆ ~PathContainer()

operations_research::PathContainer::~PathContainer ( )

Definition at line 453 of file shortest_paths.cc.

Member Function Documentation

◆ BuildInMemoryCompactPathContainer()

void operations_research::PathContainer::BuildInMemoryCompactPathContainer ( PathContainer * path_container )

static

Builds a path container which stores explicit paths and distances between path nodes in a memory-compact representation. In this case GetPenultimateNodeInPath() is O(log(path_tree_size)), path_tree_size being the size of a tree of paths from a source node (in practice it is equal to the number of nodes in the graph if all nodes are strongly connected). GetPath is O(log(path_tree_size) + path_size), where path_size is the size of the resulting path; note this is faster than successive calls to GetPenultimateNodeInPath() which would result in O(log(path_tree_size) * path_size).

Definition at line 483 of file shortest_paths.cc.

◆ BuildPathDistanceContainer()

void operations_research::PathContainer::BuildPathDistanceContainer ( PathContainer * path_container )

static

Builds a path container which only stores distances between path nodes.

Definition at line 477 of file shortest_paths.cc.

◆ GetDistance()

PathDistance operations_research::PathContainer::GetDistance	(	NodeIndex	from,
		NodeIndex	to ) const

Returns the distance between node 'from' and node 'to' following the path out of 'from' and into 'to'. Note that if 'from' == 'to', the distance is not necessarily 0 if the path out of 'to' and back into 'to' has a distance greater than 0. If you do require the distance to be 0 in this case, add to the graph an arc from 'to' to itself with a length of 0. If nodes are not connected, returns kDisconnectedPathDistance.

Definition at line 455 of file shortest_paths.cc.

◆ GetImplementation()

PathContainerImpl * operations_research::PathContainer::GetImplementation ( ) const

For internal use only. Returns the internal container implementation.

Definition at line 473 of file shortest_paths.cc.

◆ GetPath()

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

Returns path nodes from node "from" to node "to" in a ordered vector. The vector starts with 'from' and ends with 'to', if both nodes are connected (otherwise an empty vector is returned).

Definition at line 466 of file shortest_paths.cc.

◆ GetPenultimateNodeInPath()

NodeIndex operations_research::PathContainer::GetPenultimateNodeInPath	(	NodeIndex	from,
		NodeIndex	to ) const

Returns the penultimate node on the path out of node 'from' into node 'to' (the direct predecessor of node 'to' on the path). If 'from' == 'to', the penultimate node is 'to' only if the shortest path from 'to' to itself is composed of the arc ('to, 'to'), which might not be the case if either this arc doesn't exist or if the length of this arc is greater than the distance of an alternate path. If nodes are not connected, returns StarGraph::kNilNode.

Definition at line 460 of file shortest_paths.cc.

◆ operator=()

PathContainer & operations_research::PathContainer::operator= ( const PathContainer & )