Skip to main content

Basic Maxflow or Network Flow source code in c++

When there is one source and one sink and prospect is that to send maximum unit to sink then comes the need of maxflow.It is normally a bfs which helps to find the maximum capacity  over the line load and reduce this capacity from load until the load comes to zero.I mean until there is any path from source to sink.

Here is the code for maxflow.Hope it help. 


#include<cstdio>

#include<cmath>

#include<cstring>

#include<string>

#include<iostream>

#include<queue>

#include<algorithm>

using namespace std;

#define INF  2147483647





/***************** Max Flow Algorithm***************

****************************************************/

const int maxINDX=102;

int flow[maxINDX][maxINDX],cap[maxINDX][maxINDX];

int path[maxINDX];

int src,dest;



int BFS(int node) {

    int i,item,cf;

    queue<int> q;

    for(i=1;i<=node;i++)

        path[i]=-2;// color it

    q.push(src);

    path[src]=-1;

    while(!q.empty()) {

        item=q.front();

        q.pop();

        if(item==dest) {

            i=dest;

            cf=INF;

            while(path[i]!=-1) {

                if(cf>flow[path[i]][i])

                    cf=flow[path[i]][i];

                i=path[i];

            }

            return cf;

        }

        for(i=1;i<=node;i++) {

            if(flow[item][i]!=0 && path[i]==-2) {

                q.push(i);

                path[i]=item;

            }

        }

    } // end of while loop

    return 0;

}



int maxflow(int node) {

    int i,j,cf,totalflow=0;

    while((cf=BFS(node))!=0) {

        totalflow+=cf;

        i=dest;

        while(path[i]!=-1) {

            flow[path[i]][i]-=cf;

            flow[i][path[i]]+=cf;

            i=path[i];

            cout <<i<<" ->"; // for available pathS

        }

        cout << endl;

    }

    return totalflow;

}



void graph_initial(int node){

    int i,j;

    for(i=1;i<=node;i++){

        for(j=1;j<=node;j++) {

            cap[i][j]=0;

            flow[i][j]=0;

        }

    }



}



int main()

{





    int node,edge,a,b,c,i,resultedFlow,j;



    while(scanf("%d",&node)==1 && node!=0) {



        graph_initial(node);



        scanf("%d %d",&src,&dest);

        scanf("%d",&edge);



        for(i=1;i<=edge;i++) {

            scanf("%d %d %d",&a,&b,&c);

            cap[a][b]+=c;

            cap[b][a]+=c;

            flow[a][b]+=c;

            flow[b][a]+=c; // For BI-Directed Graph

        }



        resultedFlow=maxflow(node);



        printf("%d\n",resultedFlow);



    /*    for(i=1;i<=node;i++)

        for(j=1;j<=node;j++)

        cout << i<<","<<j<<":"<<flow[i][j] <<" "<<i<<":"<<path[i]<<endl;*/

    }



return 0;

}



/*

7

1 7 8

1 2 3

2 4 3

3 4 5

1 3 1

4 7 2

3 5 4

5 6 2

6 7 3

*/

Comments

Popular posts from this blog

UDP server client in c

Server #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <arpa/inet.h> #include <stdio.h> #include <unistd.h> #include <errno.h> #include <string.h> #include <stdlib.h> int main() {         int sock;         int addr_len, bytes_read;         char recv_data[1024],send_data[1024];         struct sockaddr_in server_addr , client_addr;         if ((sock = socket(AF_INET, SOCK_DGRAM, 0)) == -1) {             perror("Socket");             exit(1);         }         server_addr.sin_family = AF_INET;         server_addr.sin...

[ASTERIK] configure: error: *** uuid support not found (this typically means the uuid development package is missing)

ISSUE: Build error on Asterik , when you want test webrtc feature :) checking for uuid_generate_random in -luuid... no checking for uuid_generate_random in -le2fs-uuid... no checking for uuid_generate_random... no configure: error: *** uuid support not found (this typically means the uuid development package is missing) Fix: This issue arises due to missing of UUID generator specified by rfc4122 . +Linux sudo apt-get install uuid-dev  @Unix yum -y install libuuid-devel Asterik comes with lots of helpful script available on - asterisk/contrib/scripts/ folder of your ASTERIK source. So just use the following command on UNIX console to run the asterik pre-requisite script. contrib/scripts/install_prereq install And you are done! configuring. Now -- Make Asterik.

Video Conferencing Project in Java Source Code

My video conferencing project was completed as 300 project for 3rd year.It is not totally completed. There is some bug in here.To solve these bugs and to help other students this project is open.It is first try to make a project open source in this way so it can be modified.Any kind of question against this project will be answered. As this project was created in 3rd year 1st semester and now i nearly completed my BSc. so there will be little description about this.I will try to describe every class and function later when i get the chance.   For more details and how to build and run go to this link   in github.com . Latest code and binary release : VideoConference-v1.1 Older code and binary release : VideoConference-v1.0 Fix: 1. When in Video chat the Text chat option hanged for good. ################################################################################# FEATURE #############################################################################...