MaxCardinalitySearchDefaultTraits

Declared in lemon/max_cardinality_search.h, in the group Graph Search; the same struct on the Doxygen site.

template< typename GR , typename CAP >
struct MaxCardinalitySearchDefaultTraits

Default traits class of MaxCardinalitySearch class.

Param Digraph:

Digraph type.

Param CapacityMap:

Type of capacity map.

Public Types

typedef GR Digraph

The digraph type the algorithm runs on.

typedef CapMapSelector< CAP >::CapacityMap CapacityMap

The type of the map that stores the arc capacities. It must meet the ReadMap concept.

typedef CapacityMap::Value Value

The type of the capacity of the arcs.

typedef Digraph::template NodeMap< int > HeapCrossRef

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

typedef HeapSelector< CapacityMap >::template Selector< Value , HeapCrossRef >::Heap Heap

The heap type used by MaxCardinalitySearch algorithm. It should maximalize the priorities. The default heap type is the BinHeap, but it is specialized when the CapacityMap is ConstMap< Digraph::Node , Const< int , 1 > > to BucketHeap.

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

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

typedef Digraph::template NodeMap< Value > CardinalityMap

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

Public Static Functions

static inline CapacityMap * createCapacityMap( const Digraph & digraph )

Instantiates a CapacityMap.

This function instantiates a CapacityMap.

Parameters:

digraph – is the digraph, to which we would like to define the CapacityMap.

static inline HeapCrossRef * createHeapCrossRef( const Digraph & digraph )

Instantiates a HeapCrossRef.

This function instantiates a HeapCrossRef.

Parameters:

digraph – is the digraph, to which we would like to define the HeapCrossRef.

static inline Heap * createHeap( HeapCrossRef & crossref )

Instantiates a Heap.

This function instantiates a Heap.

Parameters:

crossref – The cross reference of the heap.

static inline ProcessedMap * createProcessedMap( const Digraph & digraph )

Instantiates a ProcessedMap.

This function instantiates a ProcessedMap.

Parameters:

digraph – is the digraph, to which we would like to define the ProcessedMap

static inline CardinalityMap * createCardinalityMap( const Digraph & digraph )

Instantiates a CardinalityMap.

This function instantiates a CardinalityMap.

Parameters:

digraph – is the digraph, to which we would like to define the CardinalityMap

template< typename CM >
struct CapMapSelector

Public Types

typedef CM CapacityMap

Public Static Functions

static inline CapacityMap * createCapacityMap( const Digraph & g )
template< typename CM >
struct CapMapSelector< ConstMap< CM , Const< int , 1 > > >

Public Types

typedef ConstMap< CM , Const< int , 1 > > CapacityMap

Public Static Functions

static inline CapacityMap * createCapacityMap( const Digraph & )
template< typename CapacityMap >
struct HeapSelector
template< typename Value , typename Ref >
struct Selector

Public Types

typedef BinHeap< Value , Ref , std::greater< Value > > Heap
template< typename CapacityKey >
struct HeapSelector< ConstMap< CapacityKey , Const< int , 1 > > >
template< typename Value , typename Ref >
struct Selector

Public Types

typedef BucketHeap< Ref , false > Heap