Loading...
Searching...
No Matches
Suurballe< GR, LEN, TR > Class Template Reference
Algorithms » Shortest Path Algorithms

## Detailed Description

template<typename GR, typename LEN, typename TR>
class lemon::Suurballe< GR, LEN, TR >

Suurballe implements an algorithm for finding arc-disjoint paths having minimum total length (cost) from a given source node to a given target node in a digraph.

Note that this problem is a special case of the minimum cost flow problem. This implementation is actually an efficient specialized version of the successive shortest path algorithm directly for this problem. Therefore this class provides query functions for flow values and node potentials (the dual solution) just like the minimum cost flow algorithms.

Template Parameters

  GR | The digraph type the algorithm runs on.
  LEN | The type of the length map. The default value is GR::ArcMap<int>.

Warning
  Length values should be non-negative.

Note
  For finding node-disjoint paths, this algorithm can be used along with the SplitNodes adaptor.

`#include <lemon/suurballe.h>`

Inheritance diagram for Suurballe< GR, LEN, TR >:
[legend]

## Classes

struct | SetFlowMap
| Named parameter for setting `FlowMap` type. More...
struct | SetPotentialMap
| Named parameter for setting `PotentialMap` type. More...
struct | SetPath
| Named parameter for setting `Path` type. More...
struct | SetHeap
| Named parameter for setting `Heap` and `HeapCrossRef` types. More...

## Public Types

typedef TR::Digraph | Digraph
| The type of the digraph.
typedef TR::LengthMap | LengthMap
| The type of the length map.
typedef TR::Length | Length
| The type of the lengths.
typedef TR::FlowMap | FlowMap
| The type of the flow map.
typedef TR::PotentialMap | PotentialMap
| The type of the potential map.
typedef TR::Path | Path
| The type of the path structures.
typedef TR::HeapCrossRef | HeapCrossRef
| The cross reference type used for the heap.
typedef TR::Heap | Heap
| The heap type used for internal Dijkstra computations.
typedef TR | Traits
| The traits class of the algorithm.

## Public Member Functions

| Suurballe (const Digraph &graph, const LengthMap &length)
| Constructor.
| ~Suurballe ()
| Destructor.
Suurballe & | flowMap (FlowMap &map)
| Set the flow map.
Suurballe & | potentialMap (PotentialMap &map)
| Set the potential map.
Execution Control
The simplest way to execute the algorithm is to call the run() function. If you need to execute the algorithm many times using the same source node, then you may call fullInit() once and start() for each target node. If you only need the flow that is the union of the found arc-disjoint paths, then you may call findFlow() instead of start().
int | run (const Node &s, const Node &t, int k=2)
| Run the algorithm.
void | init (const Node &s)
| Initialize the algorithm.
void | fullInit (const Node &s)
| Initialize the algorithm and perform Dijkstra.
int | start (const Node &t, int k=2)
| Execute the algorithm.
int | findFlow (const Node &t, int k=2)
| Execute the algorithm to find an optimal flow.
void | findPaths ()
| Compute the paths from the flow.
Query Functions
The results of the algorithm can be obtained using these functions. The algorithm should be executed before using them.
Length | totalLength () const
| Return the total length of the found paths.
int | flow (const Arc &arc) const
| Return the flow value on the given arc.
const FlowMap & | flowMap () const
| Return a const reference to an arc map storing the found flow.
Length | potential (const Node &node) const
| Return the potential of the given node.
const PotentialMap & | potentialMap () const
| Return a const reference to a node map storing the found potentials (the dual solution).
int | pathNum () const
| Return the number of the found paths.
const Path & | path (int i) const
| Return a const reference to the specified path.

## Constructor & Destructor Documentation

## Suurballe()

template<typename GR, typename LEN, typename TR>

Suurballe | ( | const Digraph & | graph,
|  | const LengthMap & | length )

inline

Constructor.

Parameters

  graph | The digraph the algorithm runs on.
  length | The length (cost) values of the arcs.

## Member Function Documentation

## flowMap() [1/2]

template<typename GR, typename LEN, typename TR>

Suurballe & flowMap | ( | FlowMap & | map | ) |

inline

This function sets the flow map. If it is not used before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.

The found flow contains only 0 and 1 values, since it is the union of the found arc-disjoint paths.

Returns
  (*this)

## potentialMap() [1/2]

template<typename GR, typename LEN, typename TR>

Suurballe & potentialMap | ( | PotentialMap & | map | ) |

inline

This function sets the potential map. If it is not used before calling run() or init(), an instance will be allocated automatically. The destructor deallocates this automatically allocated map, of course.

The node potentials provide the dual solution of the underlying minimum cost flow problem.

Returns
  (*this)

## run()

template<typename GR, typename LEN, typename TR>

int run | ( | const Node & | s,
|  | const Node & | t,
|  | int | k = 2 )

inline

This function runs the algorithm.

Parameters

  s | The source node.
  t | The target node.
  k | The number of paths to be found.

Returns
  `k` if there are at least `k` arc-disjoint paths from `s` to `t` in the digraph. Otherwise it returns the number of arc-disjoint paths found.

Note
  Apart from the return value, s.run(s, t, k) is just a shortcut of the following code.
  s.init(s);
  s.start(t, k);

## init()

template<typename GR, typename LEN, typename TR>

void init | ( | const Node & | s | ) |

inline

This function initializes the algorithm with the given source node.

Parameters

  s | The source node.

## fullInit()

template<typename GR, typename LEN, typename TR>

void fullInit | ( | const Node & | s | ) |

inline

This function initializes the algorithm and performs a full Dijkstra search from the given source node. It makes consecutive executions of start(t, k) faster, since they have to perform Dijkstra only k-1 times.

This initialization is usually worth using instead of init() if the algorithm is executed many times using the same source node.

Parameters

  s | The source node.

## start()

template<typename GR, typename LEN, typename TR>

int start | ( | const Node & | t,
|  | int | k = 2 )

inline

This function executes the algorithm.

Parameters

  t | The target node.
  k | The number of paths to be found.

Returns
  `k` if there are at least `k` arc-disjoint paths from `s` to `t` in the digraph. Otherwise it returns the number of arc-disjoint paths found.

Note
  Apart from the return value, s.start(t, k) is just a shortcut of the following code.
  s.findFlow(t, k);
  s.findPaths();

## findFlow()

template<typename GR, typename LEN, typename TR>

int findFlow | ( | const Node & | t,
|  | int | k = 2 )

inline

This function executes the successive shortest path algorithm to find a minimum cost flow, which is the union of `k` (or less) arc-disjoint paths.

Parameters

  t | The target node.
  k | The number of paths to be found.

Returns
  `k` if there are at least `k` arc-disjoint paths from the source node to the given node `t` in the digraph. Otherwise it returns the number of arc-disjoint paths found.

Precondition
  init() must be called before using this function.

## findPaths()

template<typename GR, typename LEN, typename TR>

void findPaths | ( |  | ) |

inline

This function computes arc-disjoint paths from the found minimum cost flow, which is the union of them.

Precondition
  init() and findFlow() must be called before using this function.

## totalLength()

template<typename GR, typename LEN, typename TR>

Length totalLength | ( |  | ) | const

inline

This function returns the total length of the found paths, i.e. the total cost of the found flow. The complexity of the function is O(m).

Precondition
  run() or findFlow() must be called before using this function.

## flow()

template<typename GR, typename LEN, typename TR>

int flow | ( | const Arc & | arc | ) | const

inline

This function returns the flow value on the given arc. It is `1` if the arc is involved in one of the found arc-disjoint paths, otherwise it is `0`.

Precondition
  run() or findFlow() must be called before using this function.

## flowMap() [2/2]

template<typename GR, typename LEN, typename TR>

const FlowMap & flowMap | ( |  | ) | const

inline

This function returns a const reference to an arc map storing the flow that is the union of the found arc-disjoint paths.

Precondition
  run() or findFlow() must be called before using this function.

## potential()

template<typename GR, typename LEN, typename TR>

Length potential | ( | const Node & | node | ) | const

inline

This function returns the potential of the given node. The node potentials provide the dual solution of the underlying minimum cost flow problem.

Precondition
  run() or findFlow() must be called before using this function.

## potentialMap() [2/2]

template<typename GR, typename LEN, typename TR>

const PotentialMap & potentialMap | ( |  | ) | const

inline

This function returns a const reference to a node map storing the found potentials that provide the dual solution of the underlying minimum cost flow problem.

Precondition
  run() or findFlow() must be called before using this function.

## pathNum()

template<typename GR, typename LEN, typename TR>

int pathNum | ( |  | ) | const

inline

This function returns the number of the found paths.

Precondition
  run() or findFlow() must be called before using this function.

## path()

template<typename GR, typename LEN, typename TR>

const Path & path | ( | int | i | ) | const

inline

This function returns a const reference to the specified path.

Parameters

  i | The function returns the i-th path. `i` must be between `0` and pathNum()-1.

Precondition
  run() or findPaths() must be called before using this function.