operations_research::ConstrainedShortestPathsOnDagWrapper< GraphType > Class Template Reference

#include <dag_constrained_shortest_path.h>

Public Types
using	NodeIndex = typename GraphType::NodeIndex
using	ArcIndex = typename GraphType::ArcIndex

Public Member Functions
	ConstrainedShortestPathsOnDagWrapper (const GraphType *graph, const std::vector< double > *arc_lengths, const std::vector< std::vector< double > > *arc_resources, absl::Span< const NodeIndex > topological_order, absl::Span< const NodeIndex > sources, absl::Span< const NodeIndex > destinations, const std::vector< double > *max_resources, int max_num_created_labels=1e9)
PathWithLength	RunConstrainedShortestPathOnDag ()
int	label_count () const

Detailed Description

template<class GraphType>
class operations_research::ConstrainedShortestPathsOnDagWrapper< GraphType >

Advanced API. A wrapper that holds the memory needed to run many constrained shortest path computations efficiently on the given DAG (on which resources do not change). GraphType can use one of the interfaces defined in util/graph/graph.h.

Definition at line 93 of file dag_constrained_shortest_path.h.

Member Typedef Documentation

ArcIndex

template<class GraphType >

using operations_research::ConstrainedShortestPathsOnDagWrapper< GraphType >::ArcIndex = typename GraphType::ArcIndex

Definition at line 96 of file dag_constrained_shortest_path.h.

NodeIndex

template<class GraphType >

using operations_research::ConstrainedShortestPathsOnDagWrapper< GraphType >::NodeIndex = typename GraphType::NodeIndex

Definition at line 95 of file dag_constrained_shortest_path.h.

Constructor & Destructor Documentation

ConstrainedShortestPathsOnDagWrapper()

template<class GraphType >

operations_research::ConstrainedShortestPathsOnDagWrapper< GraphType >::ConstrainedShortestPathsOnDagWrapper	(	const GraphType *	graph,
		const std::vector< double > *	arc_lengths,
		const std::vector< std::vector< double > > *	arc_resources,
		absl::Span< const NodeIndex >	topological_order,
		absl::Span< const NodeIndex >	sources,
		absl::Span< const NodeIndex >	destinations,
		const std::vector< double > *	max_resources,
		int	max_num_created_labels = 1e9 )

IMPORTANT: All arguments must outlive the class.

The vectors of arc_lengths and arc_resources[i] (for all resource i) must be of size graph.num_arcs() and indexed the same way as in graph. The vector arc_resources and max_resources must be of same size.

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 DCHECKed.

If the number of labels in memory exceeds max_num_created_labels / 2 at any point in each pass of the algorithm, new labels are not generated anymore and it returns the best path found so far, most particularly the empty path if none were found.

IMPORTANT: You cannot modify anything except arc_lengths between calls to the RunConstrainedShortestPathOnDag() function.

Implementation.

Full graphs.

Forward.

Backward.

Get the minimum resources sources -> node and node -> destination for each node.

Get reachable subgraph.

We split the number of labels evenly between each search (+1 for the additional source node).

Split sub-graphs and related information. The split is based on the number of paths. This is used as a simple proxy for the number of labels.

We use double to avoid overflow. Note that this is an heuristic, so we don't care too much if we are not precise enough.

IMPORTANT: The sub-graph has an additional node linked to sources (resp. destinations) for the forward (resp. backward) direction. This additional node is indexed with the last index. All added arcs are given to have an arc index in the original graph of -1.

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

Definition at line 277 of file dag_constrained_shortest_path.h.

Member Function Documentation

label_count()

template<class GraphType >

int operations_research::ConstrainedShortestPathsOnDagWrapper< GraphType >::label_count ( ) const

inline

For benchmarking and informational purposes, returns the number of labels generated in the call of RunConstrainedShortestPathOnDag().

Definition at line 139 of file dag_constrained_shortest_path.h.

RunConstrainedShortestPathOnDag()

template<class GraphType >

PathWithLength operations_research::ConstrainedShortestPathsOnDagWrapper< GraphType >::RunConstrainedShortestPathOnDag

(

)

Returns {+inf, {}, {}} if there is no constrained path of finite length wihtin resources constraints from one node in sources to one node in destinations.

Assign lengths on sub-relevant graphs.

Check destinations within relevant half sub-graphs.

Clear all labels from the next run.

Definition at line 534 of file dag_constrained_shortest_path.h.

---

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

• ortools/graph/dag_constrained_shortest_path.h