abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
DijkstraDefaultTraits< GR , LEN > Struct Template Reference

Default traits class of Dijkstra class. More...

#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 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.

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.

Member Typedef Documentation

◆ LengthMap

template< typename GR , typename LEN >
typedef LEN LengthMap

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

◆ OperationTraits

template< typename GR , typename LEN >
typedef DijkstraDefaultOperationTraits< Value > OperationTraits

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

See also
DijkstraDefaultOperationTraits

◆ HeapCrossRef

template< typename GR , typename LEN >
typedef Digraph::template NodeMap< int > HeapCrossRef

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

◆ Heap

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

The heap type used by the Dijkstra algorithm.

See also
BinHeap
Dijkstra

◆ PredMap

template< typename GR , typename LEN >
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

template< typename GR , typename LEN >
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

template< typename GR , typename LEN >
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()

template< typename GR , typename LEN >
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()

template< typename GR , typename LEN >
Heap * createHeap ( HeapCrossRef & r)
inlinestatic

This function instantiates a Heap.

◆ createPredMap()

template< typename GR , typename LEN >
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()

template< typename GR , typename LEN >
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()

template< typename GR , typename LEN >
DistMap * createDistMap ( const Digraph & g)
inlinestatic

This function instantiates a DistMap.

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