 |
Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
|
#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 |
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.
| typedef DistanceType operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::distance_type |
Definition at line 99 of file bounded_dijkstra.h.
| typedef GraphType::NodeIndex operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::node_type |
Definition at line 98 of file bounded_dijkstra.h.
| 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.
| 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.
|
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.
|
inline |
Definition at line 247 of file bounded_dijkstra.h.
| 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.
|
inline |
Definition at line 217 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 197 of file bounded_dijkstra.h.
|
inline |
Definition at line 251 of file bounded_dijkstra.h.
| int operations_research::BoundedDijkstraWrapper< GraphType, DistanceType, ArcLengthFunctor >::GetDestinationIndex | ( | int | node | ) | const |
Definition at line 621 of file bounded_dijkstra.h.
| 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.
|
inline |
Trivial accessors to the underlying graph and arc lengths.
Definition at line 246 of file bounded_dijkstra.h.
|
inline |
Returns true if node was reached by the last Run*() call.
Definition at line 186 of file bounded_dijkstra.h.
| 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.
| 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.
|
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 206 of file bounded_dijkstra.h.
|
inline |
Returns all the reached nodes form the previous Run*() call.
Definition at line 189 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 119 of file bounded_dijkstra.h.
| 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.
| 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.
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.
| 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.
| 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.
1.13.2