[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

Public Member Functions | List of all members
ShortestPathDijkstra< GRAPH, WEIGHT_TYPE > Class Template Reference

shortest path computer More...

`#include <vigra/graph_algorithms.hxx>`

## Public Member Functions

const DiscoveryOrder & | discoveryOrder () const
| get an array with all visited nodes, sorted by distance from source
WeightType | distance (const Node &target) const
| get the distance to a rarget node (after a call of run)
const DistanceMap & | distances () const
| get the distances node map (after a call of run)
const Graph & | graph () const
| get the graph
bool | hasTarget () const
| check if explicit target is given
const PredecessorsMap & | predecessors () const
| get the predecessors node map (after a call of run)
template<class WEIGHTS>
void | reRun (const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
| run shortest path again with given edge weights
template<class WEIGHTS>
void | run (const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
| run shortest path given edge weights
template<class WEIGHTS>
void | run (Node const &start, Node const &stop, const WEIGHTS &weights, const Node &source, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
| run shortest path in a region of interest of a GridGraph.
template<class EFGE_WEIGHTS, class NODE_WEIGHTS, class ITER>
void | runMultiSource (const EFGE_WEIGHTS &edgeWeights, const NODE_WEIGHTS &nodeWeights, ITER source_begin, ITER source_end, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
| run shortest path with given edge weights from multiple sources.
template<class WEIGHTS, class ITER>
void | runMultiSource (const WEIGHTS &weights, ITER source_begin, ITER source_end, const Node &target=lemon::INVALID, WeightType maxDistance=NumericTraits< WeightType >::max())
| run shortest path with given edge weights from multiple sources.
| ShortestPathDijkstra (const Graph &g)
| \ brief constructor from graph
const Node & | source () const
| get the source node
const Node & | target () const
| get the target node

## Detailed Description

template<class GRAPH, class WEIGHT_TYPE>
class vigra::ShortestPathDijkstra< GRAPH, WEIGHT_TYPE >

shortest path computer

## Member Function Documentation

## ◆ run() [1/2]

template<class GRAPH, class WEIGHT_TYPE>
template<class WEIGHTS>

void run | ( | const WEIGHTS & | weights,
|  | const Node & | source,
|  | const Node & | target = lemon::INVALID,
|  | WeightType | maxDistance = NumericTraits<WeightType>::max() )

run shortest path given edge weights

Parameters

  weights | : edge weights encoding the distance between adjacent nodes (must be non-negative)
  source | : source node where shortest path should start
  target | : target node where shortest path should stop. If target is not given or INVALID, the shortest path from source to all reachable nodes is computed
  maxDistance | : path search is terminated when the path length exceeds maxDistance

When a valid target is unreachable from source (either because the graph is disconnected or maxDistance is exceeded), it is set to lemon::INVALID. In contrast, if target was lemon::INVALID at the beginning, it will always be set to the last node visited in the search.

## ◆ run() [2/2]

template<class GRAPH, class WEIGHT_TYPE>
template<class WEIGHTS>

void run | ( | Node const & | start,
|  | Node const & | stop,
|  | const WEIGHTS & | weights,
|  | const Node & | source,
|  | const Node & | target = lemon::INVALID,
|  | WeightType | maxDistance = NumericTraits<WeightType>::max() )

run shortest path in a region of interest of a GridGraph.

Parameters

  start | : first point in the desired ROI.
  stop | : beyond the last point in the desired ROI (i.e. exclusive)
  weights | : edge weights encoding the distance between adjacent nodes (must be non-negative)
  source | : source node where shortest path should start
  target | : target node where shortest path should stop. If target is not given or INVALID, the shortest path from source to all reachable nodes is computed
  maxDistance | : path search is terminated when the path length exceeds maxDistance

This version of run() restricts the path search to the ROI [start, stop) and only works for instances of GridGraph. Otherwise, it is identical to the standard run() function.

## ◆ reRun()

template<class GRAPH, class WEIGHT_TYPE>
template<class WEIGHTS>

void reRun | ( | const WEIGHTS & | weights,
|  | const Node & | source,
|  | const Node & | target = lemon::INVALID,
|  | WeightType | maxDistance = NumericTraits<WeightType>::max() )

run shortest path again with given edge weights

This only differs from standard run() by initialization: Instead of resetting the entire graph, this only resets the nodes that have been visited in the previous run, i.e. the contents of the array discoveryOrder(). This will be much faster if only a small fraction of the nodes has to be reset.

## ◆ runMultiSource() [1/2]

template<class GRAPH, class WEIGHT_TYPE>
template<class WEIGHTS, class ITER>

void runMultiSource | ( | const WEIGHTS & | weights,
|  | ITER | source_begin,
|  | ITER | source_end,
|  | const Node & | target = lemon::INVALID,
|  | WeightType | maxDistance = NumericTraits<WeightType>::max() )

run shortest path with given edge weights from multiple sources.

This is otherwise identical to standard run(), except that source() returns lemon::INVALID after path search finishes.

## ◆ runMultiSource() [2/2]

template<class GRAPH, class WEIGHT_TYPE>
template<class EFGE_WEIGHTS, class NODE_WEIGHTS, class ITER>

void runMultiSource | ( | const EFGE_WEIGHTS & | edgeWeights,
|  | const NODE_WEIGHTS & | nodeWeights,
|  | ITER | source_begin,
|  | ITER | source_end,
|  | const Node & | target = lemon::INVALID,
|  | WeightType | maxDistance = NumericTraits<WeightType>::max() )

run shortest path with given edge weights from multiple sources.

This is otherwise identical to standard run(), except that source() returns lemon::INVALID after path search finishes.

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

- vigra/graph_algorithms.hxx

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany | html generated using doxygen and Python vigra 1.12.4