Detailed Description

template<typename GR, typename CAP, typename TR>
class lemon::MaxCardinalitySearch< GR, CAP, TR >

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.

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.

#include <lemon/max_cardinality_search.h>

Inheritance diagram for MaxCardinalitySearch< GR, CAP, TR >:

Classes
struct	SetCapacityMap
	Named parameter for setting CapacityMap type More...
struct	SetCardinalityMap
	Named parameter for setting CardinalityMap type More...
struct	SetProcessedMap
	Named parameter for setting ProcessedMap type More...
struct	SetHeap
	Named parameter for setting heap and cross reference type More...
struct	SetStandardHeap
	Named parameter for setting heap and cross reference type with automatic allocation More...

Public Types
typedef Traits::Digraph	Digraph
	The type of the underlying digraph.
typedef Traits::CapacityMap::Value	Value
	The type of the capacity of the arcs.
typedef Traits::CapacityMap	CapacityMap
	The type of the map that stores the arc capacities.
typedef Traits::ProcessedMap	ProcessedMap
	The type of the map indicating if a node is processed.
typedef Traits::CardinalityMap	CardinalityMap
	The type of the map that stores the cardinalities of the nodes.
typedef Traits::HeapCrossRef	HeapCrossRef
	The cross reference type used for the current heap.
typedef Traits::Heap	Heap
	The heap type used by the algorithm. It maximizes the priorities.

Public Member Functions
	MaxCardinalitySearch (const Digraph &digraph, const CapacityMap &capacity)
	Constructor.
	MaxCardinalitySearch (const Digraph &digraph)
	Constructor.
	~MaxCardinalitySearch ()
	Destructor.
MaxCardinalitySearch &	capacityMap (const CapacityMap &m)
	Sets the capacity map.
const CapacityMap &	capacityMap () const
	Returns a const reference to the capacity map.
MaxCardinalitySearch &	cardinalityMap (CardinalityMap &m)
	Sets the map storing the cardinalities calculated by the algorithm.
MaxCardinalitySearch &	processedMap (ProcessedMap &m)
	Sets the map storing the processed nodes.
const ProcessedMap &	processedMap () const
	Returns a const reference to the cardinality map.
MaxCardinalitySearch &	heap (Heap &hp, HeapCrossRef &cr)
	Sets the heap and the cross reference used by algorithm.
const Heap &	heap () const
	Returns a const reference to the heap.
const HeapCrossRef &	heapCrossRef () const
	Returns a const reference to the cross reference.
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.
void	init ()
	Initializes the internal data structures.
void	addSource (Node source, Value capacity=0)
	Adds a new source node.
Node	processNextNode ()
	Processes the next node in the priority heap.
Node	nextNode ()
	Next node to be processed.
bool	emptyQueue ()
	Returns `false` if there are nodes to be processed in the priority heap.
int	emptySize ()
	Returns the number of the nodes to be processed in the priority heap.
void	start ()
	Executes the algorithm.
void	start (Node dest)
	Executes the algorithm until `dest` is reached.
template<typename NodeBoolMap>
void	start (const NodeBoolMap &nm)
	Executes the algorithm until a condition is met.
void	run (Node s)
	Runs the maximum cardinality search algorithm from node `s`.
void	run ()
	Runs the maximum cardinality search algorithm for the whole digraph.
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.
Value	cardinality (Node node) const
	The cardinality of a node.
Value	currentCardinality (Node node) const
	The current cardinality of a node.
const CardinalityMap &	cardinalityMap () const
	Returns a reference to the NodeMap of cardinalities.
bool	reached (Node v)
	Checks if a node is reachable from the root.
bool	processed (Node v)
	Checks if a node is processed.

Constructor & Destructor Documentation

◆ MaxCardinalitySearch() [1/2]

template<typename GR, typename CAP, typename TR>

MaxCardinalitySearch	(	const Digraph &	digraph,
		const CapacityMap &	capacity )

inline

Parameters

digraph	the digraph the algorithm will run on.
capacity	the capacity map used by the algorithm.

◆ MaxCardinalitySearch() [2/2]

template<typename GR, typename CAP, typename TR>

MaxCardinalitySearch ( const Digraph & digraph )

inline

Parameters

digraph the digraph the algorithm will run on.

A constant 1 capacity map will be allocated.

Member Function Documentation

◆ capacityMap() [1/2]

template<typename GR, typename CAP, typename TR>

MaxCardinalitySearch & capacityMap ( const CapacityMap & m )

inline

Sets the capacity map.

Returns: (*this)

◆ capacityMap() [2/2]

template<typename GR, typename CAP, typename TR>

const CapacityMap & capacityMap ( ) const

inline

Returns a const reference to the capacity map used by the algorithm.

◆ cardinalityMap() [1/2]

template<typename GR, typename CAP, typename TR>

MaxCardinalitySearch & cardinalityMap ( CardinalityMap & m )

inline

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)

◆ processedMap() [1/2]

template<typename GR, typename CAP, typename TR>

MaxCardinalitySearch & processedMap ( ProcessedMap & m )

inline

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)

◆ processedMap() [2/2]

template<typename GR, typename CAP, typename TR>

const ProcessedMap & processedMap ( ) const

inline

Returns a const reference to the cardinality map used by the algorithm.

◆ heap() [1/2]

template<typename GR, typename CAP, typename TR>

MaxCardinalitySearch & heap	(	Heap &	hp,
		HeapCrossRef &	cr )

inline

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)

◆ heap() [2/2]

template<typename GR, typename CAP, typename TR>

const Heap & heap ( ) const

inline

Returns a const reference to the heap used by the algorithm.

◆ heapCrossRef()

template<typename GR, typename CAP, typename TR>

const HeapCrossRef & heapCrossRef ( ) const

inline

Returns a const reference to the cross reference of the heap.

◆ init()

template<typename GR, typename CAP, typename TR>

void init ( )

inline

Initializes the internal data structures, and clears the heap.

◆ addSource()

template<typename GR, typename CAP, typename TR>

void addSource	(	Node	source,
		Value	capacity = 0 )

inline

Adds a new source node to the priority heap.

It checks if the node has not yet been added to the heap.

◆ processNextNode()

template<typename GR, typename CAP, typename TR>

Node processNextNode ( )

inline

Processes the next node in the priority heap.

Returns: The processed node.

Warning: The priority heap must not be empty!

◆ nextNode()

template<typename GR, typename CAP, typename TR>

Node nextNode ( )

inline

Next node to be processed.

Returns: The next node to be processed or INVALID if the priority heap is empty.

◆ emptyQueue()

template<typename GR, typename CAP, typename TR>

bool emptyQueue ( )

inline

Returns false if there are nodes to be processed in the priority heap

◆ emptySize()

template<typename GR, typename CAP, typename TR>

int emptySize ( )

inline

Returns the number of the nodes to be processed in the priority heap

◆ start() [1/3]

template<typename GR, typename CAP, typename TR>

void start ( )

inline

Executes the algorithm.

Precondition: init() must be called and at least one node should be added with addSource() before using this function.

This method runs the Maximum Cardinality Search algorithm from the source node(s).

◆ start() [2/3]

template<typename GR, typename CAP, typename TR>

void start ( Node dest )

inline

Executes the algorithm until dest is reached.

Precondition: init() must be called and at least one node should be added with addSource() before using this function.

This method runs the MaxCardinalitySearch algorithm from the source nodes.

◆ start() [3/3]

template<typename GR, typename CAP, typename TR>

template<typename NodeBoolMap>

void start ( const NodeBoolMap & nm )

inline

Executes the algorithm until a condition is met.

Precondition: init() must be called and at least one node should be added with addSource() before using this function.

Parameters

nm	must be a bool (or convertible) node map. The algorithm will stop when it reaches a node `v` with nm[v]==true.

◆ run() [1/2]

template<typename GR, typename CAP, typename TR>

void run ( Node s )

inline

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();

◆ run() [2/2]

template<typename GR, typename CAP, typename TR>

void run ( )

inline

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();

}

}

lemon::INVALID
const Invalid INVALID
Invalid iterators.
Definition base.cc:32

◆ cardinality()

template<typename GR, typename CAP, typename TR>

Value cardinality ( Node node ) const

inline

Returns the cardinality of a node.

Precondition: run() must be called before using this function.

Warning: If node v in unreachable from the root the return value of this funcion is undefined.

◆ currentCardinality()

template<typename GR, typename CAP, typename TR>

Value currentCardinality ( Node node ) const

inline

Returns the current cardinality of a node.

Precondition: the given node should be reached but not processed

◆ cardinalityMap() [2/2]

template<typename GR, typename CAP, typename TR>

const CardinalityMap & cardinalityMap ( ) const

inline

Returns a reference to the NodeMap of cardinalities.

Precondition: run() must be called before using this function.

◆ reached()

template<typename GR, typename CAP, typename TR>

bool reached ( Node v )

inline

Returns true if v is reachable from the root.

Warning: The source nodes are initated as unreached.

Precondition: run() must be called before using this function.

◆ processed()

template<typename GR, typename CAP, typename TR>

bool processed ( Node v )

inline

Returns true if v is processed, i.e. the shortest path to v has already found.

Precondition: run() must be called before using this function.

Detailed Description

Classes

Public Types

Public Member Functions

Constructor & Destructor Documentation

◆ MaxCardinalitySearch() [1/2]

◆ MaxCardinalitySearch() [2/2]

Member Function Documentation

◆ capacityMap() [1/2]

◆ capacityMap() [2/2]

◆ cardinalityMap() [1/2]

◆ processedMap() [1/2]

◆ processedMap() [2/2]

◆ heap() [1/2]

◆ heap() [2/2]

◆ heapCrossRef()

◆ init()

◆ addSource()

◆ processNextNode()

◆ nextNode()

◆ emptyQueue()

◆ emptySize()

◆ start() [1/3]

◆ start() [2/3]

◆ start() [3/3]

◆ run() [1/2]

◆ run() [2/2]

◆ cardinality()

◆ currentCardinality()

◆ cardinalityMap() [2/2]

◆ reached()

◆ processed()