Example Weighted Perfect Matching

The following program shows how the functions MAX_WEIGHT_PERFECT_MATCHING() and MIN_WEIGHT_PERFECT_MATCHING()can be used to compute a maximum, respectively minimum, weighted perfect matching. 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 MIN_WEIGHT_PERFECT MATCHING() and MAX_WEIGHT_PERFECT MATCHING() is a list<edge> containing the edges in the minimum, respectively maximum, weighted perfect 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_min=MIN_WEIGHT_PERFECT_MATCHING(G,weight);

  std::cout << "Minimum Weighted Perfect Matching:" << std::endl;
  int weight_M_min=0;
  edge e;
  forall(e,M_min) {G.print_edge(e); weight_M_min+=weight[e];}
  std::cout << " weight: " << weight_M_min << std::endl;
  
  list<edge> M_max=MAX_WEIGHT_PERFECT_MATCHING(G,weight);

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

  return 0;
}

See also:

Weighted Perfect Matching in General Graphs

Graphs

Parameterized Graphs

Linear Lists

Edge Arrays

Matching Algorithms

Manual Entries: