5.3.5. Matching algorithms

Learning objectives

Algorithms from mcb_matching.h, mwb_matching.h, mc_matching.h, and mw_matching.h
The marriage problem
Weighted and unweighted, bipartite, and general matchings

In the marriage problem, ladies and gentlemen willing to marry stand vis-à-vis. Each lady may declare whom of the hopeful gentleman she would potentially marry. In general, not each gentleman appeals to each lady. Moreover, a certain surplus of ladies prevails by nature, at least on the marriage market, but not on the exchanges that are held in discotheques and similar locations; there, often a huge surplus of gentlemen prevails. Figure 5.25 shows an instance of such a problem.

Figure 5.25. The marriage problem

The marriage problem

8 ladies face 7 gentlemen in a bipartite graph. Certain pairs, but in general not not all, would celebrate a marriage. For each potential marriage, there is an edge in the graph. The marriage problem is to find a maximum matching in this graph, that is, a maximal subset M of the edges with the property that no two edges of M have a node in common. The edges drawn thick here show a maximum matching. The nodes (persons) with a thick border are matched (will be married), the other nodes are unmatched (will stay single).


The problem now is to marry as many ladies as possible such that each lady gets a gentleman of her choice and that, of course, no two ladies are married to the same gentleman. It is understood that the problem may also be formulated vice-versa, from the gentlemen's viewpoint; but as it is in nature's nature, it is unfortunately the ladies that take the choice, not vice-versa. So mating as many ladies as possible is tantamount to mating as many gentlemen as possible. Therefore, we may introduce a little justice and formulate the problem such that each pair consisting of a lady and a gentleman may tell whether they want to marry or not. So the graph that underlies the problem is undirected; the direction of the edges is irrelevant.

An abstract formulation of the problem is the following: A matching in a graph is set M of edges with no no two edges having a node in common. A maximum matching is a maximal set with this property. A maximum matching always exists; it does not have to be unique, however. Not all nodes have to be matched in a maximum matching, see Figure 5.25; if indeed all nodes are matched, the matching is called perfect.

This abstract problem definition has many concrete manifestations. Another formulation is the assignment problem: On the job market, a set of workers faces a set of open jobs, but not each worker is appropriate for each job, and each worker may fill at most one vacancy. As many workers as possible are to be engaged according to their capabilities; conversely, as many vacancies as possible are to be filled.

Maximum bipartite, unweighted matchings

The (heterosexual) marriage problem is to find a maximum matching in a bipartite graph. Often the marriage problem is specified more precisely as the problem of finding a maximum bipartite, unweighted matching. Here “bipartite” stands for the fact that the underlying graph is bipartite, “unweighted” stands for the fact that the edges are not labeled with weights, that is, that the pairs do not specify how much an accomplished marriage would be worth to them. A synonym is maximum bipartite cardinality matching.

LEDA offers some functions for computing maximum bipartite matchings. All these functions are declared in the header file mcb_matching.h.

The function

list<edge> MAX_CARD_BIPARTITE_MATCHING(graph& G);

computes a maximum bipartite cardinality matching in a graph G. Precondition is that G indeed is bipartite. The function returns a list of the edges that form a maximum matching.

To clarify the usage of this function, we list the program that has been used to create Figure 5.25. With this program the user can edit a graph in a GraphWin; each time done is pressed, a maximum matching is drawn, and the pairings of the matching are printed.

Filename: MarriageProblem.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#include <LEDA/mcb_matching.h>
#include <LEDA/basic_graph_alg.h>
#include <LEDA/graph.h>
#include <LEDA/graphwin.h>
#include <LEDA/list.h>
#include <LEDA/string.h>
#include <iostream>

using leda::GRAPH;
using leda::edge;
using leda::node;
using leda::GraphWin;
using leda::window;
using leda::list;
using leda::string;
using std::cout;


int main()
{
  GRAPH<string,int> G;

  GraphWin gw(G, 500, 700, "Marriage Problem");
  gw.set_node_shape(leda::rectangle_node);
  gw.set_node_label_type(leda::data_label);
  gw.set_node_width(100);
  gw.set_edge_direction(leda::undirected_edge);
  gw.set_flush(false);
  gw.display(window::center,window::center);

  while(gw.edit()) {

    if(!Is_Bipartite(G)) {
      gw.message("This graph is not bipartite! Click <done>.");
      gw.wait();
      gw.del_message();
      continue;
    }

    list<edge>  L = MAX_CARD_BIPARTITE_MATCHING(G);

    // max. matching may have changed, so reset drawing to initial values
    gw.set_edge_width(1);
    gw.set_edge_color(leda::black);
    gw.set_node_border_color(leda::black);
    gw.set_node_border_width(1);
    
    

    gw.set_width(L, 3);
    gw.set_color(L, leda::red);

    cout << "\nThe following is a maximum cardinality matching:\n";
    edge e;
    forall(e, L) {
      node person1 = G.source(e);
      node person2 = G.target(e);
      cout << G.inf(person1) << " marries " << G.inf(person2) << "\n";
      gw.set_border_color(person1, leda::red);
      gw.set_border_color(person2, leda::red);
      gw.set_border_width(person1, 3);
      gw.set_border_width(person2, 3);
    }

    gw.redraw();
  }
    
}

The program outputs the following:

The following is a maximum cardinality matching:
Claudia marries Michael
Bettina marries Bernd
Roxane marries Wolfram
Sibylle marries Volker
Sabine marries Joerg
Marion marries Uwe

Honey, I bet // that you gonna get // your man before you die” (Rolling Stones.)

Maximum bipartite, weighted matchings

If, in the marriage problem, each pair additionally may specify how much an accomplished marriage would be worth to it, the edges in the underlying graph carry weights. (Another view is the one of a marriage agency that obtains a certain amount of money for each accomplished marriage.)

Then the problem is to find a matching in which the sum of the edge weights of the matching is maximal. (Then the marriage agency makes as much money as possible out of the matching.) This is called a maximum bipartite, weighted matching.

LEDA keeps ready some functions for this; they all are declared in the header file mwb_matching.h. For example,

list<edge> MAX_WEIGHT_BIPARTITE_MATCHING(graph& G, edge_array<int> weight);

computes a maximum bipartite, weighted matching on the graph G. Here the weights of the edges are given by the edge array weight. G must be bipartite.

Maximum general, unweighted matchings.

Since the sexual revolution in the 60s, bipartite graphs go more and more out of fashion for representing marriage problems. Today we live in a society that admits also same-sex marriages. This means for the underlying graph that now the edges do not exhibit a strict separation of their nodes into female and male ones any more; in fact, it may be any graph. The nodes in it have just one sex only or are to be regarded as sexless; everyone may gallivant with everyone, ladies with ladies, ladies with gentlemen, and gentlemen with gentlemen.

This sexually neutral marriage problem, which has an arbitrary graph underlying, is called the problem to find a maximum general, unweighted matching. A synonym for this is maximum general cardinality matching.

LEDA offers some functions for this; they all are declared in the header file mc_matching.h. For example,

list<edge>  MAX_CARD_MATCHING(graph& G);

computes a maximum general cardinality matching on the graph G.

Maximum general, weighted matchings

The most general case, which includes the previously described cases, is the one of an arbitrary graph whose edges are provided with weights. Here a matching that maximizes the sum of the edge weights of the matching edges is called a maximum general, weighted matching. Figure 5.26 shows such a matching.

Figure 5.26. A maximum general, weighted matching

A maximum general, weighted matching

Marriages are allowed between persons of arbitrary sex. Each pair specifies how much an accomplished marriage would be worth to it.


Formulated as a marriage problem, both heterosexual and homosexual marriages are allowed here (in other words, the separation into two sexes is not made at all), and each pair specifies how much an accomplished marriage would be worth to it.

Also for this problem, LEDA offers some functions, which all are declared in the header file mw_matching.h. For example,

list<edge> MAX_WEIGHT_MATCHING(graph& G, edge_array<int> weight);

computes a general, weighted matching on the graph G. Here the weights of the edges are given by the edge array weight; they all have to be non-negative.

All functions from mw_matching.h have the precondition that the underlying graph be connected and simple and have neither self-loops nor reverse edges.

To clarify the usage of the function MAX_WEIGHT_MATCHING(), we list the program that has been used to create Figure 5.26. With this program, the user can edit a graph in a GraphWin; each time done is pressed, a maximum matching is drawn, and the pairings of the matching are printed.

Filename: MaximumGeneralWeightedMatching.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
#include <LEDA/mw_matching.h>
#include <LEDA/graph.h>
#include <LEDA/edge_array.h>
#include <LEDA/graphwin.h>
#include <LEDA/list.h>
#include <LEDA/string.h>
#include <iostream>


using leda::GRAPH;
using leda::edge_array;
using leda::edge;
using leda::node;
using leda::GraphWin;
using leda::window;
using leda::list;
using leda::string;
using std::cout;


int main()
{
  GRAPH<string,int> G;

  GraphWin gw(G, 500, 700, "Maximum General Weighted Matching");
  gw.set_node_shape(leda::rectangle_node);
  gw.set_node_label_type(leda::data_label);
  gw.set_node_width(100);
  gw.set_edge_direction(leda::undirected_edge);
  gw.set_edge_label_type(leda::data_label);
  gw.set_flush(false);
  gw.display(window::center,window::center);

  while(gw.edit()) {

    edge_array<int> weight(G);

    edge e;
    forall_edges(e,G)
      weight[e] = G.inf(e);

    list<edge> L = MAX_WEIGHT_MATCHING(G, weight);


    // max. matching may have changed, so reset drawing to initial values
    gw.set_edge_width(1);
    gw.set_edge_color(leda::black);
    gw.set_node_border_color(leda::black);
    gw.set_node_border_width(1);
    
    

    gw.set_width(L, 3);
    gw.set_color(L, leda::red);

    cout << "\nThe following is a maximum weighted matching:\n";
    int weight_of_matching = 0 ;
    forall(e, L) {
      weight_of_matching += weight[e];
      node person1 = G.source(e);
      node person2 = G.target(e);
      cout << G.inf(person1) << " marries " << G.inf(person2) << "\n";
      gw.set_border_color(person1, leda::red);
      gw.set_border_color(person2, leda::red);
      gw.set_border_width(person1, 3);
      gw.set_border_width(person2, 3);
    }

    cout << "The weight of this matching is " << weight_of_matching;
    cout << "\n";

    gw.redraw();
  }
    
}

The output of the program for the graph from Figure 5.26 is:

The following is a maximum weighted matching:
Anja marries Mick
Ulli marries Keith
Charlie marries August
Brian marries Bill
Claudia marries Herbert
Bettina marries Sibylle
Stefan marries Klaus
Heinz marries Robert
The weight of this matching is 144

Running times and further information

Of course, one always gets along with the functions from mw_matching.h, which handle the most general case and thus include all other cases. (For example, to compute a maximum cardinality matching with one of these functions, all edge weights could be set to 1.) The functions presented here strongly differ by their running times, though. The more special the case is that they handle, the faster are their implementations.

MAX_WEIGHT_MATCHING() takes time O(n·m·log(n)), MAX_CARD_MATCHING() only O(n·m·a(n,m)), with a() being the inverse Ackermann function, a function that is so small even for extremely large n and m that, in practice, it may be regarded as constant.

MAX_WEIGHT_BIPARTITE_MATCHING() takes time O(n·(m+n·log(n))). The running time of MAX_CARD_BIPARTITE_MATCHING() is O(sqrt(n)·m) in the worst case; for a random graph, its expected running time is O(m·log(n)).

More information about these functions can be found on the corresponding manual pages of mcb_matching.h, mwb_matching.h, mc_matching.h, and mw_matching.h.

These pages also describe functions for computing a perfect matching in a graph (if there is one).

Exercises

Exercise 67.

Extend the program such that, in addition, the unmatched nodes are colorized in the GraphWin and printed to standard output.




Imprint-Dataprotection