Example MAX_WEIGHT_BIPARTITE_MATCHING()
The following program shows how the function MAX_WEIGHT_BIPARTITE_MATCHING()
can be used to compute a maximum weighted matching and a corresponding
potential function for the nodes in a bipartite graph. It also shows how
the function CHECK_MCB() can be used to check the correctness
of the result.
Remark: The graph algorithms in LEDA are generic, that is, they
accept graphs as well as parameterized
graphs.
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. We use an edge_array<double>
weight to store the weights of the edges of G. .
The variant of MAX_WEIGHT_BIPARTITE_MATCHING() for int
can be used in exactly the same way. You only need to replace double
by int in weight and pot.
#include <LEDA/graph/graph.h>
#include <LEDA/graph/mwb_matching.h>
using namespace leda;
int main()
{
graph G;
list<node> B;
node n0=G.new_node(); B.append(n0);
node n1=G.new_node(); B.append(n1);
node n2=G.new_node(); B.append(n2);
node n3=G.new_node(); B.append(n3);
list<node> A;
node n4=G.new_node(); A.append(n4);
node n5=G.new_node(); A.append(n5);
node n6=G.new_node(); A.append(n6);
edge e0=G.new_edge(n4,n0); edge e1=G.new_edge(n4,n1);
edge e2=G.new_edge(n4,n2); edge e3=G.new_edge(n5,n2);
edge e4=G.new_edge(n6,n2); edge e5=G.new_edge(n6,n3);
edge_array<double> weight(G);
weight[e0]=1; weight[e1]=1; weight[e2]=3;
weight[e3]=1; weight[e4]=1; weight[e5]=1;
In order to avoid that MAX_WEIGHT_BIPARTITE_MATCHING() modifies
the edge weights internally, we call MWBM_SCALE_WEIGHTS()
explicitely. In this small example the weights are, of course, unchanged
and MWBM_SCALE_WEIGHTS() returns true. We only
want to demonstrate the usage here.
The result of MAX_WEIGHT_BIPARTITE_MATCHING() is a list<edge>
M containing the edges in the maximum weighted matching and a
node_array<integer> pot
for the potentials of the nodes of G.
We use CHECK_MCB_T() to check if M is a maximum
weighted matching of G and pot is a corresponding
potential function. If the result is correct we output M
and pot.
bool unmodified_weights=MWBM_SCALE_WEIGHTS(G,weight);
if (!unmodified_weights) {
std::cout << "Warning: MWBM_SCALE_WEIGHTS()"
<< " modified your edge weights!" << std::endl;
}
node_array<double> pot(G);
list<edge> M;
M=MAX_WEIGHT_BIPARTITE_MATCHING(G,A,B,weight,pot);
bool result_correct=CHECK_MWBM(G,weight,M,pot);
if (result_correct) {
std::cout << "Maximum Weighted Matching:" << std::endl;
double 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) {
cstd::out << "pot"; G.print_node(v);
std::cout << "=" << pot[v] << std::endl;
}
}
else std::cout << "Error: M and pot are not"
<< " a correct solution!" << std::endl;
return 0;
}
Remark: There are variants of MAX_WEIGHT_MATCHING()
that do not need the parameter pot and variants without explicitely
stating the bipartition of G as list<node> A,
list<node> B. Have look at the Manual
Page Bipartite Weighted Matchings and Assignments for details.
Tip: Using the smaller set as A and the bigger set
as B leads to smaller running times, in general.
|