Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Types | Public Member Functions | List of all members
operations_research::KShortestPathsOnDagWrapper< GraphType > Class Template Reference

#include <dag_shortest_path.h>

Public Types

using NodeIndex = typename GraphType::NodeIndex
 
using ArcIndex = typename GraphType::ArcIndex
 

Public Member Functions

 KShortestPathsOnDagWrapper (const GraphType *graph, const std::vector< double > *arc_lengths, absl::Span< const NodeIndex > topological_order, int path_count)
 
void RunKShortestPathOnDag (absl::Span< const NodeIndex > sources)
 
bool IsReachable (NodeIndex node) const
 
const std::vector< NodeIndex > & reached_nodes () const
 
std::vector< double > LengthsTo (NodeIndex node) const
 
std::vector< std::vector< ArcIndex > > ArcPathsTo (NodeIndex node) const
 
std::vector< std::vector< NodeIndex > > NodePathsTo (NodeIndex node) const
 
const GraphType & graph () const
 Accessors to the underlying graph and arc lengths.
 
const std::vector< double > & arc_lengths () const
 
int path_count () const
 

Detailed Description

template<class GraphType>
class operations_research::KShortestPathsOnDagWrapper< GraphType >

A wrapper that holds the memory needed to run many k-shortest paths computations efficiently on the given DAG. One call of RunKShortestPathOnDag() has time complexity O(E + kVlog(d)) where d is the mean degree of the graph and space complexity O(kV). GraphType can use any of the interfaces defined in util/graph/graph.h. IMPORTANT: Only use if path_count > 1 (k > 1) otherwise use ShortestPathsOnDagWrapper.

Definition at line 196 of file dag_shortest_path.h.

Member Typedef Documentation

◆ ArcIndex

template<class GraphType >
using operations_research::KShortestPathsOnDagWrapper< GraphType >::ArcIndex = typename GraphType::ArcIndex

Definition at line 199 of file dag_shortest_path.h.

◆ NodeIndex

template<class GraphType >
using operations_research::KShortestPathsOnDagWrapper< GraphType >::NodeIndex = typename GraphType::NodeIndex

Definition at line 198 of file dag_shortest_path.h.

Constructor & Destructor Documentation

◆ KShortestPathsOnDagWrapper()

template<class GraphType >
operations_research::KShortestPathsOnDagWrapper< GraphType >::KShortestPathsOnDagWrapper ( const GraphType * graph,
const std::vector< double > * arc_lengths,
absl::Span< const NodeIndex > topological_order,
int path_count )

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 RunKShortestPathOnDag() 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.

KShortestPathsOnDagWrapper implementation.

Todo
(b/332475713): Optimize if reverse graph is already provided in GraphType.

Memory allocation is done here and only once in order to avoid reallocation at each call of RunKShortestPathOnDag() for better performance.

Definition at line 492 of file dag_shortest_path.h.

Member Function Documentation

◆ arc_lengths()

template<class GraphType >
const std::vector< double > & operations_research::KShortestPathsOnDagWrapper< GraphType >::arc_lengths ( ) const
inline

Definition at line 251 of file dag_shortest_path.h.

◆ ArcPathsTo()

template<class GraphType >
std::vector< std::vector< typename GraphType::ArcIndex > > operations_research::KShortestPathsOnDagWrapper< GraphType >::ArcPathsTo ( NodeIndex node) const

Returns the list of all the arcs of the k-shortest paths from node's source to node.

Definition at line 678 of file dag_shortest_path.h.

◆ graph()

template<class GraphType >
const GraphType & operations_research::KShortestPathsOnDagWrapper< GraphType >::graph ( ) const
inline

Accessors to the underlying graph and arc lengths.

Definition at line 250 of file dag_shortest_path.h.

◆ IsReachable()

template<class GraphType >
bool operations_research::KShortestPathsOnDagWrapper< GraphType >::IsReachable ( NodeIndex node) const

Returns true if node is reachable from at least one source, i.e., the length of the shortest path from at least one source is finite.

Definition at line 650 of file dag_shortest_path.h.

◆ LengthsTo()

template<class GraphType >
std::vector< double > operations_research::KShortestPathsOnDagWrapper< GraphType >::LengthsTo ( NodeIndex node) const

Returns the lengths of the k-shortest paths from node's source to node in increasing order. If there are less than k paths, return all path lengths.

Definition at line 659 of file dag_shortest_path.h.

◆ NodePathsTo()

template<class GraphType >
std::vector< std::vector< typename GraphType::NodeIndex > > operations_research::KShortestPathsOnDagWrapper< GraphType >::NodePathsTo ( NodeIndex node) const

Returns the list of all the nodes of the k-shortest paths from node's source to node (including the source). CHECKs if the node is reachable.

Definition at line 710 of file dag_shortest_path.h.

◆ path_count()

template<class GraphType >
int operations_research::KShortestPathsOnDagWrapper< GraphType >::path_count ( ) const
inline

Definition at line 252 of file dag_shortest_path.h.

◆ reached_nodes()

template<class GraphType >
const std::vector< NodeIndex > & operations_research::KShortestPathsOnDagWrapper< GraphType >::reached_nodes ( ) const
inline

Definition at line 234 of file dag_shortest_path.h.

◆ RunKShortestPathOnDag()

template<class GraphType >
void operations_research::KShortestPathsOnDagWrapper< GraphType >::RunKShortestPathOnDag ( 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.

Definition at line 548 of file dag_shortest_path.h.

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