MinCostArborescenceDefaultTraits

Declared in lemon/min_cost_arborescence.h, in the group Minimum Spanning Tree Algorithms; the same struct on the Doxygen site.

template< class GR , class CM >
struct MinCostArborescenceDefaultTraits

Default traits class for MinCostArborescence class.

Template Parameters:
  • GR – Digraph type.

  • CM – Type of the cost map.

Public Types

typedef GR Digraph

The digraph type the algorithm runs on.

typedef CM CostMap

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

typedef CostMap::Value Value

The value type of the costs.

typedef Digraph::template ArcMap< bool > ArborescenceMap

The type of the map that stores which arcs are in the arborescence. It must conform to the WriteMap concept, and its value type must be bool (or convertible). Initially it will be set to false on each arc, then it will be set on each arborescence arc once.

typedef Digraph::template NodeMap< typename Digraph::Arc > PredMap

The type of the PredMap. It must confrom to the WriteMap concept, and its value type must be the Arc type of the digraph.

typedef Digraph::template NodeMap< int > HeapCrossRef

The type of the cross reference map of the heap of the arcs.

typedef BinHeap< int , HeapCrossRef > Heap

The type of the heap of the arcs entering the nodes, on their order in the costs.

Public Static Functions

static inline ArborescenceMap * createArborescenceMap( const Digraph & digraph )

Instantiates a ArborescenceMap.

This function instantiates a ArborescenceMap.

Parameters:

digraph – The digraph to which we would like to calculate the ArborescenceMap.

static inline PredMap * createPredMap( const Digraph & digraph )

Instantiates a PredMap.

This function instantiates a PredMap.

Parameters:

digraph – The digraph to which we would like to define the PredMap.