The complexity of the algorithm is O(n + e).
|
Public Types |
typedef _Traits::Graph | Graph |
| The type of the underlying graph.
|
typedef _Traits::LengthMap::Value | Value |
| The type of the length of the edges.
|
typedef _Traits::LengthMap | LengthMap |
| The type of the map that stores the edge lengths.
|
typedef _Traits::PredMap | PredMap |
| The type of the map that stores the last edges of the shortest paths.
|
typedef _Traits::DistMap | DistMap |
| The type of the map that stores the dists of the nodes.
|
typedef _Traits::OperationTraits | OperationTraits |
| The operation traits.
|
typedef Graph::NodeMap< Value > | WeightMap |
| The Node weight map.
|
Public Member Functions |
| DagShortestPath (const Graph &_graph, const LengthMap &_length) |
| Constructor.
|
| DagShortestPath (const Graph &_graph, const WeightMap &_length) |
| Constructor with node weight map.
|
| ~DagShortestPath () |
| Destructor.
|
DagShortestPath & | lengthMap (const LengthMap &m) |
| Sets the length map.
|
DagShortestPath & | predMap (PredMap &m) |
| Sets the map storing the predecessor edges.
|
DagShortestPath & | distMap (DistMap &m) |
| Sets the map storing the distances calculated by the algorithm.
|
|
The simplest way to execute the algorithm is to use one of the member functions called run (...)
If you need more control on the execution, first you must call init(...), then you can add several source nodes with addSource(). Finally start() will perform the actual path computation. Some functions have an alternative form (checkedInit(...), checkedRun(...)) which also verifies if the graph given in the constructor is a dag.
|
void | init (const Value value=OperationTraits::infinity()) |
| Initializes the internal data structures.
|
void | init (const typename Graph::template NodeMap< int > &node_order, const Value value=OperationTraits::infinity()) |
| Initializes the internal data structures with a given topological sort (NodeMap).
|
void | init (const std::vector< Node > &node_order, const Value value=OperationTraits::infinity()) |
| Initializes the internal data structures with a given topological sort (std::vector).
|
bool | checkedInit (const Value value=OperationTraits::infinity()) |
| Initializes the internal data structures. It also checks if the graph is dag.
|
bool | checkedInit (const typename Graph::template NodeMap< int > &node_order, const Value value=OperationTraits::infinity()) |
| Initializes the internal data structures with a given topological sort (NodeMap). It also checks if the graph is dag.
|
bool | checkedInit (const std::vector< Node > &node_order, const Value value=OperationTraits::infinity()) |
| Initializes the internal data structures with a given topological sort (std::vector). It also checks if the graph is dag.
|
void | addSource (Node source, Value dst=OperationTraits::zero()) |
| Adds a new source node.
|
Node | processNextNode () |
| Executes one step from the dag shortest path algorithm.
|
bool | emptyQueue () |
| Returns false if there are nodes to be processed in the queue.
|
int | queueSize () |
| Returns the number of the nodes to be processed.
|
void | start () |
| Executes the algorithm.
|
void | run (Node s) |
| Runs DagShortestPath algorithm from node s .
|
bool | checkedRun (Node s) |
| Runs DagShortestPath algorithm from node s . It also checks if the graph is a dag.
|
|
The result of the DagShortestPath algorithm can be obtained using these functions.
Before the use of these functions, either run() or start() must be called.
|
template<typename Path> |
bool | getPath (Path &p, Node t) |
| Copies the shortest path to t into p .
|
Value | dist (Node v) const |
| The distance of a node from the root.
|
Edge | predEdge (Node v) const |
| Returns the 'previous edge' of the shortest path tree.
|
Node | predNode (Node v) const |
| Returns the 'previous node' of the shortest path tree.
|
const DistMap & | distMap () const |
| Returns a reference to the NodeMap of distances.
|
const PredMap & | predMap () const |
| Returns a reference to the shortest path tree map.
|
bool | reached (Node v) |
| Checks if a node is reachable from the root.
|
Classes |
struct | DefDistMap |
| Named parameter for setting DistMap type More...
|
struct | DefOperationTraits |
| Named parameter for setting OperationTraits type More...
|
struct | DefPredMap |
| Named parameter for setting PredMap type Named parameter for setting PredMap type More...
|
class | UninitializedParameter |
| Exception for uninitialized parameters. More...
|