DijkstraDefaultTraits< GR, LEN > Struct Template Reference

Detailed Description

template<typename GR, typename LEN>
struct lemon::DijkstraDefaultTraits< GR, LEN >

Default traits class of Dijkstra class.

Template Parameters

GR	The type of the digraph.
LEN	The type of the length map.

#include <lemon/dijkstra.h>

Public Types
typedef GR	Digraph
	The type of the digraph the algorithm runs on.
typedef LEN	LengthMap
	The type of the map that stores the arc lengths.
typedef LEN::Value	Value
	The type of the length of the arcs.
typedef DijkstraDefaultOperationTraits < Value >	OperationTraits
	Operation traits for Dijkstra algorithm.
typedef Digraph::template NodeMap< int >	HeapCrossRef
	The cross reference type used by the heap.
typedef BinHeap< typename LEN::Value, HeapCrossRef, std::less< Value > >	Heap
	The heap type used by the Dijkstra algorithm.
typedef Digraph::template NodeMap< typename Digraph::Arc >	PredMap
	The type of the map that stores the predecessor arcs of the shortest paths.
typedef NullMap< typename Digraph::Node, bool >	ProcessedMap
	The type of the map that indicates which nodes are processed.
typedef Digraph::template NodeMap< typename LEN::Value >	DistMap
	The type of the map that stores the distances of the nodes.

Static Public Member Functions
static HeapCrossRef *	createHeapCrossRef (const Digraph &g)
	Instantiates a HeapCrossRef.
static Heap *	createHeap (HeapCrossRef &r)
	Instantiates a Heap.
static PredMap *	createPredMap (const Digraph &g)
	Instantiates a PredMap.
static ProcessedMap *	createProcessedMap (const Digraph &g)
	Instantiates a ProcessedMap.
static DistMap *	createDistMap (const Digraph &g)
	Instantiates a DistMap.

Member Typedef Documentation

typedef LEN LengthMap

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

typedef DijkstraDefaultOperationTraits<Value> OperationTraits

This class defines the operations that are used in the algorithm.

See Also

DijkstraDefaultOperationTraits

typedef Digraph::template NodeMap<int> HeapCrossRef

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

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

The heap type used by the Dijkstra algorithm.

See Also

BinHeap

Dijkstra

typedef Digraph::template NodeMap<typename Digraph::Arc> PredMap

The type of the map that stores the predecessor arcs of the shortest paths. It must meet the WriteMap concept.

typedef NullMap<typename Digraph::Node,bool> ProcessedMap

The type of the map that indicates which nodes are processed. It must meet the WriteMap concept. By default it is a NullMap.

typedef Digraph::template NodeMap<typename LEN::Value> DistMap

The type of the map that stores the distances of the nodes. It must meet the WriteMap concept.

Member Function Documentation

static HeapCrossRef* createHeapCrossRef ( const Digraph &  g )

inlinestatic

This function instantiates a HeapCrossRef.

Parameters

g	is the digraph, to which we would like to define the HeapCrossRef.

static Heap* createHeap ( HeapCrossRef &  r )

inlinestatic

This function instantiates a Heap.

static PredMap* createPredMap ( const Digraph &  g )

inlinestatic

This function instantiates a PredMap.

Parameters

g	is the digraph, to which we would like to define the PredMap.

static ProcessedMap* createProcessedMap ( const Digraph &  g )

inlinestatic

This function instantiates a ProcessedMap.

Parameters

g	is the digraph, to which we would like to define the ProcessedMap.

static DistMap* createDistMap ( const Digraph &  g )

inlinestatic

This function instantiates a DistMap.

Parameters

g	is the digraph, to which we would like to define the DistMap.