MaxCardinalitySearch< _Graph, _CapacityMap, _Traits > Class Template Reference
[Graph Search]

---

Detailed Description

template<typename _Graph, typename _CapacityMap, typename _Traits>
class lemon::MaxCardinalitySearch< _Graph, _CapacityMap, _Traits >

This class provides an efficient implementation of Maximum Cardinality Search algorithm. The maximum cardinality search chooses first time any node of the graph. Then every time it chooses the node which is connected to the processed nodes at most in the sum of capacities on the out edges. If there is a cut in the graph the algorithm should choose again any unprocessed node of the graph. Each node cardinality is the sum of capacities on the out edges to the nodes which are processed before the given node.

The edge 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:

	_Graph	The graph type the algorithm runs on. The default value is ListGraph. The value of Graph is not used directly by the search algorithm, it is only passed to MaxCardinalitySearchDefaultTraits.
	_CapacityMap	This read-only EdgeMap determines the capacities of the edges. It is read once for each edge, so the map may involve in relatively time consuming process to compute the edge capacity if it is necessary. The default map type is Graph::EdgeMap<int>. The value of CapacityMap is not used directly by search algorithm, it is only passed to MaxCardinalitySearchDefaultTraits.
	_Traits	Traits class to set various data types used by the algorithm. The default traits class is MaxCardinalitySearchDefaultTraits<_Graph, _CapacityMap>. See MaxCardinalitySearchDefaultTraits for the documentation of a MaxCardinalitySearch traits class.

Author:

Balazs Dezso

#include <lemon/nagamochi_ibaraki.h>

List of all members.

Classes
struct	DefCardinalityMap
struct	DefHeap
struct	DefProcessedMap
struct	DefStandardHeap
	Named parameter for setting heap and cross reference type with automatic allocation More...
class	UninitializedParameter
	Exception for uninitialized parameters. More...
Public Types
typedef Traits::Graph	Graph
	The type of the underlying graph.
typedef Traits::CapacityMap::Value	Value
	The type of the capacity of the edges.
typedef Traits::CapacityMap	CapacityMap
	The type of the map that stores the edge 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 maximize the priorities.
Public Member Functions
	MaxCardinalitySearch (const Graph &graph, const CapacityMap &capacity)
	Constructor.
	~MaxCardinalitySearch ()
	Destructor.
MaxCardinalitySearch &	capacityMap (const CapacityMap &m)
	Sets 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.
MaxCardinalitySearch &	heap (Heap &hp, HeapCrossRef &cr)
	Sets the heap and the cross reference used by algorithm.
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 actual path computation.
void	init ()
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	queueSize ()
	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 maximal cardinality search algorithm from node s.
void	run ()
	Runs the maximal cardinality search algorithm for the whole graph.
Query Functions
The result 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.
Private Attributes
const Graph *	_graph
	Pointer to the underlying graph.
const CapacityMap *	_capacity
	Pointer to the capacity map.
CardinalityMap *	_cardinality
	Pointer to the map of cardinality.
bool	local_cardinality
	Indicates if _cardinality is locally allocated (true) or not.
ProcessedMap *	_processed
	Pointer to the map of processed status of the nodes.
bool	local_processed
	Indicates if _processed is locally allocated (true) or not.
HeapCrossRef *	_heap_cross_ref
	Pointer to the heap cross references.
bool	local_heap_cross_ref
	Indicates if _heap_cross_ref is locally allocated (true) or not.
Heap *	_heap
	Pointer to the heap.
bool	local_heap
	Indicates if _heap is locally allocated (true) or not.

---

Constructor & Destructor Documentation

MaxCardinalitySearch	(	const Graph &	graph,
		const CapacityMap &	capacity
	)			[inline]

Parameters:

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

---

Member Function Documentation

MaxCardinalitySearch& capacityMap

(

const CapacityMap &

m

)

[inline]

Sets the capacity map.

Returns:

(*this)

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)

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)

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)

void init

(

)

[inline]

Initializes the internal data structures.

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.

Node processNextNode

(

)

[inline]

Processes the next node in the priority heap.

Returns:

The processed node.

Warning:

The priority heap must not be empty!

Node nextNode

(

)

[inline]

Next node to be processed.

Returns:

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

bool emptyQueue

(

)

[inline]

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

int queueSize

(

)

[inline]

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

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).

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.

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.

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

void run

(

)

[inline]

This method runs the MaxCardinalitySearch algorithm from all unprocessed node of the graph.

Note:

d.run(s) is just a shortcut of the following code.

         d.init();
         for (NodeIt it(graph); it != INVALID; ++it) {
           if (!d.reached(it)) {
             d.addSource(s);
             d.start();
           }
         }

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.

Value currentCardinality

(

Node

node

)

const [inline]

Returns the current cardinality of a node.

Precondition:

the given node should be reached but not processed

const CardinalityMap& cardinalityMap

(

)

const [inline]

Returns a reference to the NodeMap of cardinalities.

Precondition:

run() must be called before using this function.

bool reached

(

Node

v

)

[inline]

Returns true if v is reachable from the root.

Warning:

The source nodes are inditated as unreached.

Precondition:

run() must be called before using this function.

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.