0

I try to implement ford fulkerson algorithm but i have problems at my_alg function.I think the reason for this problem is find_edge function.since when i find the edge and increment its flow(asker_sayisi),at the next line it seems to be incremented but at the next line when i find the same edge again i see that it is not incremented.I could not find the problem.Thanks for your help

#include <vector>
#include <stack>
#include <string>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <queue>

using namespace std;
#define min(x,y) (x)<(y)? (x):(y) ;
class Node;
class Graph;
class Edge;
int sinir,num_isl,num_bridges;
int head,tail;

//enum for the status of a node
enum Status {
NOT_VISITED,
VISITED,
IN_QUEUE
};

//forward declaration


//An object of this class represents an edge in the graph.
class Edge
{
        private:
        Node *orgNode;//the originating vertex
        Node *dstNode;//the destination vertex
        //Node *prev;
        public:
        unsigned bridge_capacity;//cost of the edge
        int asker_sayisi;
        public:
        Edge(Node *firstNode, Node *secNode, unsigned inCost)
        {
        orgNode = firstNode;
        dstNode = secNode;
        bridge_capacity = inCost;
        asker_sayisi=0;
        }
        Edge(){
            asker_sayisi=0;


            }

        Node* getDstNode()
        {
            return dstNode;
        }

        Node* getOrgNode()
        {
            return orgNode;
        }

        unsigned get_bridge_capacity()
        {
            return bridge_capacity;
        }
        void set_asker_sayisi(int a){
            asker_sayisi=a;

            }
};



//An object of this class holds a vertex of the graph
class Node
{
            private:
            string name;
            vector<Edge> adjNodeList;//list of outgoing edges for this vertex
            enum Status status;//used in dfs to mark the node visited
            int ada_capacity;

            int dst_toNest;
            public:
            Node *prev;
            vector<Node*>prevNodeList;
            public:
            Node(string id,int capacity)
            {
            name = id;
            status = NOT_VISITED;
            ada_capacity=capacity;
            }

            Node(string id)
            {
            name = id;
            status = NOT_VISITED;
            }

            //do not del the adj nodes here...they will be deleted by graph destructor
            ~Node()
            {
            adjNodeList.clear();
            }

            void add_prevNodeList(Node *prevNode){
                prevNodeList.push_back(prevNode);               

                }


            /*vector<Node*>& get_prevNodeList()
            {
            return prevNodeList;
            }*/ 


            enum Status getStatus()
            {
            return status;
            }

            void setStatus(enum Status st)
            {
            status = st;
            }

            string getName()
            {
            return name;
            }

            void setDesttoNest(int koy){


                dst_toNest=koy;

                }


            void incDesttoNest()
            {
            dst_toNest++;   
            }


            int getDsttoNest()
            {               
            return dst_toNest;  
            }

            int getCapacity(){

                return ada_capacity;
                }

            void addAdjNode(Node *adj, unsigned bridge_capacity)
            {
            //create an edge with 'this' as the originating node and adj as the destination node
            Edge newEdge(this, adj, bridge_capacity);
            adjNodeList.push_back(newEdge);
            }

            vector<Edge>& getAdjNodeList()
            {
            return adjNodeList;
            }

            //displays all adjacent verticies of this vertex
            void displayList()
            {
            string edgeOp = " -> " ;
            for(int i=0 ; i < adjNodeList.size() ; i++)
            {
            Edge edg = adjNodeList[i];
            //edg.asker_sayisi=0;
            cout << name << " -> " << edg.getDstNode()->getName() <<edg.get_bridge_capacity() << endl ;
            }

            }
};

class Graph
{
            public:
            vector<Node*> nodeList;//list of verticies
            bool foundCycle;//true if a cycle is found, false otherwise
            int desiredCycSize;

            void clearVisited() 
            {
            for(int i = 0; i < nodeList.size() && !foundCycle ; i++)
            {
            nodeList[i]->setStatus(NOT_VISITED);
            }
            }
            public:
            void addNewNode(Node *nNode)
            {
            nodeList.push_back(nNode);
            }
            private:
            Node* findNodeByName(string name)
            {
            for(int i = 0 ; i < nodeList.size() ; i++)
            {
            if(nodeList[i]->getName() == name)
            return nodeList[i];
            }
            return NULL;
            }

            public:
            Graph()
            {
            foundCycle = false;
            }

            ~Graph()
            {
            //free mem allocated to verticies
            for(int i=0 ; i < nodeList.size() ; i++)
            delete nodeList[i];
            nodeList.clear();
            }


            void displayGraph()
            {
            for(int i=0 ; i < nodeList.size() ; i++)
            {
            nodeList[i]->displayList(); 
            }
            }



};




int bfs(Graph *as,Node *nest,Node *island){


    queue <Node*> bf;
    for(int i=0;i<2*num_isl+2;i++){
        as->nodeList[i]->setStatus(NOT_VISITED);
        }

    nest->prev=NULL;
    bf.push(nest);
    nest->setStatus(IN_QUEUE);  

    while (!bf.empty()){
        Node *olurmu=bf.front();

        olurmu->setStatus(VISITED);
        bf.pop();

        vector <Edge> ls=olurmu->getAdjNodeList();
        for(int i=0;i<ls.size();i++){
                if(((ls[i].getDstNode())->getStatus())==NOT_VISITED&&(ls[i].get_bridge_capacity()-ls[i].asker_sayisi>0)){
                ls[i].getDstNode()->setStatus(IN_QUEUE);
                bf.push(ls[i].getDstNode());            
                ls[i].getDstNode()->prev=ls[i].getOrgNode();

                }

            }

        }
        return as->nodeList[num_isl]->getStatus()==VISITED;

 }


 Edge *find_edge(Graph *g,Node *from,Node *to){ 

            vector<Edge> b=from->getAdjNodeList();
            for(int i=0;i<b.size();i++){
                if(b[i].getDstNode()==to)
                return (&b[i]);
                }
            return NULL;

            }



int my_alg(Graph *as,Node *source,Node *sink){


    int max_flow=0;

    while(bfs(as,source,sink)){
        Node *b=as->nodeList[num_isl];
        int inc=100000000;
        while(b->prev!=NULL){
            Edge *bok=find_edge(as,b->prev,b);
            inc=min(inc,bok->get_bridge_capacity()-bok->asker_sayisi);
            b=b->prev;

            }
            b=as->nodeList[num_isl];

        while(b->prev!=NULL){
            Edge *bok=find_edge(as,b->prev,b);
            bok->asker_sayisi+=inc;
            cout<<bok->asker_sayisi<<endl;

            bok=find_edge(as,b->prev,b);
            cout<<bok;
            //cout<<bok->asker_sayisi;
            bok=find_edge(as,b->prev,b);
            cout<<bok<<endl;
            cout<<bok->asker_sayisi<<endl;
            /*bok->asker_sayisi-=inc;
            b=b->prev;*/
            } 
            break;
        max_flow+=inc;
//cout<<inc;
    }

return max_flow;
}

Edited by Dani: Formatting fixed

2
Contributors
1
Reply
3
Views
5 Years
Discussion Span
Last Post by Clinton Portis
0

i've actually looked up youtube videos to teach myself this somewhat complex topic... never actually studies flow systems. i got the basic concept and can do some simple examples.

i am down with your code, but i am not down with flow systems. if we put our heads together we might be able to come up with something. one thing that might help me out (if you are interested in doing so) would be to comment every line of code so I can see what your though process is.

Edited by Clinton Portis: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.