Public Types | Static Public Member Functions

DijkstraWizardDefaultTraits< GR, LEN > Struct Template Reference


Detailed Description

template<class GR, class LEN>
struct lemon::DijkstraWizardDefaultTraits< GR, LEN >

Default traits class of dijkstra() function.

Template Parameters:
GRThe type of the digraph.
LENThe type of the length map.

#include <lemon/dijkstra.h>

Inheritance diagram for DijkstraWizardDefaultTraits< GR, LEN >:

List of all members.

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< Value,
typename Digraph::template
NodeMap< int >, 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.
typedef lemon::Path< DigraphPath
 The type of the shortest paths.

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 meet 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<Value, typename Digraph::template NodeMap<int>, 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.

The type of the shortest paths. It must meet the Path concept.


Member Function Documentation

static HeapCrossRef* createHeapCrossRef ( const Digraph g) [inline, static]

This function instantiates a HeapCrossRef.

Parameters:
gis the digraph, to which we would like to define the HeapCrossRef.
static Heap* createHeap ( HeapCrossRef r) [inline, static]

This function instantiates a Heap.

Parameters:
ris the HeapCrossRef which is used.
static PredMap* createPredMap ( const Digraph g) [inline, static]

This function instantiates a PredMap.

Parameters:
gis the digraph, to which we would like to define the PredMap.
static ProcessedMap* createProcessedMap ( const Digraph g) [inline, static]

This function instantiates a ProcessedMap.

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

This function instantiates a DistMap.

Parameters:
gis the digraph, to which we would like to define the DistMap
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines