 |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
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 119 of file bounded_dijkstra.h.
#include <bounded_dijkstra.h>
Public Types | |
| typedef GraphType::NodeIndex | NodeIndex |
| typedef GraphType::ArcIndex | ArcIndex |
| typedef DistanceType | distance_type |
| template<typename T> | |
| using | ByNode = internal::IndexedVector<NodeIndex, T> |
| A vector of T, indexed by NodeIndex/ArcIndex. | |
| template<typename T> | |
| using | ByArc = internal::IndexedVector<ArcIndex, T> |
Public Member Functions | |
| BoundedDijkstraWrapper (const GraphType *graph, const ByArc< 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< NodeIndex > & | RunBoundedDijkstra (NodeIndex source_node, DistanceType distance_limit) |
| bool | OneToOneShortestPath (NodeIndex from, NodeIndex to, DistanceType distance_limit) |
| const std::vector< NodeIndex > & | RunBoundedDijkstraFromMultipleSources (const std::vector< std::pair< NodeIndex, DistanceType > > &sources_with_distance_offsets, DistanceType distance_limit) |
| std::vector< NodeIndex > | RunBoundedDijkstraFromMultipleSourcesToMultipleDestinations (const std::vector< std::pair< NodeIndex, DistanceType > > &sources_with_distance_offsets, const std::vector< std::pair< NodeIndex, DistanceType > > &destinations_with_distance_offsets, int num_destinations_to_reach, DistanceType distance_limit) |
| const std::vector< NodeIndex > & | RunBoundedDijkstraWithSettledNodeCallback (const std::vector< std::pair< NodeIndex, DistanceType > > &sources_with_distance_offsets, std::function< void(NodeIndex settled_node, DistanceType settled_distance, DistanceType *distance_limit)> settled_node_callback, DistanceType distance_limit) |
| bool | IsReachable (NodeIndex node) const |
| Returns true if node was reached by the last Run*() call. | |
| const ByNode< NodeIndex > & | reached_nodes () const |
| Returns all the reached nodes form the previous Run*() call. | |
| const ByNode< DistanceType > & | distances () const |
| The distance of the nodes from their source. | |
| const ByNode< NodeIndex > & | parents () const |
| const ByNode< ArcIndex > & | arc_from_source () const |
| std::vector< ArcIndex > | ArcPathTo (NodeIndex node) const |
| std::vector< ArcIndex > | ArcPathToNode (NodeIndex node) const |
| std::vector< NodeIndex > | NodePathTo (NodeIndex node) const |
| NodeIndex | SourceOfShortestPathToNode (NodeIndex node) const |
| int | GetSourceIndex (NodeIndex node) const |
| int | GetDestinationIndex (NodeIndex node) const |
| const GraphType & | graph () const |
| Trivial accessors to the underlying graph and arc lengths. | |
| const ByArc< DistanceType > & | arc_lengths () const |
| DistanceType | GetArcLength (ArcIndex arc) const |
| typedef GraphType::ArcIndex operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::ArcIndex |
Definition at line 122 of file bounded_dijkstra.h.
| using operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::ByArc = internal::IndexedVector<ArcIndex, T> |
Definition at line 129 of file bounded_dijkstra.h.
| using operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::ByNode = internal::IndexedVector<NodeIndex, T> |
A vector of T, indexed by NodeIndex/ArcIndex.
Definition at line 127 of file bounded_dijkstra.h.
| typedef DistanceType operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::distance_type |
Definition at line 123 of file bounded_dijkstra.h.
| typedef GraphType::NodeIndex operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::NodeIndex |
Definition at line 121 of file bounded_dijkstra.h.
| operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::BoundedDijkstraWrapper | ( | const GraphType * | graph, |
| const ByArc< 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 351 of file bounded_dijkstra.h.
| 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 365 of file bounded_dijkstra.h.
|
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 242 of file bounded_dijkstra.h.
|
inline |
Definition at line 281 of file bounded_dijkstra.h.
| std::vector< typename GraphType::ArcIndex > operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::ArcPathTo | ( | NodeIndex | node | ) | const |
Returns the list of all the arcs in the shortest path from the node's source to the node.
Definition at line 605 of file bounded_dijkstra.h.
|
inline |
Definition at line 249 of file bounded_dijkstra.h.
|
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 229 of file bounded_dijkstra.h.
|
inline |
Definition at line 285 of file bounded_dijkstra.h.
| int operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::GetDestinationIndex | ( | NodeIndex | node | ) | const |
Definition at line 658 of file bounded_dijkstra.h.
| int operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::GetSourceIndex | ( | NodeIndex | 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 650 of file bounded_dijkstra.h.
|
inline |
Trivial accessors to the underlying graph and arc lengths.
Definition at line 280 of file bounded_dijkstra.h.
|
inline |
Returns true if node was reached by the last Run*() call.
Definition at line 218 of file bounded_dijkstra.h.
| std::vector< typename GraphType::NodeIndex > operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::NodePathTo | ( | NodeIndex | 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 623 of file bounded_dijkstra.h.
| bool operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::OneToOneShortestPath | ( | NodeIndex | from, |
| NodeIndex | 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 476 of file bounded_dijkstra.h.
|
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.
Definition at line 238 of file bounded_dijkstra.h.
|
inline |
Returns all the reached nodes form the previous Run*() call.
Definition at line 221 of file bounded_dijkstra.h.
|
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 149 of file bounded_dijkstra.h.
| const std::vector< typename GraphType::NodeIndex > & operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::RunBoundedDijkstraFromMultipleSources | ( | const std::vector< std::pair< NodeIndex, 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 381 of file bounded_dijkstra.h.
| std::vector< typename GraphType::NodeIndex > operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::RunBoundedDijkstraFromMultipleSourcesToMultipleDestinations | ( | const std::vector< std::pair< NodeIndex, DistanceType > > & | sources_with_distance_offsets, |
| const std::vector< std::pair< NodeIndex, 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.
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 392 of file bounded_dijkstra.h.
| const std::vector< typename GraphType::NodeIndex > & operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::RunBoundedDijkstraWithSettledNodeCallback | ( | const std::vector< std::pair< NodeIndex, DistanceType > > & | sources_with_distance_offsets, |
| std::function< void(NodeIndex 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 497 of file bounded_dijkstra.h.
| GraphType::NodeIndex operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::SourceOfShortestPathToNode | ( | NodeIndex | node | ) | const |
Returns the node's source. This is especially useful when running Dijkstras from multiple sources.
Definition at line 642 of file bounded_dijkstra.h.
1.14.0