Suurballe

Declared in lemon/suurballe.h, in the group Shortest Path Algorithms; the same class on the Doxygen site.

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

Algorithm for finding arc-disjoint paths between two nodes having minimum total length.

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.

Note

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

Warning

Length values should be non-negative.

Template Parameters:
  • GR – The digraph type the algorithm runs on.

  • LEN – The type of the length map. The default value is GR::ArcMap< int >.

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().

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

Run the algorithm.

This function runs the algorithm.

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 );

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.

inline void init( const Node & s )

Initialize the algorithm.

This function initializes the algorithm with the given source node.

Parameters:

s – The source node.

inline void fullInit( const Node & s )

Initialize the algorithm and perform Dijkstra.

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.

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

Execute the algorithm.

This function executes the algorithm.

Note

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

s.findFlow( t , k );
s.findPaths();

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.

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

Execute the algorithm to find an optimal flow.

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.

Pre:

init() must be called before using this function.

inline void findPaths()

Compute the paths from the flow.

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

Pre:

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

Query Functions

The results of the algorithm can be obtained using these functions.

The algorithm should be executed before using them.

inline Length totalLength() const

Return the total length of the found paths.

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).

Pre:

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

inline int flow( const Arc & arc ) const

Return the flow value on the given arc.

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.

Pre:

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

inline const FlowMap & flowMap() const

Return a const reference to an arc map storing the found flow.

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

Pre:

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

inline Length potential( const Node & node ) const

Return the potential of the given node.

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

Pre:

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

inline const PotentialMap & potentialMap() const

Return a const reference to a node map storing the found potentials (the dual solution).

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.

Pre:

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

inline int pathNum() const

Return the number of the found paths.

This function returns the number of the found paths.

Pre:

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

inline const Path & path( int i ) const

Return a const reference to the specified path.

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.

Pre:

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

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 Functions

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

Constructor.

Parameters:
  • graph – The digraph the algorithm runs on.

  • length – The length (cost) values of the arcs.

inline ~Suurballe()

Destructor.

inline Suurballe & flowMap( FlowMap & map )

Set the flow map.

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)

inline Suurballe & potentialMap( PotentialMap & map )

Set the potential map.

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)

Protected Functions

inline Suurballe()
template< typename T >
struct SetFlowMapTraits : public Traits

Public Types

typedef T FlowMap
template< typename T >
struct SetFlowMap : public Suurballe< GR , LEN , SetFlowMapTraits< T > >

Named parameter for setting FlowMap type.

Public Types

typedef Suurballe< GR , LEN , SetFlowMapTraits< T > > Create
template< typename T >
struct SetPotentialMapTraits : public Traits

Public Types

typedef T PotentialMap
template< typename T >
struct SetPotentialMap : public Suurballe< GR , LEN , SetPotentialMapTraits< T > >

Named parameter for setting PotentialMap type.

Public Types

typedef Suurballe< GR , LEN , SetPotentialMapTraits< T > > Create
template< typename T >
struct SetPathTraits : public Traits

Public Types

typedef T Path
template< typename T >
struct SetPath : public Suurballe< GR , LEN , SetPathTraits< T > >

Named parameter for setting Path type. It must conform to the Path concept and it must have an addBack() function.

Public Types

typedef Suurballe< GR , LEN , SetPathTraits< T > > Create
template< typename H , typename CR >
struct SetHeapTraits : public Traits

Public Types

typedef H Heap
typedef CR HeapCrossRef
template< typename H , typename CR = typename Digraph::template NodeMap< int > >
struct SetHeap : public Suurballe< GR , LEN , SetHeapTraits< H , typename Digraph::template NodeMap< int > > >

Named parameter for setting Heap and HeapCrossRef types.

Named parameter for setting Heap and HeapCrossRef types with automatic allocation. They will be used for internal Dijkstra computations. The heap type must conform to the Heap concept and its priority type must be Length.

Public Types

typedef Suurballe< GR , LEN , SetHeapTraits< H , CR > > Create