PrimDefaultTraits< GR, CM > Struct Template Reference

---

Detailed Description

template<class GR, class CM>
struct lemon::PrimDefaultTraits< GR, CM >

Default traits class of Prim class.

Parameters:

	GR	Graph type.
	CM	Type of cost map.

#include <lemon/prim.h>

List of all members.

Public Types
typedef GR	UGraph
	The graph type the algorithm runs on.
typedef CM	CostMap
	The type of the map that stores the edge costs.
typedef UGraph::template NodeMap< int >	HeapCrossRef
	The cross reference type used by heap.
typedef BinHeap< typename CM::Value, HeapCrossRef, std::less< Value > >	Heap
	The heap type used by Prim algorithm.
typedef UGraph::template NodeMap< typename GR::UEdge >	PredMap
	The type of the map that stores the last edges of the minimum spanning tree.
typedef NullMap< typename UGraph::UEdge, bool >	TreeMap
typedef NullMap< typename UGraph::Node, bool >	ProcessedMap
	The type of the map that stores whether a nodes is processed.
Static Public Member Functions
static HeapCrossRef *	createHeapCrossRef (const GR &_graph)
	Instantiates a HeapCrossRef.
static PredMap *	createPredMap (const GR &_graph)
	Instantiates a PredMap.
static TreeMap *	createTreeMap (const GR &)
	Instantiates a TreeMap.
static ProcessedMap *	createProcessedMap (const GR &_graph)
	Instantiates a ProcessedMap.

---

Member Typedef Documentation

typedef CM CostMap

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

typedef UGraph::template NodeMap<int> HeapCrossRef

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

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

The heap type used by Prim algorithm.

See also:

BinHeap

Prim

typedef UGraph::template NodeMap<typename GR::UEdge> PredMap

The type of the map that stores the last edges of the minimum spanning tree. It must meet the WriteMap concept.

typedef NullMap<typename UGraph::UEdge,bool> TreeMap

The type of the map that stores whether an edge is in the spanning tree or not. The type of the map that stores whether an edge is in the spanning tree or not. By default it is a NullMap.

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

The type of the map that stores whether a nodes is processed. It must meet the WriteMap concept. By default it is a NodeMap<bool>.

---

Member Function Documentation

static HeapCrossRef* createHeapCrossRef

(

const GR &

_graph

)

[inline, static]

This function instantiates a HeapCrossRef.

Parameters:

_graph

is the graph, to which we would like to define the HeapCrossRef.

static PredMap* createPredMap

(

const GR &

_graph

)

[inline, static]

This function instantiates a PredMap.

Parameters:

_graph

is the graph, to which we would like to define the PredMap.

static TreeMap* createTreeMap

(

const GR &

)

[inline, static]

This function instantiates a TreeMap.

The first parameter is the graph, to which we would like to define the TreeMap

static ProcessedMap* createProcessedMap

(

const GR &

_graph

)

[inline, static]

This function instantiates a ProcessedMap.

Parameters:

_graph

is the graph, to which we would like to define the ProcessedMap