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.
GR | The digraph type the algorithm runs on. |
LEN | The type of the length map. The default value is GR::ArcMap<int> . |
#include <lemon/suurballe.h>
Public Types | |
typedef GR | Digraph |
The type of the digraph the algorithm runs on. | |
typedef LEN | LengthMap |
The type of the length map. | |
typedef LengthMap::Value | Length |
The type of the lengths. | |
typedef GR::ArcMap< int > | FlowMap |
The type of the flow map. | |
typedef GR::NodeMap< Length > | PotentialMap |
The type of the potential map. | |
typedef SimplePath< GR > | Path |
The type of the path structures. | |
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. | |
int | run (const Node &s, const Node &t, int k=2) |
Run the algorithm. | |
void | init (const Node &s) |
Initialize 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. | |
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.
graph | The digraph the algorithm runs on. |
length | The length (cost) values of the arcs. |
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.
(*this)
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.
(*this)
int run | ( | const Node & | s, |
const Node & | t, | ||
int | k = 2 |
||
) | [inline] |
This function runs the algorithm.
s | The source node. |
t | The target node. |
k | The number of paths to be found. |
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.s.run(s, t, k)
is just a shortcut of the following code. s.init(s); s.findFlow(t, k); s.findPaths();
void init | ( | const Node & | s | ) | [inline] |
This function initializes the algorithm.
s | The source node. |
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.
t | The target node. |
k | The number of paths to be found. |
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.void findPaths | ( | ) | [inline] |
This function computes the paths from the found minimum cost flow, which is the union of some arc-disjoint paths.
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(e).
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
.
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.
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.
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.
int pathNum | ( | ) | const [inline] |
This function returns the number of the found paths.
const Path& path | ( | int | i | ) | const [inline] |
This function returns a const reference to the specified path.
i | The function returns the i -th path. i must be between 0 and pathNum()-1 . |