#include <dag_constrained_shortest_path.h>

Public Attributes
int	from = 0

int	to = 0

double	length = 0.0

std::vector< double >	resources

Detailed Description

This library provides APIs to compute the constrained shortest path (CSP) on a given directed acyclic graph (DAG) with resources on each arc. A CSP is a shortest path on a DAG which does not exceed a set of maximum resources consumption. The algorithm is exponential and has no guarantee to finish. It is based on bi-drectionnal search. First is a forward pass from the source to nodes “somewhere in the middle” to generate forward labels, just as the onedirectional labeling algorithm we discussed; then a symmetric backward pass from the destination generates backward labels; and finally at each node with both forward and backward labels, it joins any pair of labels to form a feasible complete path. Intuitively, the number of labels grows exponentially with the number of arcs in the path. The overall number of labels are then expected to be smaller with shorter paths. For DAG with a topological ordering, we can pick any node (usually right in the middle) as a midpoint to stop each pass at. Then labels can be joined at only one half of the nodes by considering all edges between each half.

In the DAG, multiple arcs between the same pair of nodes is allowed. However, self-loop arcs are not allowed.

Note: we use the length formalism here, but the arc lengths can represent any numeric physical quantity. A shortest path will just be a path minimizing this quantity where the length/resources of a path is the sum of the length/resources of its arcs. An arc length can be negative, or +inf (indicating that it should not be used). An arc length cannot be -inf or nan.

Resources on each arc must be non-negative and cannot be +inf or nan. Basic API. tail and head should both be in [0, num_nodes) If the length is +inf, then the arc is not used.

Definition at line 67 of file dag_constrained_shortest_path.h.