1

There is a line(cout << e.src) in the overloaded method for << that causes error. Removing that line causes the error. The error doesn't show any stacktrace. It just prints

Segmentation Fault(core dumped)

#include <queue>
#include<iostream>
using namespace std;


class Edge{
    public:
        int src, dest;
        int flow=0;
        int capacity;
        Edge* residual;

    Edge(int src, int dest, int capacity){
        this->src = src;
        this->dest = dest;
        this->capacity = capacity;
    }

    void augment(int bottleneck){
        int previousCapacity = this->getRemainingCapacity();
        cout<<"augmenting edge ("<<src<<"->"<<dest<<")chaging flow from "<<this->flow<<" to ";
        this->flow+=bottleneck;
        this->residual->flow-=bottleneck;       
        cout<<this->flow<<" and capacity from "<<previousCapacity<< " to "<<this->getRemainingCapacity()<<endl;

    }

    bool isResidual(){
        if (capacity==0){
            return true;
        }
        else{
            return false;
        }
    }

    int getRemainingCapacity(){
        return capacity - flow;
    }


    friend ostream& operator << (ostream& out, const Edge& e){
        out<<e.src; //THIS LINE CAUSES AN ERROR, FUNCTION WORKS PERFECT IF THIS LINE IS COMMENTED

        // Edge* ed = &e;
        // out<<e.src;
        // out<<"Edge("<<e.src<<"->"<<e.dest<<")| flow="<<e.flow<<"| capacity="<<e.capacity<<" | residual capacity = "<<e.getRemainingCapacity()<<endl;
        return out;
    }


};

class NetworkFlowSolverBase{
    public:
        int V;
        int source;
        int sink;
        vector<Edge*>* adj;

    NetworkFlowSolverBase(int source, int sink, int V){
        this->V = V;
        this->source = source;
        this->sink = sink;
        adj = new vector<Edge*>[V];
    }

    void addEdge(int source, int dest, int capacity){
        Edge* e1 = new Edge(source, dest, capacity);
        Edge* e2 = new Edge(dest, source, 0);

        e1->residual = e2;
        e2->residual = e1;

        adj[e1->src].push_back(e1);
        adj[e2->src].push_back(e2);
    }

    virtual void solve()=0;
};


class FordFulkersonBFSSolver: public NetworkFlowSolverBase{

    public:

    void bfs(int source,int sink, bool visited[], int parent){
        queue<pair<int, Edge*>> currentEdgeParentEdge;
        currentEdgeParentEdge.push({source, NULL});
        while(!currentEdgeParentEdge.empty()){
            pair<int, Edge*> top = currentEdgeParentEdge.front();
            cout<<*(top.second)<<endl;
            visited[top.first] = true;
            currentEdgeParentEdge.pop();
            for(vector<Edge*>::iterator it=adj[top.first].begin();it!=adj[top.first].end();it++){
                if (!visited[(*it)->dest]){
                    currentEdgeParentEdge.push({(*it)->dest, (*it)});
                }
            }
        }
    }

    void solve(){
        cout<<"ford"<<endl;
        bool visited[V]={false};
        bfs(source, sink, visited, -1);

    }

    FordFulkersonBFSSolver(int source, int sink, int V): NetworkFlowSolverBase(source, sink, V){

    }

};


int main()
{

    int n = 6;
    int s = 0;
    int t = n-1;

    FordFulkersonBFSSolver solver(s, t, n);

    //edges from source
    solver.addEdge(s, 1, 16);
    solver.addEdge(s, 2, 13);

    solver.addEdge(1, 2, 10);
    solver.addEdge(2, 1, 4);
    solver.addEdge(1, 3, 12);
    solver.addEdge(2, 4, 14);
    solver.addEdge(3, 2, 9);
    solver.addEdge(4, 3, 7);

    //edges to sink
    solver.addEdge(3, t, 20);
    solver.addEdge(4, t, 4);
    solver.solve();

    cout << "Hello World!" << endl;
    return 0;
}
Nimish Bansal
  • 1,719
  • 4
  • 20
  • 37

0 Answers0