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;
}
