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>
Classes | |
struct | SetFlowMap |
Named parameter for setting FlowMap type. More... | |
struct | SetHeap |
Named parameter for setting Heap and HeapCrossRef types. More... | |
struct | SetPath |
Named parameter for setting Path type. More... | |
struct | SetPotentialMap |
Named parameter for setting PotentialMap type. 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. More... | |
~Suurballe () | |
Destructor. | |
Suurballe & | flowMap (FlowMap &map) |
Set the flow map. More... | |
Suurballe & | potentialMap (PotentialMap &map) |
Set the potential map. More... | |
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. More... | |
void | init (const Node &s) |
Initialize the algorithm. More... | |
void | fullInit (const Node &s) |
Initialize the algorithm and perform Dijkstra. More... | |
int | start (const Node &t, int k=2) |
Execute the algorithm. More... | |
int | findFlow (const Node &t, int k=2) |
Execute the algorithm to find an optimal flow. More... | |
void | findPaths () |
Compute the paths from the flow. More... | |
Query Functions | |
The results of the algorithm can be obtained using these functions. | |
Length | totalLength () const |
Return the total length of the found paths. More... | |
int | flow (const Arc &arc) const |
Return the flow value on the given arc. More... | |
const FlowMap & | flowMap () const |
Return a const reference to an arc map storing the found flow. More... | |
Length | potential (const Node &node) const |
Return the potential of the given node. More... | |
const PotentialMap & | potentialMap () const |
Return a const reference to a node map storing the found potentials (the dual solution). More... | |
int | pathNum () const |
Return the number of the found paths. More... | |
const Path & | path (int i) const |
Return a const reference to the specified path. More... | |
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)
|
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)
|
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.
|
inline |
This function initializes the algorithm with the given source node.
s | The source node. |
|
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.
s | The source node. |
|
inline |
This function executes the algorithm.
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.start(t, k)
is just a shortcut of the following code.
|
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.
|
inline |
This function computes arc-disjoint paths from the found minimum cost flow, which is the union of them.
|
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).
|
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
.
|
inline |
This function returns a const reference to an arc map storing the flow that is the union of the found arc-disjoint paths.
|
inline |
This function returns the potential of the given node. The node potentials provide the dual solution of the underlying minimum cost flow problem.
|
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.
|
inline |
This function returns the number of the found paths.
|
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 . |