Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Max flow problem

  1. Nov 4, 2011 #1
    i have following code
    Code (Text):

    #include<iostream>
    #define MAX 100
    using namespace std;
    int graph[MAX][MAX];
    int queue[MAX];
    int head,tail;
    int parent[MAX];
    int V,E;
    int s,t,fTotal;
    int F[MAX][MAX];

    //breadth First search
    bool reachable(int s,int  t){
        bool found=false;
        head=tail=0;
        int vq;
        memset(parent,255,sizeof(parent));
        queue[tail++]=s;
        parent[s]=s;
        while(head< tail && ! found){
            vq=queue[head++];
            for(int i=0;i<V;i++){
                //Parents also made the function as visit vector
                if(graph[vq][i] && parent[i]==-1)
                    queue[tail++]=i;
                parent[i]=vq;
                if(i==t){
                    found=true;
                    break;
                }
            }
        }
        return found;
    }

    void maxflow(){
        int vj,min;
        fTotal=0;
        while(reachable(s,t)){
            //Gets the minimum possible capacity in edges of the path s to t
            min=graph[parent[t]][t];
            vj=t;
            while(parent[vj]!=vj){
                if(graph[parent[vj]][vj]<min)
                    min=graph[parent[vj]][vj];
                vj=parent[vj];
            }

            vj=t;
            while(parent[vj]!=vj){

                graph[parent[vj]][vj]-=min;
                graph[vj][parent[vj]]+=min;
                F[parent[vj]][vj]+=min;
                vj=parent[vj];
            }
            fTotal+=min;
        }
    }

    bool read(){
        cin>>V>>E>>s>>t;
        if(!V && !E) return false;
        memset(graph,0,sizeof(graph));
        memset(queue,0,sizeof(queue));
        memset(F,0,sizeof(F));
        int v1,v2,val;
        for(int i=0;i<E;i++){
            cin>>v1>>v2>>val;
            graph[v1][v2]=val;
        }
        return true;
    }

    int  main(){
        while(read()){
            maxflow();
            cout<<" max flow from s to t is : "<<fTotal<<endl;
        }
        return 0;
    }
    which for this input

    (1,2) 2
    (1,3) 3
    (2,4) 3
    (3,4) 1
    (2,5) 1
    (3,5) 1
    (4,6) 2
    (5,6) 3
    returns zero as output,please tell me what is wrong?
     
    Last edited by a moderator: Nov 4, 2011
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted



Similar Discussions: Max flow problem
  1. Traffic flow (Replies: 2)

Loading...