Aleph::Compute_Maximum_Cardinality_Bipartite_Matching< GT, Max_Flow, SA > Class Template Reference

Class for computing the maximum cardinality matching of a bipartite graph. More...

#include <tpl_bipartite.H>

Public Member Functions
void	operator() (const GT &g, DynDlist< typename GT::Arc * > &matching)
	Computes the maximum bipartite matching of a graph.

Detailed Description

template<class GT, template< class > class Max_Flow = Ford_Fulkerson_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
class Aleph::Compute_Maximum_Cardinality_Bipartite_Matching< GT, Max_Flow, SA >

Class for computing the maximum cardinality matching of a bipartite graph.

The class handles two type parameters:

1. GT the bipartite graph type
2. Max_Flow the maximum flow algorithm to use for the computation. By default, the Ford-Fulkerson algorithm is used.

Definition at line 293 of file tpl_bipartite.H.

Member Function Documentation

operator()()

template<class GT , template< class > class Max_Flow = Ford_Fulkerson_Maximum_Flow, class SA = Dft_Show_Arc<GT>>

void Aleph::Compute_Maximum_Cardinality_Bipartite_Matching< GT, Max_Flow, SA >::operator() ( const GT &  g, DynDlist< typename GT::Arc * > &  matching  )

inline

Computes the maximum bipartite matching of a graph.

compute_maximum_cardinality_bipartite_matching(g,matching) takes a bipartite graph g and computes the maximum bipartite matching in the list matching.

The procedure computes the bipartition sets, then constructs an equivalent unit-capacity flow network, and invokes a maximum flow algorithm on it.

Parameters

[in]	g	the bipartite graph.
[out]	matching	list of arcs that form the matching.

Exceptions

bad_alloc

if there is not enough memory.

Definition at line 310 of file tpl_bipartite.H.

References Aleph::maps().

---

The documentation for this class was generated from the following file:

• tpl_bipartite.H