My Project
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. More...
 
typedef LEN::Value Value
 The type of the arc lengths.
 
typedef DijkstraDefaultOperationTraits< ValueOperationTraits
 Operation traits for Dijkstra algorithm. More...
 
typedef Digraph::template NodeMap< int > HeapCrossRef
 The cross reference type used by the heap. More...
 
typedef BinHeap< typename LEN::Value, HeapCrossRef, std::less< Value > > Heap
 The heap type used by the Dijkstra algorithm. More...
 
typedef Digraph::template NodeMap< typename Digraph::Arc > PredMap
 The type of the map that stores the predecessor arcs of the shortest paths. More...
 
typedef NullMap< typename Digraph::Node, bool > ProcessedMap
 The type of the map that indicates which nodes are processed. More...
 
typedef Digraph::template NodeMap< typename LEN::Value > DistMap
 The type of the map that stores the distances of the nodes. More...
 

Static Public Member Functions

static HeapCrossRefcreateHeapCrossRef (const Digraph &g)
 Instantiates a HeapCrossRef. More...
 
static HeapcreateHeap (HeapCrossRef &r)
 Instantiates a Heap. More...
 
static PredMapcreatePredMap (const Digraph &g)
 Instantiates a PredMap. More...
 
static ProcessedMapcreateProcessedMap (const Digraph &g)
 Instantiates a ProcessedMap. More...
 
static DistMapcreateDistMap (const Digraph &g)
 Instantiates a DistMap. More...
 

Member Typedef Documentation

◆ LengthMap

typedef LEN LengthMap

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

◆ OperationTraits

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

See also
DijkstraDefaultOperationTraits

◆ HeapCrossRef

typedef Digraph::template NodeMap<int> HeapCrossRef

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

◆ Heap

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

The heap type used by the Dijkstra algorithm.

See also
BinHeap
Dijkstra

◆ PredMap

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.

◆ ProcessedMap

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.

◆ DistMap

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

◆ createHeapCrossRef()

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.

◆ createHeap()

static Heap* createHeap ( HeapCrossRef r)
inlinestatic

This function instantiates a Heap.

◆ createPredMap()

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.

◆ createProcessedMap()

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.

◆ createDistMap()

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.