Bipartite Graph Matching

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Bipartite Graph Matching

Post by jan_holmes »

Is there anyone could give me an example how to code using Bipartite Graph Matching ??? Thx... :D

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha »

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.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes »

Would you please give me an example how to code it ??? thx... :)

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha »

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?

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

Post by asif_rahman0 »

Hi Moha,
Can you please tell what is alternative path theory??

help would be appreciated.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes »

Yes, Moha... Actually, I'm not very clear with the explanation... Please could you give me the source code of straight forward of a Bipartite Graph Matching problem ??? Thx

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS »

Hi Moha,
I got some ideas about alternative path theory.
But what is the time complexity of this approach? :-?
Could you explain more or offer some online references? :D
Thank you.
--
DJWS, a newbie in prgoramming :wink:

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha »

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 2-dimentional 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 non-matching 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]

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude »

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...

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;
}
    
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)
fahim
#include <smile.h>

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur »

To Moha -

Has so-called "Hungarian Method" something to do with the alternating path theory?

Thank you.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder »

I believe you either apply max-flow with BFS or hungarian algorithm or hopcroft-karp. the last is fastest. you can look up hungarian algorithm on google/wikipedia

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude »

thanks bugz,
I used dfs - Edmond Karp.. its not working anyway..
I suppose its the right way..

1. find an augmenting path
2. take the min residual.
3. del the min from all edge and maxflow+=min
4. loop to 1, until there is no augmenting path left

isnt it?
fahim
#include <smile.h>

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha »

Hi, the alternative path is same as augmenting. I call it alternative because for bipartite graph our path is alternative between the matched and not-matched 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 not-matched 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.
Has so-called "Hungarian Method" something to do with the alternating path theory?
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.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Moha 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 not-matched edge.
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 term :wink:

smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude »

thanks moha!
i corrected that error for my dfs code with putting a flag for checking.. (if a path is found it will quit everything), and turned to a TLE (!!) - may be there was something wrong.. but anyhow when i moved to bfs i got ac in 0.063 seconds.

thanks a lot buddy!
fahim
#include <smile.h>

Post Reply

Return to “Algorithms”