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.
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>
Classes | |
struct | SetCapacityMap |
Named parameter for setting CapacityMap type More... | |
struct | SetCardinalityMap |
Named parameter for setting CardinalityMap type More... | |
struct | SetHeap |
Named parameter for setting heap and cross reference type More... | |
struct | SetProcessedMap |
Named parameter for setting ProcessedMap 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. More... | |
MaxCardinalitySearch (const Digraph &digraph) | |
Constructor. More... | |
~MaxCardinalitySearch () | |
Destructor. | |
MaxCardinalitySearch & | capacityMap (const CapacityMap &m) |
Sets the capacity map. More... | |
const CapacityMap & | capacityMap () const |
Returns a const reference to the capacity map. More... | |
MaxCardinalitySearch & | cardinalityMap (CardinalityMap &m) |
Sets the map storing the cardinalities calculated by the algorithm. More... | |
MaxCardinalitySearch & | processedMap (ProcessedMap &m) |
Sets the map storing the processed nodes. More... | |
const ProcessedMap & | processedMap () const |
Returns a const reference to the cardinality map. More... | |
MaxCardinalitySearch & | heap (Heap &hp, HeapCrossRef &cr) |
Sets the heap and the cross reference used by algorithm. More... | |
const Heap & | heap () const |
Returns a const reference to the heap. More... | |
const HeapCrossRef & | heapCrossRef () const |
Returns a const reference to the cross reference. More... | |
Execution control | |
The simplest way to execute the algorithm is to use one of the member functions called run(). | |
void | init () |
Initializes the internal data structures. More... | |
void | addSource (Node source, Value capacity=0) |
Adds a new source node. More... | |
Node | processNextNode () |
Processes the next node in the priority heap. More... | |
Node | nextNode () |
Next node to be processed. More... | |
bool | emptyQueue () |
Returns false if there are nodes to be processed in the priority heap. More... | |
int | emptySize () |
Returns the number of the nodes to be processed in the priority heap. More... | |
void | start () |
Executes the algorithm. More... | |
void | start (Node dest) |
Executes the algorithm until dest is reached. More... | |
template<typename NodeBoolMap > | |
void | start (const NodeBoolMap &nm) |
Executes the algorithm until a condition is met. More... | |
void | run (Node s) |
Runs the maximum cardinality search algorithm from node s . More... | |
void | run () |
Runs the maximum cardinality search algorithm for the whole digraph. More... | |
Query Functions | |
Value | cardinality (Node node) const |
The cardinality of a node. More... | |
Value | currentCardinality (Node node) const |
The current cardinality of a node. More... | |
const CardinalityMap & | cardinalityMap () const |
Returns a reference to the NodeMap of cardinalities. More... | |
bool | reached (Node v) |
Checks if a node is reachable from the root. More... | |
bool | processed (Node v) |
Checks if a node is processed. More... | |
|
inline |
digraph | the digraph the algorithm will run on. |
capacity | the capacity map used by the algorithm. |
|
inline |
digraph | the digraph the algorithm will run on. |
A constant 1 capacity map will be allocated.
|
inline |
Sets the capacity map.
(*this)
|
inline |
Returns a const reference to the capacity map used by the algorithm.
|
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.
(*this)
|
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.
(*this)
|
inline |
Returns a const reference to the cardinality map used by the algorithm.
|
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.
(*this)
|
inline |
Returns a const reference to the heap used by the algorithm.
|
inline |
Returns a const reference to the cross reference of the heap.
|
inline |
Initializes the internal data structures, and clears the heap.
|
inline |
Adds a new source node to the priority heap.
It checks if the node has not yet been added to the heap.
|
inline |
Processes the next node in the priority heap.
|
inline |
Next node to be processed.
|
inline |
Returns false
if there are nodes to be processed in the priority heap
|
inline |
Returns the number of the nodes to be processed in the priority heap
|
inline |
Executes the algorithm.
This method runs the Maximum Cardinality Search algorithm from the source node(s).
|
inline |
Executes the algorithm until dest
is reached.
This method runs the MaxCardinalitySearch algorithm from the source nodes.
|
inline |
Executes the algorithm until a condition is met.
nm | must be a bool (or convertible) node map. The algorithm will stop when it reaches a node v with nm[v]==true . |
|
inline |
This method runs the MaxCardinalitySearch algorithm from a root node s
.
|
inline |
This method runs the MaxCardinalitySearch algorithm from all unprocessed node of the digraph.
|
inline |
Returns the cardinality of a node.
v
in unreachable from the root the return value of this funcion is undefined.
|
inline |
Returns the current cardinality of a node.
|
inline |
Returns a reference to the NodeMap of cardinalities.
|
inline |
Returns true
if v
is reachable from the root.
|
inline |
Returns true
if v
is processed, i.e. the shortest path to v
has already found.