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:

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.Add a single node

`S`

with a directed edge from`S`

to every node in`M`

(this is your "super-source" node).Add a single node

`T`

with a directed edge from every node in`F`

to`T`

(this is your "super-sink" node).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

flowfrom`S`

to`T`

is a set of edges such that for each node (except`S`

and`T`

), the weight of itsin-fluxedges is the same as the weight of itsout-fluxedges. 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.