Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer > Class Template Reference

Detailed Description

template<class GraphType, typename ArcLengthContainer = std::vector<double>>
class operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >

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.

#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

Member Typedef Documentation

◆ ArcIndex

template<class GraphType, typename ArcLengthContainer = std::vector<double>>
using operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >::ArcIndex = typename GraphType::ArcIndex

Definition at line 96 of file dag_shortest_path.h.

◆ ArcLengths

template<class GraphType, typename ArcLengthContainer = std::vector<double>>
using operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >::ArcLengths = ArcLengthContainer

Definition at line 97 of file dag_shortest_path.h.

◆ NodeIndex

template<class GraphType, typename ArcLengthContainer = std::vector<double>>
using operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >::NodeIndex = typename GraphType::NodeIndex

Definition at line 95 of file dag_shortest_path.h.

Constructor & Destructor Documentation

◆ ShortestPathsOnDagWrapper()

template<class GraphType, typename ArcLengths>
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.

Member Function Documentation

◆ arc_lengths()

template<class GraphType, typename ArcLengthContainer = std::vector<double>>
const ArcLengths & operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >::arc_lengths ( ) const
inline

Definition at line 149 of file dag_shortest_path.h.

◆ ArcPathTo()

template<class GraphType, typename ArcLengths>
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.

◆ graph()

template<class GraphType, typename ArcLengthContainer = std::vector<double>>
const GraphType & operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >::graph ( ) const
inline

Accessors to the underlying graph and arc lengths.

Definition at line 148 of file dag_shortest_path.h.

◆ IsReachable()

template<class GraphType, typename ArcLengths>
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.

◆ LengthTo() [1/2]

template<class GraphType, typename ArcLengthContainer = std::vector<double>>
std::vector< double > operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >::LengthTo ( ) const
inline

Definition at line 137 of file dag_shortest_path.h.

◆ LengthTo() [2/2]

template<class GraphType, typename ArcLengthContainer = std::vector<double>>
double operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >::LengthTo ( NodeIndex node) const
inline

Returns the length of the shortest path from node's source to node.

Definition at line 134 of file dag_shortest_path.h.

◆ NodePathTo()

template<class GraphType, typename ArcLengths>
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.

◆ reached_nodes()

template<class GraphType, typename ArcLengthContainer = std::vector<double>>
const std::vector< NodeIndex > & operations_research::ShortestPathsOnDagWrapper< GraphType, ArcLengthContainer >::reached_nodes ( ) const
inline

Definition at line 131 of file dag_shortest_path.h.

◆ RunShortestPathOnDag()

template<class GraphType, typename ArcLengths>
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.

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