Bipartite Graph Matching
Moderator: Board moderators

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
Bipartite Graph Matching
Is there anyone could give me an example how to code using Bipartite Graph Matching ??? Thx...
If you mean, how to code the BM, I use one dfs, i send the vertex number and the part that I am on it, i.e. 0 or 1 for Up and Down.
also I use 2 array, mark and match, match=j means that ith vertex in down is matched to jth vertex in the upper level. and mark=1 means that ith vertex in upper level is already matched. its code is very very little. less that 10 lines.
also I use 2 array, mark and match, match=j means that ith vertex in down is matched to jth vertex in the upper level. and mark=1 means that ith vertex in upper level is already matched. its code is very very little. less that 10 lines.

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
Do you know about alternative path theory? so if we search each vertex in the upper level, check if it is already matched or not? if it is not matched so select an edge and add this edge to the matching set, and go to the lower level, in this level you should select a matched edge, and go with it to the upper level. is it clear?

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
OK, For Matching the computational complexity is O(n^3) because you need at most 'n' dfs to find the maximum matching.
As I saied before, you should write a function (a dfs function) for finding the alternative path from a vertex, say V. according to bipartite graph we can save its adjcancy matrix with a 2dimentional matrix. for which mat[a] means that there is a connection between vertex a'th from upper part to vertex b'th in the lower part.
All we need in this section is to write a dfs function to find an alternative path in this graph. we should start our work from upper park(say a), then we should find a vertex in the lower part(say b). If and only if the edge(a,b) is not a member of our matching set. is there is no option here so that means there is no alternative path from this vertex 'a', so we search for another alternative path from vertext 'a'+1 in the upper part.
the main problem here arises to write the dfs function. I used to write it with a function with 2 parameters, one of them is V, which stands for the vertex number and the other is E which means where am I, for distinguationg between the parts.
So, I will go from an vertex 'a' in the upper part to a vertex 'b' in lower part if and only if the traversed edge is not a matching edge, alone the traversing I mark this edge as a matching edge. and in the lower part when i am in vertex 'b' I want to go to the upper part. but just with the matching edges. when I find an alternative path I switch all of the edge that I traversed, from matching to nonmatching and vice versa.
For those who want to write the matching algorithm for first time, I recommand them to write it with using the maximum flow. It is an easy implemantation.[/code]
As I saied before, you should write a function (a dfs function) for finding the alternative path from a vertex, say V. according to bipartite graph we can save its adjcancy matrix with a 2dimentional matrix. for which mat[a] means that there is a connection between vertex a'th from upper part to vertex b'th in the lower part.
All we need in this section is to write a dfs function to find an alternative path in this graph. we should start our work from upper park(say a), then we should find a vertex in the lower part(say b). If and only if the edge(a,b) is not a member of our matching set. is there is no option here so that means there is no alternative path from this vertex 'a', so we search for another alternative path from vertext 'a'+1 in the upper part.
the main problem here arises to write the dfs function. I used to write it with a function with 2 parameters, one of them is V, which stands for the vertex number and the other is E which means where am I, for distinguationg between the parts.
So, I will go from an vertex 'a' in the upper part to a vertex 'b' in lower part if and only if the traversed edge is not a matching edge, alone the traversing I mark this edge as a matching edge. and in the lower part when i am in vertex 'b' I want to go to the upper part. but just with the matching edges. when I find an alternative path I switch all of the edge that I traversed, from matching to nonmatching and vice versa.
For those who want to write the matching algorithm for first time, I recommand them to write it with using the maximum flow. It is an easy implemantation.[/code]
hi moha,
i tried to do the maxflow by this way, i guess i made a lot of error, or misunderstood few points. i felt quite hopeless, can you have a simple look.. you helped me alot previous days.. i'll be so grateful to you always..
what you called alternative path, i call them augmenting path, as they increment the value of maxflow...
anyway, this was 820, where both directions are there.
I know i was supposed to write at vol 8, but i guess i got to understand algorithms first...
(anyway, i had exam, so i became really irregular at the uva forum)
i tried to do the maxflow by this way, i guess i made a lot of error, or misunderstood few points. i felt quite hopeless, can you have a simple look.. you helped me alot previous days.. i'll be so grateful to you always..
what you called alternative path, i call them augmenting path, as they increment the value of maxflow...
Code: Select all
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int residue[105][105];
int parent[105];
bool entered[105];
int source, sink, connections;
int maxflow;
int n;
void dfs(int node) {
int temp;
int minm,i;
if(node==sink) {
temp=sink;
minm = 1000000;
//finding min
while(temp!=source) {
if(residue[temp][parent[temp]]<minm)
minm=residue[temp][parent[temp]];
temp=parent[temp];
}
maxflow+=minm;
//cutting my augmenting path
temp=sink;
while(temp!=source) {
residue[temp][parent[temp]]=minm;
residue[parent[temp]][temp]=minm;
temp=parent[temp];
}
return;
}
for(i=1;i<=n;i++) if(residue[node][i]>0 && !entered[i]) {
entered[i]=true;
parent[i]=node;
dfs(i);
entered[i]=false;
}
}
int main() {
int i,j;
int a,b,c;
int cases=0;
while(scanf("%d",&n)==1) {
if(!n) break;
maxflow=0;
memset(residue,0,sizeof(residue));
memset(entered,0,sizeof(entered));
for(i=0;i<connections;i++) {
if(residue[a][b]==0)
residue[a][b]=residue[b][a]=c;
else residue[a][b]=residue[b][a]=residue[a][b]+c;
}
parent[source]=0;
entered[source]=true;
dfs(source);
cout<<maxflow<<endl;
}
//system("pause");
return 0;
}
I know i was supposed to write at vol 8, but i guess i got to understand algorithms first...
(anyway, i had exam, so i became really irregular at the uva forum)
fahim
#include <smile.h>
#include <smile.h>

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm
Hi, the alternative path is same as augmenting. I call it alternative because for bipartite graph our path is alternative between the matched and notmatched edge.
Your algorithm is ok! But remember that you use dfs for finding the augmenting path. That may be slow your code. consider this graph:
v1 is connected to v2 with capacity 10000, and v1 is connected to v3 with 10000 and for v2 to v4 and v3 to v4. and there is a link between v2 and v3 with capacity 1. for example if you find this path:v1 v2 v3 v4, you can update the flow with 1. and if you find another path like: v1 v3 v2 v4, you can update the total flow with 2 and this process continues.
finding augmented path with dfs has this problem, but for matching problem, because all of our capacities are 1 we don't have this anymore.
You can use BFS for finding augmented path, in this case the order of algorithm dose not changed by value of capacities.
The algorithm that I propose for matching is very similar to finding maxflow in graph but in this case we know our graph is bipartite and for going to lower part we should take a notmatched edge and if we want to come back from lower part to upper part we should select a matched edge. Because all of capacities are 1.
Your algorithm is ok! But remember that you use dfs for finding the augmenting path. That may be slow your code. consider this graph:
v1 is connected to v2 with capacity 10000, and v1 is connected to v3 with 10000 and for v2 to v4 and v3 to v4. and there is a link between v2 and v3 with capacity 1. for example if you find this path:v1 v2 v3 v4, you can update the flow with 1. and if you find another path like: v1 v3 v2 v4, you can update the total flow with 2 and this process continues.
finding augmented path with dfs has this problem, but for matching problem, because all of our capacities are 1 we don't have this anymore.
You can use BFS for finding augmented path, in this case the order of algorithm dose not changed by value of capacities.
The algorithm that I propose for matching is very similar to finding maxflow in graph but in this case we know our graph is bipartite and for going to lower part we should take a notmatched edge and if we want to come back from lower part to upper part we should select a matched edge. Because all of capacities are 1.
Yes, as far as i remember, in that method we label the edge and with that labeling we use the ordinary matching. if that matching is a perfect one our job is done, otherwise we change the labels.Has socalled "Hungarian Method" something to do with the alternating path theory?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
I think the correct term is alternating path, not alternative path. I don't mean to be nitpicking; it's just that if you want to use google to search for the algorithm, you have to use the first termMoha wrote:Hi, the alternative path is same as augmenting. I call it alternative because for bipartite graph our path is alternative between the matched and notmatched edge.