Finding the maximum cardinality matching in a bipartite graph

This is kind of part 14 of the series about: How to build a Constraint Programming solver?
But it is also interesting for you if you don’t care about constraint programming.
In this post you’ll learn about bipartite graphs and matchings.

Anyway these are the other posts so far in the ongoing series:

All of that can only happen because of the generous support of some people.
I’m very happy that I can cover my server expenses now because of my Patrons.
To keep this going please consider supporting this blog on Patreon. If you do I will create a better/faster blog experience soon and you will get posts like this earlier!

If you want to just keep reading -> Here you go 😉

Last time I realized that the library I’m using doesn’t implement the easy algorithm I need which is bipartite maximum cardinality matching instead of bipartite maximum matching. This means they are solving a harder problem which I don’t have 😀

Additionally I like coding things from scratch so using a library is not the best choice but I am of course also limited in the amount of time I have and if people built it before it is often a good practice to not reinvent the wheel. Nevertheless this is a learning project where it is often good to know how a wheel works from the ground up.

The problem

We want to know whether a setting of numbers and possibilities in an all_different constraint is satisfiable or not.

For example we have 3 cells we want to fill with the numbers 1-3 and each should be used exactly once.

In the following examples our values are always at the top and the variables at the bottom. The goal is to match our variables to the values such that the all different constraint is satisfied. In this example there is no such matching:

Bipartite maximum cardinality smaller than #values

In a more precise definition a matching is a set of edges such that two edges don’t share the same vertex: Each vertex has at most one matching edge connected to it.

We are always interested in a matching which uses the most edges (maximum cardinality matching).

This is for example a matching (blue edges):

Small matching

We need this maximum cardinality matching to check whether it is possible to fulfill the constraint and later to also remove edges which would make it impossible when used (explained in the all different section).

How can we find those matchings?

Let’s have a look at a slightly bigger example:

Bipartite graph

I should mention that these graphs are called bipartite graphs as they have two…