Example Maximum Cardinality Matching in General Graphs

The following program shows how the function MAX_CARD_MATCHING() can be used to compute a maximum cardinality matching and an odd set cover in a general graph and how the function CHECK_MAX_CARD_MATCHING() 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 graph G=(V,E) with six nodes and eight edges. The result of MAX_CARD_MATCHING() is a list<edge> M containing the edges in the maximum cardinality matching and a node_array<int> OSC that contains the labels of the nodes of G.

We use CHECK_MAX_CARD_MATCHING() to check if M is a maximum cardinality matching and OSC is an odd set cover of G. If the result is correct we output M and OSC. The function aborts, if the result is not correct.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/mc_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);
 
  node_array<int> OSC(G);
  list<edge> M=MAX_CARD_MATCHING(G,OSC);

  bool result_correct=CHECK_MAX_CARD_MATCHING(G,M,OSC);

  if (result_correct) {
    std::cout << "Maximum Cardinality Matching:" << std::endl;
    edge e;
    forall(e,M) G.print_edge(e);
    std::cout << std::endl;

    node v; forall_nodes(v,G) {
      std::cout << "label"; G.print_node(v);
      std::cout << "=" << OSC[v] << std::endl;
    }
  }
 
  return 0;
}

Remark: There is a variants of MAX_CARD_MATCHING() that does not need the parameter node_array<int> OSC.

See also:

Maximum Cardinality Matching in General Graphs

Graphs

Parameterized Graphs

Linear Lists

Node Arrays

Matching Algorithms

Manual Entries: