![]() |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
#include <dag_shortest_path.h>
Public Types | |
using | NodeIndex = typename GraphType::NodeIndex |
using | ArcIndex = typename GraphType::ArcIndex |
using | ArcLengths = ArcLengthContainer |
Public Member Functions | |
ShortestPathsOnDagWrapper (const GraphType *graph, const ArcLengths *arc_lengths, absl::Span< const NodeIndex > topological_order) | |
void | RunShortestPathOnDag (absl::Span< const NodeIndex > sources) |
bool | IsReachable (NodeIndex node) const |
const std::vector< NodeIndex > & | reached_nodes () const |
double | LengthTo (NodeIndex node) const |
Returns the length of the shortest path from node's source to node. | |
std::vector< double > | LengthTo () const |
std::vector< ArcIndex > | ArcPathTo (NodeIndex node) const |
std::vector< NodeIndex > | NodePathTo (NodeIndex node) const |
const GraphType & | graph () const |
Accessors to the underlying graph and arc lengths. | |
const ArcLengths & | arc_lengths () const |
Advanced API. A wrapper that holds the memory needed to run many shortest path computations efficiently on the given DAG. One call of RunShortestPathOnDag() has time complexity O(E + V) and space complexity O(V). GraphType can use any of the interfaces defined in util/graph/graph.h. ArcLengthContainer can be any container of doubles.
Definition at line 93 of file dag_shortest_path.h.
using operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >::ArcIndex = typename GraphType::ArcIndex |
Definition at line 96 of file dag_shortest_path.h.
using operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >::ArcLengths = ArcLengthContainer |
Definition at line 97 of file dag_shortest_path.h.
using operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >::NodeIndex = typename GraphType::NodeIndex |
Definition at line 95 of file dag_shortest_path.h.
operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengths >::ShortestPathsOnDagWrapper | ( | const GraphType * | graph, |
const ArcLengths * | arc_lengths, | ||
absl::Span< const NodeIndex > | topological_order ) |
IMPORTANT: All arguments must outlive the class.
The vector of arc_lengths must be of size graph.num_arcs() and indexed the same way as in graph.
You must provide a topological order. You can use util::graph::FastTopologicalSort(graph) to compute one if you don't already have one. An invalid topological order results in an upper bound for all shortest path computations. For maximum performance, you can further reindex the nodes under the topological order so that the memory access pattern is generally forward instead of random. For example, if the topological order for a graph with 4 nodes is [2,1,0,3], you can re-label the nodes 2, 1, and 0 to 0, 1, and 2 (and updates arcs accordingly).
Validity of arcs and topological order are CHECKed if compiled in DEBUG mode.
SUBTLE: You can modify the graph, the arc lengths or the topological order between calls to the RunShortestPathOnDag() function. That's fine. Doing so will obviously invalidate the result API of the last shortest path run, which could return an upper bound, junk, or crash.
ShortestPathsOnDagWrapper implementation.
Memory allocation is done here and only once in order to avoid reallocation at each call of RunShortestPathOnDag() for better performance.
Definition at line 335 of file dag_shortest_path.h.
|
inline |
Definition at line 149 of file dag_shortest_path.h.
std::vector< typename GraphType::ArcIndex > operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengths >::ArcPathTo | ( | NodeIndex | node | ) | const |
Returns the list of all the arcs in the shortest path from node's source to node. CHECKs if the node is reachable.
Definition at line 416 of file dag_shortest_path.h.
|
inline |
Accessors to the underlying graph and arc lengths.
Definition at line 148 of file dag_shortest_path.h.
bool operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengths >::IsReachable | ( | NodeIndex | node | ) | const |
Returns true if node is reachable from at least one source, i.e., the length from at least one source is finite.
Definition at line 408 of file dag_shortest_path.h.
|
inline |
Definition at line 137 of file dag_shortest_path.h.
|
inline |
Returns the length of the shortest path from node's source to node.
Definition at line 134 of file dag_shortest_path.h.
std::vector< typename GraphType::NodeIndex > operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengths >::NodePathTo | ( | NodeIndex | node | ) | const |
Returns the list of all the nodes in the shortest path from node's source to node (including the source). CHECKs if the node is reachable.
Definition at line 436 of file dag_shortest_path.h.
|
inline |
Definition at line 131 of file dag_shortest_path.h.
void operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengths >::RunShortestPathOnDag | ( | absl::Span< const NodeIndex > | sources | ) |
Computes the shortest path to all reachable nodes from the given sources. This must be called before any of the query functions below.
Caching the vector addresses allow to not fetch it on each access.
Avoid reassigning incoming_shortest_path_arc_ at every call for better performance, so it only makes sense for nodes that are reachable from at least one source, the other ones will contain junk.
Stop exploring a node as soon as its length to all sources is +inf.
Definition at line 364 of file dag_shortest_path.h.