

Can anyone please explain, how we can reduce standard maximum flow inmplementation to bipartite matching? What info is stored for each vertice? It would be great to see pseudocode or real code... Thanks! 

Here is bipartite graph:
o o
o o
o o
Now build new graph. Building of it is simple we just add source and sink and connect every vertex from first part to source and every vertex from second part to sink.
o o
/ \
so ot
\ /
o o
We connect tho vertices (u, v) with edge with capacity equal to 1 if there is an edge between them in original graph. Capacities of all edges going from source and to sink is also 1.
Value of maximal flow in such graph is equal to value of maximal matching. Restoring matching is simple: all saturated edges between parts belong to matching. 

You said it backwards. The reduction is from bipartite matching to maximum flow. 

Sorry, it seems you misunderstood me. When we have to solve bipartite matching problem, we use max flow approach. How can we simplify our code for max flow method to work it faster when searching for bipartite matching? That's my question. There is paragraph of text in the article dedicated to this, but I failed to understand it. 

I haven't even tried to compile this code...but something like this should work:
int adj[N][M]; // bipartition with N vertices on left, M on right
int seen[N], prev[M];
bool dfs(int x) {
if (x == 1) return 1;
if (seen[x]) return 0;
seen[x] = 1;
for (int i = 0; i < M; ++i)
if (adj[x][i] && dfs(prev[i])) {
prev[i] = x;
return 1;
}
return 0;
}
int maxflow() {
memset(prev, 1, sizeof(prev));
int flow = 0;
for (int i = 0; i < N; ++i) {
memset(seen, 0, sizeof(seen));
if (dfs(i))
++flow;
}
return flow;
}


I have a question about the algorithm. We connect a vertex from one to set to the other with capacity 1, using a directed edge.
If we use a nondirected edge, will the algorithm still find the correct answer?
In other words, if (capacity[i][j] = 1) > (capacity[j][i] = 1), then the idea remains correct?
All examples I've tried seem to work either if you use directed edges or not directed (Assuming the edges that go from source to vertices in one set and edges that go from vertices in the other set to the sink all have capacity 1). 

No, this algorithm will fail. Example graph: {(0,3),(1,3),(2,3),(2,4),(2,5)}. The maximum matching is 2, your modified algorithm will return 3. 

I don't get your example. Which nodes do you match? As I drew it on paper it seems there is a single edge in the middle of the graph, which his algorithm will catch. Anyway, I can't find a matching with weight 2, not to mention 3 (assuming node 0 is source and node 5 is sink). 

Hi espr1t,
I had a look at this configuration yesterday and it seemed to work properly, the max flow was only 2.
The description is kind of confusing {(0,3),(1,3),(2,3),(2,4),(2,5)} but it basically falls into two sets of nodes, the left hand side is {0,1,2} and the right hand side is {3,4,5}. If you use the Graphviz syntax it would look like this:
digraph matching {
0 > 3
1 > 3
2 > 3
2 > 4
2 > 5
}
You still need to connect the source and sink nodes before finding the matching as a Max Flow. 

I had a look at this configuration yesterday and it seemed to work properly, the max flow was only 2.
The maximum matching is only 2, while the max flow in wackamole's network is 3, thus proving the reduction he was asking about incorrect.
To clarify my example: I gave an instance of a maximum matching problem, giving the set of edges for the graph. The edges are undirected, so I really should have said: {{0,3},{1,3},{2,3},{2,4},{2,5}}. The maximum matching is 2, for example {{0,3}, {2,4}} is a matching.
Edit: Here is the maxflow with value 3. s is source, t is sink, saturate the edges s0, 03, 3t, s1, 13, 32, 24, 4t, s2, 25, 5t.
Note that this is not the standard maxflow reduction, where the capacity of 32 is 0, while here it's 1. The standard reduction is of course correct. 

Oh, sorry, I didn't realize node 2 was on the same side with 0 and 1. It is a nice example :) 
