#include <bounded_dijkstra.h>

Public Types
typedef GraphType::NodeIndex	node_type

typedef DistanceType	distance_type

Public Member Functions
	BoundedDijkstraWrapper (const GraphType graph, const std::vector< DistanceType > arc_lengths)

	BoundedDijkstraWrapper (const GraphType *graph, ArcLengthFunctor arc_length_functor)
	Variant that takes a custom arc length functor and copies it locally.

const std::vector< int > &	RunBoundedDijkstra (int source_node, DistanceType distance_limit)

bool	OneToOneShortestPath (int from, int to, DistanceType distance_limit)

const std::vector< int > &	RunBoundedDijkstraFromMultipleSources (const std::vector< std::pair< int, DistanceType > > &sources_with_distance_offsets, DistanceType distance_limit)

std::vector< int >	RunBoundedDijkstraFromMultipleSourcesToMultipleDestinations (const std::vector< std::pair< int, DistanceType > > &sources_with_distance_offsets, const std::vector< std::pair< int, DistanceType > > &destinations_with_distance_offsets, int num_destinations_to_reach, DistanceType distance_limit)

const std::vector< int > &	RunBoundedDijkstraWithSettledNodeCallback (const std::vector< std::pair< int, DistanceType > > &sources_with_distance_offsets, std::function< void(node_type settled_node, DistanceType settled_distance, DistanceType *distance_limit)> settled_node_callback, DistanceType distance_limit)

bool	IsReachable (int node) const
	Returns true if `node` was reached by the last Run*() call.

const std::vector< int > &	reached_nodes () const
	Returns all the reached nodes form the previous Run*() call.

const std::vector< DistanceType > &	distances () const
	The distance of the nodes from their source.

const std::vector< int > &	parents () const

const std::vector< int > &	arc_from_source () const

std::vector< int >	ArcPathTo (int node) const

std::vector< int >	ArcPathToNode (int node) const

std::vector< int >	NodePathTo (int node) const

int	SourceOfShortestPathToNode (int node) const

int	GetSourceIndex (int node) const

int	GetDestinationIndex (int node) const

const GraphType &	graph () const
	Trivial accessors to the underlying graph and arc lengths.

const std::vector< DistanceType > &	arc_lengths () const

DistanceType	GetArcLength (int arc) const

Detailed Description

template<class GraphType, class DistanceType, class ArcLengthFunctor = ElementGetter<DistanceType>>
class operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >

A wrapper that holds the memory needed to run many bounded shortest path computations on the given graph. The graph must implement the interface described in graph.h (without the need for reverse arcs).

We use the length and distance formalism here, but the arc lengths can represent any numeric physical quantity. A shortest path will just be a path minimizing this quantity. Arc length MUST be non-negative though. The code should work with both signed and unsigned integer, or floating point DistanceType.

If one do not use source/destination distance offset, this class is integer-overflow safe, and one can safely use distance_limit = std::numeric_limits<int64_t>::max() for instance. Any arcs with a distance >= distance_limit will then be the same as a non-existent arc.

With source/destination offsets, the potential integer overflow situation is trickier: one need to make sure that the range (distance_limit - source_offset) do not overflow in case of negative source_offset. And also that (distance_limit + destination_offset) do not overflow. Note that with negative source_offset, arc with a length greater than the distance_limit can still be considered!

Definition at line 96 of file bounded_dijkstra.h.

Member Typedef Documentation

◆ distance_type

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

DistanceType operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::distance_type

Definition at line 99 of file bounded_dijkstra.h.

◆ node_type

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

GraphType::NodeIndex operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::node_type

Definition at line 98 of file bounded_dijkstra.h.

Constructor & Destructor Documentation

◆ BoundedDijkstraWrapper() [1/2]

template<class GraphType , class DistanceType , class ArcLengthFunctor >

operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::BoundedDijkstraWrapper	(	const GraphType *	graph,
		const std::vector< DistanceType > *	arc_lengths )

IMPORTANT: Both arguments must outlive the class. The arc lengths cannot be negative and the vector must be of the correct size (both preconditions are CHECKed).

SUBTLE: The client can modify the graph and the arc length between calls to RunBoundedDijkstra(). That's fine. Doing so will obviously invalidate the reader API of the last Dijkstra run, which could return junk, or crash.

Implementation.

Definition at line 317 of file bounded_dijkstra.h.

◆ BoundedDijkstraWrapper() [2/2]

template<class GraphType , class DistanceType , class ArcLengthFunctor >

operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::BoundedDijkstraWrapper	(	const GraphType *	graph,
		ArcLengthFunctor	arc_length_functor )

Variant that takes a custom arc length functor and copies it locally.

Definition at line 331 of file bounded_dijkstra.h.

Member Function Documentation

◆ arc_from_source()

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

const std::vector< int > & operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::arc_from_source ( ) const

inline

The arc reaching a given node in the path from their source. arc_from_source()[x] is undefined (i.e. junk) when parents()[x] == x.

Definition at line 210 of file bounded_dijkstra.h.

◆ arc_lengths()

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

const std::vector< DistanceType > & operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::arc_lengths ( ) const

inline

Definition at line 247 of file bounded_dijkstra.h.

◆ ArcPathTo()

template<class GraphType , class DistanceType , class ArcLengthFunctor >

std::vector< int > operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::ArcPathTo ( int node ) const

Returns the list of all the arcs in the shortest path from the node's source to the node.

Definition at line 569 of file bounded_dijkstra.h.

◆ ArcPathToNode()

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

std::vector< int > operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::ArcPathToNode ( int node ) const

inline

Definition at line 217 of file bounded_dijkstra.h.

◆ distances()

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

const std::vector< DistanceType > & operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::distances ( ) const

inline

The distance of the nodes from their source.

The following vectors are all indexed by graph node indices.

IMPORTANT: after each Run*() function, only the positions of the reached nodes are updated, the others will contain junk.

Definition at line 197 of file bounded_dijkstra.h.

◆ GetArcLength()

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

DistanceType operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::GetArcLength ( int arc ) const

inline

Definition at line 251 of file bounded_dijkstra.h.

◆ GetDestinationIndex()

template<class GraphType , class DistanceType , class ArcLengthFunctor >

int operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::GetDestinationIndex ( int node ) const

Definition at line 621 of file bounded_dijkstra.h.

◆ GetSourceIndex()

template<class GraphType , class DistanceType , class ArcLengthFunctor >

int operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::GetSourceIndex ( int node ) const

Original Source/Destination index extraction, after a call to the multi-source and/or multi-destination variants: Retrieves the original index of the source or destination node in the source/destination lists given in the method calls. Eg. if you called RunBoundedDijkstraFromMultipleSourcesToMultipleDestinations(srcs, dsts), then srcs[GetSourceIndex(node)] = (node, ...), for all "node" that appear in "srcs". Ditto for dsts and GetDestinationIndex().

If the node was listed several times as a source (or destinations), it'll pick the listing with the smallest distance offset. If the node is not a source (or destination), this returns junk: you can't rely on the value.

These methods are invalidated by the next RunBoundedDijkstra*() call.

Definition at line 613 of file bounded_dijkstra.h.

◆ graph()

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

const GraphType & operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::graph ( ) const

inline

Trivial accessors to the underlying graph and arc lengths.

Definition at line 246 of file bounded_dijkstra.h.

◆ IsReachable()

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

bool operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::IsReachable ( int node ) const

inline

Returns true if node was reached by the last Run*() call.

Definition at line 186 of file bounded_dijkstra.h.

◆ NodePathTo()

template<class GraphType , class DistanceType , class ArcLengthFunctor >

std::vector< int > operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::NodePathTo ( int node ) const

Returns the list of all the nodes in the shortest path from the node's source to the node. This always start by the node's source, and end by the given node. In the case that source == node, returns {node}.

Definition at line 587 of file bounded_dijkstra.h.

◆ OneToOneShortestPath()

template<class GraphType , class DistanceType , class ArcLengthFunctor >

bool operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::OneToOneShortestPath	(	int	from,
		int	to,
		DistanceType	distance_limit )

Finds the shortest path between two nodes, subject to the distance limit. Returns true iff it exists and its length is < distance_limit.

If this returns true, you can get the path distance with distances()[to] and the path with ArcPathTo(to) or NodePathTo(to).

Stop the search, by setting the distance limit to 0.

Definition at line 442 of file bounded_dijkstra.h.

◆ parents()

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

const std::vector< int > & operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::parents ( ) const

inline

The parent of the nodes in the shortest path from their source. When a node doesn't have any parent (it has to be a source), its parent is itself.

Note: a path will never contain the same node twice, even if some arcs have a length of zero. Note also that some sources may have parents, because of the initial distances.

Definition at line 206 of file bounded_dijkstra.h.

◆ reached_nodes()

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

const std::vector< int > & operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::reached_nodes ( ) const

inline

Returns all the reached nodes form the previous Run*() call.

Definition at line 189 of file bounded_dijkstra.h.

◆ RunBoundedDijkstra()

template<class GraphType , class DistanceType , class ArcLengthFunctor = ElementGetter<DistanceType>>

const std::vector< int > & operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::RunBoundedDijkstra	(	int	source_node,
		DistanceType	distance_limit )

inline

The typical Dijkstra, from a single source with distance zero, to all nodes of the graph within the distance limit (exclusive). The first element of the returned vector will always be the source_node with a distance of zero. See RunBoundedDijkstraFromMultipleSources() for more information.

Definition at line 119 of file bounded_dijkstra.h.

◆ RunBoundedDijkstraFromMultipleSources()

template<class GraphType , class DistanceType , class ArcLengthFunctor >

const std::vector< int > & operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::RunBoundedDijkstraFromMultipleSources	(	const std::vector< std::pair< int, DistanceType > > &	sources_with_distance_offsets,
		DistanceType	distance_limit )

Returns the list of all the nodes which are under the given distance limit (exclusive) from at least one of the given source nodes (which also have an initial distance offset, to be added to the distance). The nodes are sorted by increasing distance. By "distance", we mean the length of the shortest path from any source plus the source's distance offset, where the length of a path is the sum of the length of its arcs

Definition at line 347 of file bounded_dijkstra.h.

◆ RunBoundedDijkstraFromMultipleSourcesToMultipleDestinations()

template<class GraphType , class DistanceType , class ArcLengthFunctor >

std::vector< int > operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::RunBoundedDijkstraFromMultipleSourcesToMultipleDestinations	(	const std::vector< std::pair< int, DistanceType > > &	sources_with_distance_offsets,
		const std::vector< std::pair< int, DistanceType > > &	destinations_with_distance_offsets,
		int	num_destinations_to_reach,
		DistanceType	distance_limit )

Like RunBoundedDijkstraFromMultipleSources(), but this one stops as soon as it has determined the shortest path from any of the sources to the closest "num_destinations_to_reach" destinations, and returns those destinations, sorted by overall distance (also counting the destination offsets).

If num_destinations_to_reach is non-positive, returns the empty vector, if it is greater than the number of distinct destination nodes, it has no effect (it's safe to do so).

If the limit is reached before, the returned vector may have smaller size, in particular it may be empty if none of the destinations was reachable.

Both the sources and the destinations have a "distance offset", which is added to the path length to determine the distance between them.

The rest of the reader API below is available; with the caveat that you should only try to access the nodes that have been reached by the search. That's true for the returned node index (if not -1) and its ancestors.

Note: the distances() will take the source offsets into account, but not the destination offsets.

Initialize the destinations. We'll adapt the distance limit according to the minimal destination distance offset. This is an optional optimization, to reduce the search space.

Skip useless repetitions.

Clean up, sparsely, for the next call.

Return the closest "num_destinations_to_reach" reached destinations, sorted by distance.

Definition at line 358 of file bounded_dijkstra.h.

◆ RunBoundedDijkstraWithSettledNodeCallback()

template<class GraphType , class DistanceType , class ArcLengthFunctor >

const std::vector< int > & operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::RunBoundedDijkstraWithSettledNodeCallback	(	const std::vector< std::pair< int, DistanceType > > &	sources_with_distance_offsets,
		std::function< void(node_type settled_node, DistanceType settled_distance, DistanceType *distance_limit)>	settled_node_callback,
		DistanceType	distance_limit )

Like RunBoundedDijkstraFromMultipleSources(), but will call a user-provided callback "settled_node_callback" when settling each node ('settling' a node happens at most once per node, when popping it from the Dijkstra queue, meaning that the node has been fully 'processed'). This callback may modify the distance limit dynamically, thus affecting the stopping criterion.

Sparse clear is_reached_ from the last call.

Initialize sources.

Sources with an initial distance ≥ limit are not reached.

Skip useless repetitions.

Dijkstra loop.

The queue may contain the same node more than once, skip irrelevant entries.

We usually never enqueue anything >= distance_limit, but if settled_node_callback is not nullptr, the limit might have been changed after the enqueue were done. So we re-test it here to make sure we never call the callback on such node.

If we are over the distance, we can empty the queue and abort.

Visit the neighbors.

Overflow-safe check of top.distance + arc_length >= distance_limit. This works since we know top.distance < distance_limit, as long as we don't have negative top.distance (which might happen with negative source offset). Note that for floating point, it is not exactly the same as (top_distance + arc_length < distance_limit) though.

Definition at line 462 of file bounded_dijkstra.h.

◆ SourceOfShortestPathToNode()

template<class GraphType , class DistanceType , class ArcLengthFunctor >

int operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::SourceOfShortestPathToNode ( int node ) const

Returns the node's source. This is especially useful when running Dijkstras from multiple sources.

Definition at line 604 of file bounded_dijkstra.h.

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

ortools/graph/bounded_dijkstra.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ distance_type

◆ node_type

Constructor & Destructor Documentation

◆ BoundedDijkstraWrapper() [1/2]

◆ BoundedDijkstraWrapper() [2/2]

Member Function Documentation

◆ arc_from_source()

◆ arc_lengths()

◆ ArcPathTo()

◆ ArcPathToNode()

◆ distances()

◆ GetArcLength()

◆ GetDestinationIndex()

◆ GetSourceIndex()

◆ graph()

◆ IsReachable()

◆ NodePathTo()

◆ OneToOneShortestPath()

◆ parents()

◆ reached_nodes()

◆ RunBoundedDijkstra()

◆ RunBoundedDijkstraFromMultipleSources()

◆ RunBoundedDijkstraFromMultipleSourcesToMultipleDestinations()

◆ RunBoundedDijkstraWithSettledNodeCallback()

◆ SourceOfShortestPathToNode()