Example Maximum Weighted Matching in General Graphs

The following program shows how the function MAX_WEIGHT_MATCHING() can be used to compute a maximum weighted matching in a graph. The correctness of the result is checked internally.

Remark: The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs.

In main() we first create a graph G=(V,E) with six nodes and nine edges. We assign weights of type int to the edges using an edge_array<int> weight. The edge weights are multiples of four in order to avoid the internal modification. The result of MAX_WEIGHT_MATCHING() is a list<edge> M containing the edges in the maximum weighted matching of G and weight.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/mw_matching.h>

using namespace leda;

int main()
{
  graph G; 

  node n0=G.new_node(); node n1=G.new_node();
  node n2=G.new_node(); node n3=G.new_node();
  node n4=G.new_node(); node n5=G.new_node();

  edge e0=G.new_edge(n0,n1); edge e1=G.new_edge(n1,n2);
  edge e2=G.new_edge(n2,n3); edge e3=G.new_edge(n3,n0);
  edge e4=G.new_edge(n0,n4); edge e5=G.new_edge(n3,n4);
  edge e6=G.new_edge(n1,n5); edge e7=G.new_edge(n2,n5);
  edge e8=G.new_edge(n4,n5);

  edge_array<int> weight(G);
  weight[e0]=4;  weight[e1]=4;  weight[e2]=4;
  weight[e3]=4;  weight[e4]=12; weight[e5]=12;
  weight[e6]=12; weight[e7]=12; weight[e8]=8;
 
  list<edge> M=MAX_WEIGHT_MATCHING(G,weight);

  std::cout << "Maximum Weighted Matching:" << std::endl;
  int weight_M=0;
  edge e;
  forall(e,M) {G.print_edge(e); weight_M+=weight[e];}
  std::cout << " weight: " << weight_M << std::endl;

  return 0;
}

See also:

Maximum Weighted Matching in General Graphs

Graphs

Parameterized Graphs

Linear Lists

Edge Arrays

Matching Algorithms

Manual Entries: