FloydWarshall Class Template Reference
[Path and Flow Algorithms]

#include <lemon/floyd_warshall.h>

List of all members.


Detailed Description

template<typename _Graph, typename _LengthMap typename _Traits>
class lemon::FloydWarshall< _Graph, _Traits >

This class provides an efficient implementation of Floyd-Warshall algorithm. The edge lengths are passed to the algorithm using a ReadMap, so it is easy to change it to any kind of length.

The algorithm solves the shortest path problem for each pair of node when the edges can have negative length but the graph should not contain cycles with negative sum of length. If we can assume that all edge is non-negative in the graph then the dijkstra algorithm should be used from each node rather and if the graph is sparse and there are negative circles then the johnson algorithm.

The complexity of this algorithm is O(n^3 + e).

The type of the length is determined by the Value of the length map.

Parameters:
_Graph The graph type the algorithm runs on. The default value is ListGraph. The value of _Graph is not used directly by FloydWarshall, it is only passed to FloydWarshallDefaultTraits.
_LengthMap This read-only EdgeMap determines the lengths of the edges. It is read once for each edge, so the map may involve in relatively time consuming process to compute the edge length if it is necessary. The default map type is Graph::EdgeMap<int>. The value of _LengthMap is not used directly by FloydWarshall, it is only passed to FloydWarshallDefaultTraits.
_Traits Traits class to set various data types used by the algorithm. The default traits class is FloydWarshallDefaultTraits<_Graph,_LengthMap>. See FloydWarshallDefaultTraits for the documentation of a FloydWarshall traits class.
Author:
Balazs Dezso


Public Types

typedef _Traits::Graph Graph
 The type of the underlying graph.
typedef _Traits::LengthMap::Value Value
 The type of the length of the edges.
typedef _Traits::LengthMap LengthMap
 The type of the map that stores the edge lengths.
typedef _Traits::PredMap PredMap
 The type of the map that stores the last edges of the shortest paths. The type of the PredMap is a matrix map for Edges.
typedef _Traits::DistMap DistMap
 The type of the map that stores the dists of the nodes. The type of the DistMap is a matrix map for Values.
typedef _Traits::OperationTraits OperationTraits
 The operation traits.

Public Member Functions

 FloydWarshall (const Graph &_graph, const LengthMap &_length)
 Constructor.
 ~FloydWarshall ()
 Destructor.
FloydWarshalllengthMap (const LengthMap &m)
 Sets the length map.
FloydWarshallpredMap (PredMap &m)
 Sets the map storing the predecessor edges.
FloydWarshalldistMap (DistMap &m)
 Sets the map storing the distances calculated by the algorithm.
Execution control
The simplest way to execute the algorithm is to use one of the member functions called run(...).
If you need more control on the execution, Finally start() will perform the actual path computation.

void init ()
 Initializes the internal data structures.
void start ()
 Executes the algorithm.
bool checkedStart ()
 Executes the algorithm and checks the negative cycles.
void run ()
 Runs FloydWarshall algorithm.
Query Functions
The result of the FloydWarshall algorithm can be obtained using these functions.
Before the use of these functions, either run() or start() must be called.

template<typename Path>
bool getPath (Path &p, Node source, Node target)
 Copies the shortest path to t into p.
Value dist (Node source, Node target) const
 The distance between two nodes.
Edge predEdge (Node root, Node node) const
 Returns the 'previous edge' of the shortest path tree.
Node predNode (Node root, Node node) const
 Returns the 'previous node' of the shortest path tree.
const DistMapdistMap () const
 Returns a reference to the matrix node map of distances.
const PredMappredMap () const
 Returns a reference to the shortest path tree map.
bool connected (Node source, Node target)
 Checks if a node is reachable from the root.

Classes

struct  DefDistMap
 Named parameter for setting DistMap type More...
struct  DefOperationTraits
 Named parameter for setting OperationTraits type More...
struct  DefPredMap
 Named parameter for setting PredMap type Named parameter for setting PredMap type More...
class  UninitializedParameter
 Exception for uninitialized parameters. More...


Constructor & Destructor Documentation

FloydWarshall const Graph _graph,
const LengthMap _length
[inline]
 

Parameters:
_graph the graph the algorithm will run on.
_length the length map used by the algorithm.


Member Function Documentation

FloydWarshall& lengthMap const LengthMap m  )  [inline]
 

Sets the length map.

Returns:
(*this)

FloydWarshall& predMap PredMap m  )  [inline]
 

Sets the map storing the predecessor edges. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.

Returns:
(*this)

FloydWarshall& distMap DistMap m  )  [inline]
 

Sets the map storing the distances calculated by the algorithm. If you don't use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.

Returns:
(*this)

void init  )  [inline]
 

Initializes the internal data structures.

void start  )  [inline]
 

This method runs the FloydWarshall algorithm in order to compute the shortest path to each node pairs. The algorithm computes

  • The shortest path tree for each node.
  • The distance between each node pairs.

bool checkedStart  )  [inline]
 

This method runs the FloydWarshall algorithm in order to compute the shortest path to each node pairs. If there is a negative cycle in the graph it gives back false. The algorithm computes

  • The shortest path tree for each node.
  • The distance between each node pairs.

void run  )  [inline]
 

This method runs the FloydWarshall algorithm from a each node in order to compute the shortest path to each node pairs. The algorithm computes

  • The shortest path tree for each node.
  • The distance between each node pairs.

Note:
d.run(s) is just a shortcut of the following code.
         d.init();
         d.start();

bool getPath Path &  p,
Node  source,
Node  target
[inline]
 

This function copies the shortest path to t into p. If it t is a source itself or unreachable, then it does not alter p.

Returns:
Returns true if a path to t was actually copied to p, false otherwise.
See also:
DirPath

Value dist Node  source,
Node  target
const [inline]
 

Returns the distance between two nodes.

Precondition:
run() must be called before using this function.
Warning:
If node v in unreachable from the root the return value of this funcion is undefined.

Edge predEdge Node  root,
Node  node
const [inline]
 

For the node node it returns the 'previous edge' of the shortest path tree to direction of the node root i.e. it returns the last edge of a shortest path from the node root to node. It is INVALID if node is unreachable from the root or if node=root. The shortest path tree used here is equal to the shortest path tree used in predNode().

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

Node predNode Node  root,
Node  node
const [inline]
 

For a node node it returns the 'previous node' of the shortest path tree to direction of the node root, i.e. it returns the last but one node from a shortest path from the root to node. It is INVALID if node is unreachable from the root or if node=root. The shortest path tree used here is equal to the shortest path tree used in predEdge().

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

const DistMap& distMap  )  const [inline]
 

Returns a reference to the matrix node map of distances.

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

const PredMap& predMap  )  const [inline]
 

Returns a reference to the matrix node map of the edges of the shortest path tree.

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

bool connected Node  source,
Node  target
[inline]
 

Returns true if v is reachable from the root.

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


The documentation for this class was generated from the following file:
Generated on Fri Feb 3 18:41:24 2006 for LEMON by  doxygen 1.4.6