JohnsonDefaultTraits< _Graph, _LengthMap > Struct Template Reference

---

Detailed Description

template<class _Graph, class _LengthMap>
struct lemon::JohnsonDefaultTraits< _Graph, _LengthMap >

Default traits class of Johnson class.

Parameters:

	_Graph	Graph type.
	_LegthMap	Type of length map.

#include <lemon/johnson.h>

List of all members.

Public Types
typedef _Graph	Graph
	The graph type the algorithm runs on.
typedef _LengthMap	LengthMap
	The type of the map that stores the edge lengths.
typedef JohnsonDefaultOperationTraits < Value >	OperationTraits
	Operation traits for bellman-ford algorithm.
typedef Graph::template NodeMap< int >	HeapCrossRef
	The cross reference type used by heap.
typedef BinHeap< typename LengthMap::Value, HeapCrossRef, std::less< Value > >	Heap
	The heap type used by Dijkstra algorithm.
typedef DynamicMatrixMap < Graph, typename Graph::Node, typename Graph::Edge >	PredMap
	The type of the matrix map that stores the last edges of the shortest paths.
typedef DynamicMatrixMap < Graph, typename Graph::Node, Value >	DistMap
	The type of the matrix map that stores the dists of the nodes.
Static Public Member Functions
static HeapCrossRef *	createHeapCrossRef (const Graph &graph)
	Instantiates a HeapCrossRef.
static Heap *	createHeap (HeapCrossRef &crossRef)
	Instantiates a Heap.
static PredMap *	createPredMap (const Graph &graph)
	Instantiates a PredMap.
static DistMap *	createDistMap (const _Graph &graph)
	Instantiates a DistMap.

---

Member Typedef Documentation

typedef _LengthMap LengthMap

The type of the map that stores the edge lengths. It must meet the ReadMap concept.

typedef JohnsonDefaultOperationTraits<Value> OperationTraits

It defines the infinity type on the given Value type and the used operation.

See also:

JohnsonDefaultOperationTraits

typedef Graph::template NodeMap<int> HeapCrossRef

The cross reference type used by heap. Usually it is Graph::NodeMap<int>.

typedef BinHeap<typename LengthMap::Value, HeapCrossRef, std::less<Value> > Heap

The heap type used by Dijkstra algorithm.

See also:

BinHeap

Dijkstra

typedef DynamicMatrixMap<Graph, typename Graph::Node, typename Graph::Edge> PredMap

The type of the map that stores the last edges of the shortest paths. It must be a matrix map with Graph::Edge value type.

typedef DynamicMatrixMap<Graph, typename Graph::Node, Value> DistMap

The type of the matrix map that stores the dists of the nodes. It must meet the WriteMatrixMap concept.

---

Member Function Documentation

static HeapCrossRef* createHeapCrossRef

(

const Graph &

graph

)

[inline, static]

This function instantiates a HeapCrossRef.

Parameters:

graph

is the graph, to which we would like to define the HeapCrossRef.

static Heap* createHeap

(

HeapCrossRef &

crossRef

)

[inline, static]

This function instantiates a Heap.

Parameters:

crossRef

The cross reference for the heap.

static PredMap* createPredMap

(

const Graph &

graph

)

[inline, static]

This function instantiates a PredMap.

Parameters:

graph

is the graph, to which we would like to define the PredMap.

Todo:

The graph alone may be insufficient for the initialization

static DistMap* createDistMap

(

const _Graph &

graph

)

[inline, static]

This function instantiates a DistMap.

Parameters:

graph

is the graph, to which we would like to define the DistMap