# C++ – Bipartite Matching

algorithmc++graphmatching

How can I implement a bipartite matching algorithm (probably based on a max-flow algorithm) in C or C++ ?

To be specific, I have this input in a file:
(1,3)
(1,5)
(2,5)

(M,F) –> where M represents id of MALE and F is id of FEMALE.

I need to find the maximum number of matches and show matched couples.
Like:
matches: 1&3 , 2&5

I have read in some books I can base this problem on a "maximum flow in a network" algorithm, but I couldn't find any specific info other than the sentence "this problem can be solved by …. algorithm".
I have little knowledge about max-flow, and dont know how to implement it either…

#### Best Solution

Yes, bipartite matching can be reduced to maximum flow:

1. You're given sets of nodes `M` and `F`. Add a directed edge from a node `m` in `M` to a node `f` in `F` if you've got the pair `(m, f)` in your file.

2. Add a single node `S` with a directed edge from `S` to every node in `M` (this is your "super-source" node).

3. Add a single node `T` with a directed edge from every node in `F` to `T` (this is your "super-sink" node).

4. Now, you need to find the maximum flow (with all your edges of weight 1) from `S` to `T`.

So what the heck is maximum flow? A flow from `S` to `T` is a set of edges such that for each node (except `S` and `T`), the weight of its in-flux edges is the same as the weight of its out-flux edges. Imagine that your graph is a series of pipes, and you're pouring water in the system at `S` and letting it out at `T`. At every node in between, the amount of water going in has to be the same as the amount of water coming out.

Try to convince yourself that a flow corresponds to a matching of your original sets. (Given a flow, how to you get a matching? Given a matching, how to you get a flow?)

Finally, to find the maximum flow in a graph, you can use the Ford-Fulkerson algorithm. The above wikipedia page gives a good description of it, with pseudo-code.