Example MWMCB_MATCHING_T()
The following program shows how the function MWMCB_MATCHING_T() can
be used to compute a maximum weighted maximum cardinality matching and
a corresponding potential function for the nodes in a bipartite graph.
Remark: The graph algorithms in LEDA are generic, that is, they
accept graphs as well as parameterized
graphs.
In order to use the template function MWMCB_MATCHING_T()
we need to include <LEDA/templates/mwb_matching.t>. We
use the LEDA number type integer
as the number type NT for
the edge weights. In constrast to the C++ number type int,
LEDA's integer does not overflow.
#include <LEDA/graph/graph.h>
#include <LEDA/graph/templates/mwb_matching.h>
#include <LEDA/numbers/integer.h>
using namespace leda;
In main() we first create a bipartite graph G=(A,B,E)
with three nodes in A, four nodes in B, and
six edges. We use a list<node>
to store A and B. Then we assign weights to
the edges using an edge_array<integer>
weight.
int main()
{
graph G;
list<node> A;
node a0=G.new_node(); A.append(a0);
node a1=G.new_node(); A.append(a1);
node a2=G.new_node(); A.append(a2);
list<node> B;
node b0=G.new_node(); B.append(b0);
node b1=G.new_node(); B.append(b1);
node b2=G.new_node(); B.append(b2);
node b3=G.new_node(); B.append(b3);
edge e0=G.new_edge(a0,b1); edge e1=G.new_edge(a0,b3);
edge e2=G.new_edge(a1,b0); edge e3=G.new_edge(a2,b0);
edge e4=G.new_edge(a2,b2); edge e5=G.new_edge(a0,b0);
edge_array<integer> weight(G);
weight[e0]=1; weight[e1]=2; weight[e2]=3;
weight[e3]=2; weight[e4]=1; weight[e5]=10;
The result of MWMCB_MATCHING_T() is a list<edge>
M containing the edges in the maximum weighted maximum cardinality
matching and a node_array<integer>
pot for the potentials of the nodes of G.
node_array<integer> pot(G);
list<edge> M=MWMCB_MATCHING_T(G,A,B,weight,pot);
std::cout << "Maximum Weighted Maximum "
<< " Cardinality Matching:" << std::endl;
integer weight_of_M=0;
edge e;
forall(e,M) {G.print_edge(e); weight_of_M+=weight[e];}
std::cout << " weight: " << weight_of_M << std::endl;
node v; forall_nodes(v,G) {
std::cout << "pot"; G.print_node(v);
std::cout << "=" << pot[v] << std::endl;
}
return 0;
}
Remark 1: Notice that the resulting matching in our example is
a maximum cardinality matching for G, but not a maximum weighted matching.
Remark 2: There is a variant of MWMCB_MATCHING_T()
that does not need the parameter pot.
Tip: Using the smaller set as A and the bigger set
as B leads to smaller running times, in general.
|