Johnson< _Graph, _LengthMap, _Traits > Class Template Reference
[Shortest Path algorithms]

---

Detailed Description

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

This class provides an efficient implementation of Johnson 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.

The complexity of this algorithm is or with fibonacci heap . Usually the fibonacci heap implementation is slower than either binary heap implementation or the Floyd-Warshall algorithm.

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 Johnson, it is only passed to JohnsonDefaultTraits.
	_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 Johnson, it is only passed to JohnsonDefaultTraits.
	_Traits	Traits class to set various data types used by the algorithm. The default traits class is JohnsonDefaultTraits<_Graph,_LengthMap>. See JohnsonDefaultTraits for the documentation of a Johnson traits class.

Author:

Balazs Dezso

#include <lemon/johnson.h>

List of all members.

Query Functions
The result of the Johnson algorithm can be obtained using these functions. Before the use of these functions, either run() or start() must be called.
typedef PredMatrixMapPath < Graph, PredMap >	Path
Path	path (Node s, Node t)
	Gives back the shortest path.
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 DistMap &	distMap () const
	Returns a reference to the matrix node map of distances.
const PredMap &	predMap () 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
struct	DefHeap
struct	DefOperationTraits
struct	DefPredMap
	Named parameter for setting PredMap type Named parameter for setting PredMap type More...
struct	DefStandardHeap
	Named parameter for setting heap and cross reference type with automatic allocation More...
class	UninitializedParameter
	Exception for uninitialized parameters. More...
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.
typedef _Traits::HeapCrossRef	HeapCrossRef
	The cross reference type used for the current heap.
typedef _Traits::Heap	Heap
	The heap type used by the dijkstra algorithm.
Public Member Functions
	Johnson (const Graph &_graph, const LengthMap &_length)
	Constructor.
	~Johnson ()
	Destructor.
Johnson &	lengthMap (const LengthMap &m)
	Sets the length map.
Johnson &	predMap (PredMap &m)
	Sets the map storing the predecessor edges.
Johnson &	distMap (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 ()
template<typename PotentialMap >
void	shiftedStart (const PotentialMap &potential)
	Executes the algorithm with own potential map.
void	start ()
	Executes the algorithm.
bool	checkedStart ()
	Executes the algorithm and checks the negatvie cycles.
void	run ()
	Runs Johnson algorithm.
Private Member Functions
void	create_maps ()
	Creates the maps if necessary.
Private Attributes
const Graph *	graph
	Pointer to the underlying graph.
const LengthMap *	length
	Pointer to the length map.
PredMap *	_pred
	Pointer to the map of predecessors edges.
bool	local_pred
	Indicates if _pred is locally allocated (true) or not.
DistMap *	_dist
	Pointer to the map of distances.
bool	local_dist
	Indicates if _dist is locally allocated (true) or not.
HeapCrossRef *	_heap_cross_ref
	Pointer to the heap cross references.
bool	local_heap_cross_ref
	Indicates if _heap_cross_ref is locally allocated (true) or not.
Heap *	_heap
	Pointer to the heap.
bool	local_heap
	Indicates if _heap is locally allocated (true) or not.

---

Constructor & Destructor Documentation

Johnson	(	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

Johnson& lengthMap

(

const LengthMap &

m

)

[inline]

Sets the length map.

Returns:

(*this)

Johnson& 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)

Johnson& 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 shiftedStart

(

const PotentialMap &

potential

)

[inline]

This method runs the Johnson algorithm in order to compute the shortest path to each node pairs. The potential map can be given for this algorithm which usually calculated by the Bellman-Ford algorithm. If the graph does not have negative length edge then this start function can be used with constMap<Node, int>(0) parameter to omit the running time of the Bellman-Ford. The algorithm computes

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

void start

(

)

[inline]

This method runs the Johnson 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 Johnson algorithm in order to compute the shortest path to each node pairs. If the graph contains negative cycle 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 Johnson 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();

Path path	(	Node	s,
		Node	t
	)			[inline]

Gives back the shortest path.

Precondition:

The t should be reachable from the t.

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.