MaxCardinalitySearch
Declared in lemon/max_cardinality_search.h, in the group Graph Search; the same class on the Doxygen site.
-
template< typename GR , typename CAP , typename TR >
class MaxCardinalitySearch Maximum Cardinality Search algorithm class.
This class provides an efficient implementation of Maximum Cardinality Search algorithm. The maximum cardinality search first chooses any node of the digraph. Then every time it chooses one unprocessed node with maximum cardinality, i.e the sum of capacities on out arcs to the nodes which were previusly processed. If there is a cut in the digraph the algorithm should choose again any unprocessed node of the digraph. The arc capacities are passed to the algorithm using a ReadMap, so it is easy to change it to any kind of capacity.
The type of the capacity is determined by the Value of the capacity map.
It is also possible to change the underlying priority heap.
- Template Parameters:
GR – The digraph type the algorithm runs on. The value of Digraph is not used directly by the search algorithm, it is only passed to MaxCardinalitySearchDefaultTraits.
CAP – This read-only ArcMap determines the capacities of the arcs. It is read once for each arc, so the map may involve in relatively time consuming process to compute the arc capacity if it is necessary. The default map type is ConstMap< concepts::Digraph::Arc , Const< int , 1 > >. The value of CapacityMap is not used directly by search algorithm, it is only passed to MaxCardinalitySearchDefaultTraits.
TR – Traits class to set various data types used by the algorithm. The default traits class is MaxCardinalitySearchDefaultTraits< GR , CAP >. See MaxCardinalitySearchDefaultTraits for the documentation of a MaxCardinalitySearch traits class.
Execution control
The simplest way to execute the algorithm is to use one of the member functions called run()
.
If you need more control on the execution, first you must call
init(), then you can add several source nodes with addSource(). Finally start() will perform the computation.-
inline void init()
Initializes the internal data structures.
Initializes the internal data structures, and clears the heap.
-
inline void addSource( Node source , Value capacity = 0 )
Adds a new source node.
Adds a new source node to the priority heap.
It checks if the node has not yet been added to the heap.
-
inline Node processNextNode()
Processes the next node in the priority heap.
Warning
The priority heap must not be empty!
- Returns:
The processed node.
-
inline Node nextNode()
Next node to be processed.
- Returns:
The next node to be processed or INVALID if the priority heap is empty.
-
inline bool emptyQueue()
Returns
falseif there are nodes to be processed in the priority heap
-
inline int emptySize()
Returns the number of the nodes to be processed in the priority heap
-
inline void start()
Executes the algorithm.
This method runs the Maximum Cardinality Search algorithm from the source node(s).
- Pre:
init() must be called and at least one node should be added with addSource() before using this function.
-
inline void start( Node dest )
Executes the algorithm until
destis reached.This method runs the MaxCardinalitySearch algorithm from the source nodes.
- Pre:
init() must be called and at least one node should be added with addSource() before using this function.
-
template< typename NodeBoolMap >
inline void start( const NodeBoolMap & nm ) Executes the algorithm until a condition is met.
- Parameters:
nm – must be a bool (or convertible) node map. The algorithm will stop when it reaches a node
vwithnm[v]==true.- Pre:
init() must be called and at least one node should be added with addSource() before using this function.
-
inline void run( Node s )
Runs the maximum cardinality search algorithm from node
s.This method runs the MaxCardinalitySearch algorithm from a root node
s.Note
d.run(s) is just a shortcut of the following code.
d.init(); d.addSource( s ); d.start();
-
inline void run()
Runs the maximum cardinality search algorithm for the whole digraph.
This method runs the MaxCardinalitySearch algorithm from all unprocessed node of the digraph.
Note
d.run(s) is just a shortcut of the following code.
d.init(); for( NodeIt it( digraph ) ; it != INVALID ; ++it ) { if( ! d.reached( it ) ) { d.addSource( s ); d.start(); } }
Query Functions
The results of the maximum cardinality search algorithm can be obtained using these functions.
Before the use of these functions, either
run() or start() must be called.-
inline Value cardinality( Node node ) const
The cardinality of a node.
Returns the cardinality of a node.
Warning
If node
vin unreachable from the root the return value of this funcion is undefined.- Pre:
run() must be called before using this function.
-
inline Value currentCardinality( Node node ) const
The current cardinality of a node.
Returns the current cardinality of a node.
- Pre:
the given node should be reached but not processed
-
inline const CardinalityMap & cardinalityMap() const
Returns a reference to the NodeMap of cardinalities.
- Pre:
run() must be called before using this function.
Public Types
-
typedef Traits::CardinalityMap CardinalityMap
The type of the map that stores the cardinalities of the nodes.
-
typedef MaxCardinalitySearch Create
Public Functions
-
inline MaxCardinalitySearch( const Digraph & digraph , const CapacityMap & capacity )
Constructor.
- Parameters:
digraph – the digraph the algorithm will run on.
capacity – the capacity map used by the algorithm.
-
inline MaxCardinalitySearch( const Digraph & digraph )
Constructor.
A constant 1 capacity map will be allocated.
- Parameters:
digraph – the digraph the algorithm will run on.
-
inline ~MaxCardinalitySearch()
Destructor.
-
inline MaxCardinalitySearch & capacityMap( const CapacityMap & m )
Sets the capacity map.
- Returns:
(*this)
-
inline const CapacityMap & capacityMap() const
Returns a const reference to the capacity map.
Returns a const reference to the capacity map used by the algorithm.
-
inline MaxCardinalitySearch & cardinalityMap( CardinalityMap & m )
Sets the map storing the cardinalities calculated by the algorithm. If you don’t use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.
- Returns:
(*this)
-
inline MaxCardinalitySearch & processedMap( ProcessedMap & m )
Sets the map storing the processed nodes. If you don’t use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.
- Returns:
(*this)
-
inline const ProcessedMap & processedMap() const
Returns a const reference to the processed map.
Returns a const reference to the processed map used by the algorithm.
-
inline MaxCardinalitySearch & heap( Heap & hp , HeapCrossRef & cr )
Sets the heap and the cross reference used by algorithm. If you don’t use this function before calling run(), it will allocate one. The destuctor deallocates this automatically allocated map, of course.
- Returns:
(*this)
-
inline const Heap & heap() const
Returns a const reference to the heap.
Returns a const reference to the heap used by the algorithm.
-
inline const HeapCrossRef & heapCrossRef() const
Returns a const reference to the cross reference.
Returns a const reference to the cross reference of the heap.
Protected Functions
-
inline MaxCardinalitySearch()
-
template< class T >
struct DefCapacityMapTraits : public Traits -
Public Static Functions
-
static inline CapacityMap * createCapacityMap( const Digraph & )
-
static inline CapacityMap * createCapacityMap( const Digraph & )
-
template< class T >
struct SetCapacityMap : public MaxCardinalitySearch< Digraph , CapacityMap , DefCapacityMapTraits< T > > Named parameter for setting CapacityMap type
Named parameter for setting CapacityMap type for the algorithm.
Public Types
-
typedef MaxCardinalitySearch< Digraph , CapacityMap , DefCapacityMapTraits< T > > Create
-
typedef MaxCardinalitySearch< Digraph , CapacityMap , DefCapacityMapTraits< T > > Create
-
template< class T >
struct DefCardinalityMapTraits : public Traits -
Public Static Functions
-
static inline CardinalityMap * createCardinalityMap( const Digraph & )
-
static inline CardinalityMap * createCardinalityMap( const Digraph & )
-
template< class T >
struct SetCardinalityMap : public MaxCardinalitySearch< Digraph , CapacityMap , DefCardinalityMapTraits< T > > Named parameter for setting CardinalityMap type
Named parameter for setting CardinalityMap type for the algorithm.
Public Types
-
typedef MaxCardinalitySearch< Digraph , CapacityMap , DefCardinalityMapTraits< T > > Create
-
typedef MaxCardinalitySearch< Digraph , CapacityMap , DefCardinalityMapTraits< T > > Create
-
template< class T >
struct DefProcessedMapTraits : public Traits -
Public Static Functions
-
static inline ProcessedMap * createProcessedMap( const Digraph & )
-
static inline ProcessedMap * createProcessedMap( const Digraph & )
-
template< class T >
struct SetProcessedMap : public MaxCardinalitySearch< Digraph , CapacityMap , DefProcessedMapTraits< T > > Named parameter for setting ProcessedMap type
Named parameter for setting ProcessedMap type for the algorithm.
Public Types
-
typedef MaxCardinalitySearch< Digraph , CapacityMap , DefProcessedMapTraits< T > > Create
-
typedef MaxCardinalitySearch< Digraph , CapacityMap , DefProcessedMapTraits< T > > Create
-
template< class H , class CR >
struct DefHeapTraits : public Traits -
Public Static Functions
-
static inline HeapCrossRef * createHeapCrossRef( const Digraph & )
-
static inline Heap * createHeap(HeapCrossRef&)
-
static inline HeapCrossRef * createHeapCrossRef( const Digraph & )
-
template< class H , class CR = typename Digraph::template NodeMap< int > >
struct SetHeap : public MaxCardinalitySearch< Digraph , CapacityMap , DefHeapTraits< H , typename Digraph::template NodeMap< int > > > Named parameter for setting heap and cross reference type
Named parameter for setting heap and cross reference type for the algorithm.
Public Types
-
typedef MaxCardinalitySearch< Digraph , CapacityMap , DefHeapTraits< H , CR > > Create
-
typedef MaxCardinalitySearch< Digraph , CapacityMap , DefHeapTraits< H , CR > > Create
-
template< class H , class CR >
struct DefStandardHeapTraits : public Traits -
Public Static Functions
-
static inline HeapCrossRef * createHeapCrossRef( const Digraph & digraph )
-
static inline Heap * createHeap( HeapCrossRef & crossref )
-
static inline HeapCrossRef * createHeapCrossRef( const Digraph & digraph )
-
template< class H , class CR = typename Digraph::template NodeMap< int > >
struct SetStandardHeap : public MaxCardinalitySearch< Digraph , CapacityMap , DefStandardHeapTraits< H , typename Digraph::template NodeMap< int > > > Named parameter for setting heap and cross reference type with automatic allocation
Named parameter for setting heap and cross reference type. It can allocate the heap and the cross reference object if the cross reference’s constructor waits for the digraph as parameter and the heap’s constructor waits for the cross reference.
Public Types
-
typedef MaxCardinalitySearch< Digraph , CapacityMap , DefStandardHeapTraits< H , CR > > Create
-
typedef MaxCardinalitySearch< Digraph , CapacityMap , DefStandardHeapTraits< H , CR > > Create