All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
List of all members | Public Types | Static Public Member Functions
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
GRThe type of the digraph.
LENThe 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 arc lengths.
 
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 HeapCrossRefcreateHeapCrossRef (const Digraph &g)
 Instantiates a HeapCrossRef.
 
static HeapcreateHeap (HeapCrossRef &r)
 Instantiates a Heap.
 
static PredMapcreatePredMap (const Digraph &g)
 Instantiates a PredMap.
 
static ProcessedMapcreateProcessedMap (const Digraph &g)
 Instantiates a ProcessedMap.
 
static DistMapcreateDistMap (const Digraph &g)
 Instantiates a DistMap.
 

Member Typedef Documentation

typedef LEN LengthMap

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

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 conform to the WriteMap concept.

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

The type of the map that indicates which nodes are processed. It must conform to 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 conform to the WriteMap concept.

Member Function Documentation

static HeapCrossRef* createHeapCrossRef ( const Digraph g)
inlinestatic

This function instantiates a HeapCrossRef.

Parameters
gis 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
gis the digraph, to which we would like to define the PredMap.
static ProcessedMap* createProcessedMap ( const Digraph g)
inlinestatic

This function instantiates a ProcessedMap.

Parameters
gis the digraph, to which we would like to define the ProcessedMap.
static DistMap* createDistMap ( const Digraph g)
inlinestatic

This function instantiates a DistMap.

Parameters
gis the digraph, to which we would like to define the DistMap.