JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Bipartite matching | Reply
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!
Re: Bipartite matching (response to post by Margarita) | Reply
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
 /    \
s-o  o-t
 \    / 
  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.
Re: Bipartite matching (response to post by Margarita) | Reply
You said it backwards. The reduction is from bipartite matching to maximum flow.
Re: Bipartite matching (response to post by artie) | Reply
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.
Re: Bipartite matching (response to post by Margarita) | Reply
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;
}
 
Re: Bipartite matching (response to post by artie) | Reply
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 non-directed 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).
Re: Bipartite matching (response to post by wack-a-mole) | Reply
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.
Re: Bipartite matching (response to post by tomek) | Reply
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).
Re: Bipartite matching (response to post by espr1t) | Reply
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.
Re: Bipartite matching (response to post by alastair.andrew) | Reply
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 wack-a-mole'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 max-flow with value 3. s is source, t is sink, saturate the edges s-0, 0-3, 3-t, s-1, 1-3, 3-2, 2-4, 4-t, s-2, 2-5, 5-t.

Note that this is not the standard max-flow reduction, where the capacity of 3-2 is 0, while here it's 1. The standard reduction is of course correct.
Re: Bipartite matching (response to post by tomek) | Reply
Oh, sorry, I didn't realize node 2 was on the same side with 0 and 1. It is a nice example :)
RSS