Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

DijkstraDefaultTraits Struct Template Reference

#include <lemon/dijkstra.h>

Inheritance diagram for DijkstraDefaultTraits:

Inheritance graph
[legend]
List of all members.

Detailed Description

template<class GR, class LM>
struct lemon::DijkstraDefaultTraits< GR, LM >

Default traits class of Dijkstra class.
Parameters:
GR Graph type.
LM Type of length map.

Definition at line 40 of file dijkstra.h.

Public Types

typedef GR Graph
 The graph type the algorithm runs on.
typedef LM LengthMap
 The type of the map that stores the edge lengths.
typedef BinHeap< typename
Graph::Node, typename LM::Value,
typename GR::template NodeMap<
int >, std::less< Value > > 
Heap
 The heap type used by Dijkstra algorithm.
typedef Graph::template NodeMap<
typename GR::Edge > 
PredMap
 The type of the map that stores the last edges of the shortest paths.
typedef NullMap< typename
Graph::Node, typename Graph::Node > 
PredNodeMap
 The type of the map that stores the last but one nodes of the shortest paths.
typedef NullMap< typename
Graph::Node, bool > 
ReachedMap
 The type of the map that stores whether a nodes is reached.
typedef Graph::template NodeMap<
typename LM::Value > 
DistMap
 The type of the map that stores the dists of the nodes.

Static Public Member Functions

static PredMapcreatePredMap (const GR &G)
 Instantiates a PredMap.
static PredNodeMapcreatePredNodeMap (const GR &G)
 Instantiates a PredNodeMap.
static ReachedMapcreateReachedMap (const GR &G)
 Instantiates a ReachedMap.
static DistMapcreateDistMap (const GR &G)
 Instantiates a DistMap.


Member Typedef Documentation

typedef LM LengthMap
 

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

Definition at line 48 of file dijkstra.h.

typedef BinHeap<typename Graph::Node, typename LM::Value, typename GR::template NodeMap<int>, std::less<Value> > Heap
 

The heap type used by Dijkstra algorithm.

See also:
BinHeap

Dijkstra

Definition at line 60 of file dijkstra.h.

typedef Graph::template NodeMap<typename GR::Edge> PredMap
 

The type of the map that stores the last edges of the shortest paths. It must meet the WriteMap concept.

Definition at line 69 of file dijkstra.h.

typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap
 

The type of the map that stores the last but one nodes of the shortest paths. It must meet the WriteMap concept.

Definition at line 86 of file dijkstra.h.

typedef NullMap<typename Graph::Node,bool> ReachedMap
 

The type of the map that stores whether a nodes is reached. It must meet the WriteMap concept. By default it is a NullMap.

Todo:
If it is set to a real map, Dijkstra::reached() should read this.
Todo:
named parameter to set this type, function to read and write.

Definition at line 104 of file dijkstra.h.

typedef Graph::template NodeMap<typename LM::Value> DistMap
 

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

Definition at line 119 of file dijkstra.h.


Member Function Documentation

static PredMap* createPredMap const GR &  G  )  [inline, static]
 

This function instantiates a PredMap.

Parameters:
G is the graph, to which we would like to define the PredMap.
Todo:
The graph alone may be insufficient for the initialization

Definition at line 75 of file dijkstra.h.

static PredNodeMap* createPredNodeMap const GR &  G  )  [inline, static]
 

This function instantiates a PredNodeMap.

Parameters:
G is the graph, to which we would like to define the PredNodeMap

Definition at line 92 of file dijkstra.h.

static ReachedMap* createReachedMap const GR &  G  )  [inline, static]
 

This function instantiates a ReachedMap.

Parameters:
G is the graph, to which we would like to define the ReachedMap

Definition at line 110 of file dijkstra.h.

static DistMap* createDistMap const GR &  G  )  [inline, static]
 

This function instantiates a DistMap.

Parameters:
G is the graph, to which we would like to define the DistMap

Definition at line 124 of file dijkstra.h.


The documentation for this struct was generated from the following file:
Generated on Mon Feb 21 15:02:30 2005 for LEMON by  doxygen 1.4.1