Bipartite Graph Matching

[jan_holmes]

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

[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]

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

[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]

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

help would be appreciated.

[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]

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?
Thank you.
--
DJWS, a newbie in prgoramming

[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]

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)

[serur]

To Moha -

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

Thank you.

[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]

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?

[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]

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

[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!