Classes | Public Types | Public Member Functions

Suurballe< GR, LEN, TR > Class Template Reference


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:
GRThe digraph type the algorithm runs on.
LENThe 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>

List of all members.

Classes

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

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.
SuurballeflowMap (FlowMap &map)
 Set the flow map.
SuurballepotentialMap (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 FlowMapflowMap () 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 PotentialMappotentialMap () 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 Pathpath (int i) const
 Return a const reference to the specified path.

Constructor & Destructor Documentation

Suurballe ( const Digraph graph,
const LengthMap length 
) [inline]

Constructor.

Parameters:
graphThe digraph the algorithm runs on.
lengthThe length (cost) values of the arcs.

Member Function Documentation

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)
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)
int run ( const Node &  s,
const Node &  t,
int  k = 2 
) [inline]

This function runs the algorithm.

Parameters:
sThe source node.
tThe target node.
kThe 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);
void init ( const Node &  s) [inline]

This function initializes the algorithm with the given source node.

Parameters:
sThe source node.
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:
sThe source node.
int start ( const Node &  t,
int  k = 2 
) [inline]

This function executes the algorithm.

Parameters:
tThe target node.
kThe 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();
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:
tThe target node.
kThe 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.
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.
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).

Precondition:
run() or findFlow() must be called before using this function.
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.
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.
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.
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.
int pathNum ( ) const [inline]

This function returns the number of the found paths.

Precondition:
run() or findFlow() must be called before using this function.
const Path& path ( int  i) const [inline]

This function returns a const reference to the specified path.

Parameters:
iThe 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.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines