 |
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.11
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 |
Public Member Functions | |
| ShortestPathsOnDagWrapper (const GraphType *graph, const std::vector< double > *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 std::vector< double > & | arc_lengths () const |
Advanced API. This concept only enforces the standard graph API needed for all algorithms on DAGs. One could add the requirement of being a DAG wihtin this concept (which is done before running the algorithm). 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.
Definition at line 118 of file dag_shortest_path.h.
| using operations_research::ShortestPathsOnDagWrapper< GraphType >::ArcIndex = typename GraphType::ArcIndex |
Definition at line 121 of file dag_shortest_path.h.
| using operations_research::ShortestPathsOnDagWrapper< GraphType >::NodeIndex = typename GraphType::NodeIndex |
Definition at line 120 of file dag_shortest_path.h.
| operations_research::ShortestPathsOnDagWrapper< GraphType >::ShortestPathsOnDagWrapper | ( | const GraphType * | graph, |
| const std::vector< double > * | 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 368 of file dag_shortest_path.h.
|
inline |
Definition at line 171 of file dag_shortest_path.h.
| std::vector< typename GraphType::ArcIndex > operations_research::ShortestPathsOnDagWrapper< GraphType >::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 454 of file dag_shortest_path.h.
|
inline |
Accessors to the underlying graph and arc lengths.
Definition at line 170 of file dag_shortest_path.h.
| bool operations_research::ShortestPathsOnDagWrapper< GraphType >::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 444 of file dag_shortest_path.h.
|
inline |
Definition at line 159 of file dag_shortest_path.h.
|
inline |
Returns the length of the shortest path from node's source to node.
Definition at line 158 of file dag_shortest_path.h.
| std::vector< typename GraphType::NodeIndex > operations_research::ShortestPathsOnDagWrapper< GraphType >::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 475 of file dag_shortest_path.h.
|
inline |
Definition at line 155 of file dag_shortest_path.h.
| void operations_research::ShortestPathsOnDagWrapper< GraphType >::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 399 of file dag_shortest_path.h.
1.12.0