Example Maximum Cardinality Matching in Bipartite Graphs

The following program shows how the function MAX_CARD_BIPARTITE_MATCHING() can be used to compute a maximum cardinality matching and a node cover in a bipartite graph and 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 complete bipartite graph G=(A,B,E) with three nodes in A, two nodes in B, and six edges. We use a list<node> to store A and B. The result of MAX_CARD_BIPARTITE_MATCHING() is a list<edge> M containing the edges in the maximum cardinality matching and a node_array<bool> NC that is true for nodes in the node cover and false for the other nodes of G.

We use CHECK_MCB() to check if M is a maximum cardinality matching and NC is a maximum cardinality node cover of G. If the result is correct we output M and NC. The function writes diagnostic output to cerr, if the result is not correct.

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

using namespace leda;

int main()
{
  graph G; 

  node a0=G.new_node(), a1=G.new_node(), a2=G.new_node();
  list<node> A=G.all_nodes();
  
  node b0=G.new_node(), b1=G.new_node();
  list<node> B; B.append(b0); B.append(b1);
  
  G.new_edge(a0,b0); G.new_edge(a0,b1);
  G.new_edge(a1,b0); G.new_edge(a1,b1);
  G.new_edge(a2,b0); G.new_edge(a2,b1);
 
  node_array<bool> NC(G);
  list<edge> M=MAX_CARD_BIPARTITE_MATCHING(G,A,B,NC);

  bool result_correct=CHECK_MCB(G,M,NC);

  if (result_correct) {
    std::cout << "Matching: ";
    edge e; forall(e,M) G.print_edge(e);
    std::cout << std::endl << "Node Cover: ";
    std::node v; forall_nodes(v,G) if (NC[v]) G.print_node(v);
    std::cout << std::endl;
  }

  else std::cout << "M is not maximum cardinality matching!" 
                 << std::endl;
			
  return 0;
}

Remark: There are variants of MAX_CARD_BIPARTITE_MATCHING() that do not need the parameter node_array<bool> NC and variants without explicitely stating the bipartition of G as list<node> A, list<node> B. Have look at the Manual Page Maximum Cardinality Matching in Bipartite Graphs for details.

See also:

Maximum Cardinality Matching in Bipartite Graphs

Graphs

Parameterized Graphs

Linear Lists

Node Arrays

Matching Algorithms

Manual Entries: