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

Default traits class of MaxCardinalitySearch class. More...

#include <lemon/max_cardinality_search.h>

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.
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.
typedef HeapSelector< CapacityMap >::template Selector< Value , HeapCrossRef >::Heap Heap
 The heap type used by MaxCardinalitySearch algorithm.
typedef NullMap< typename Digraph::Node , bool > ProcessedMap
 The type of the map that stores whether a node is processed.
typedef Digraph::template NodeMap< Value > CardinalityMap
 The type of the map that stores the cardinalities of the nodes.

Static Public Member Functions

static CapacityMap * createCapacityMap (const Digraph &digraph)
 Instantiates a CapacityMap.
static HeapCrossRef * createHeapCrossRef (const Digraph &digraph)
 Instantiates a HeapCrossRef.
static Heap * createHeap (HeapCrossRef &crossref)
 Instantiates a Heap.
static ProcessedMap * createProcessedMap (const Digraph &digraph)
 Instantiates a ProcessedMap.
static CardinalityMap * createCardinalityMap (const Digraph &digraph)
 Instantiates a CardinalityMap.

Detailed Description

template< typename GR , typename CAP >
struct lemon::MaxCardinalitySearchDefaultTraits< GR , CAP >

Default traits class of MaxCardinalitySearch class.

Parameters
DigraphDigraph type.
CapacityMapType of capacity map.

Member Typedef Documentation

◆ CapacityMap

template< typename GR , typename CAP >
typedef CapMapSelector< CAP >::CapacityMap CapacityMap

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

◆ HeapCrossRef

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

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

◆ Heap

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

See also
MaxCardinalitySearch

◆ ProcessedMap

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

◆ CardinalityMap

template< typename GR , typename CAP >
typedef Digraph::template NodeMap< Value > CardinalityMap

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

Member Function Documentation

◆ createCapacityMap()

template< typename GR , typename CAP >
CapacityMap * createCapacityMap ( const Digraph & digraph)
inlinestatic

This function instantiates a CapacityMap.

Parameters
digraphis the digraph, to which we would like to define the CapacityMap.

◆ createHeapCrossRef()

template< typename GR , typename CAP >
HeapCrossRef * createHeapCrossRef ( const Digraph & digraph)
inlinestatic

This function instantiates a HeapCrossRef.

Parameters
digraphis the digraph, to which we would like to define the HeapCrossRef.

◆ createHeap()

template< typename GR , typename CAP >
Heap * createHeap ( HeapCrossRef & crossref)
inlinestatic

This function instantiates a Heap.

Parameters
crossrefThe cross reference of the heap.

◆ createProcessedMap()

template< typename GR , typename CAP >
ProcessedMap * createProcessedMap ( const Digraph & digraph)
inlinestatic

This function instantiates a ProcessedMap.

Parameters
digraphis the digraph, to which we would like to define the ProcessedMap

◆ createCardinalityMap()

template< typename GR , typename CAP >
CardinalityMap * createCardinalityMap ( const Digraph & digraph)
inlinestatic

This function instantiates a CardinalityMap.

Parameters
digraphis the digraph, to which we would like to define the CardinalityMap