Input error in C++ and segmentation fault

Question

I have the code gom.cpp

#include "another.cpp"
#include <iostream>
#include <vector>
#include <assert.h>

using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
bool same[MAXV];
int s;
const int INF = 0;
#define rep(i,a,b) for (__typeof(a) i=(a); i<(b); ++i)


template <class T>
void assert_equal(T expected, T actual, bool kill = false) {
    if (!(expected == actual)) {
        cout << "Assertion failed:" << endl;
        cout << "Expected: " << expected << endl;
        cout << "  Actual: " << actual << endl;
        if (kill) assert(false);
    }
}


pair<vii, vvi> construct_gh_tree(flow_network &g) {
    int n = g.n;
    int v;
    vii par(n, ii(0, 0));
    vvi cap(n, vi(n, -1));
    rep(s,1,n) {
        int l = 0, r = 0;
        par[s].second = g.max_flow(s, par[s].first, false);
        memset(d, 0, n * sizeof(int));
        memset(same, 0, n * sizeof(int));
        d[q[r++] = s] = 1;
        while (l < r) {
            same[v = q[l++]] = true;
            for (int i = g.head[v]; i != -1; i = g.e[i].nxt)
                if (g.e[i].cap > 0 && d[g.e[i].v] == 0)
                    d[q[r++] = g.e[i].v] = 1;
        }
        rep(i,s+1,n)
            if (par[i].first == par[s].first && same[i]) par[i].first = s;
        g.reset();
    }
    rep(i,0,n) {
        int mn = INF, cur = i;
        while (true) {
            cap[cur][i] = mn;
            if (cur == 0) break;
            mn = min(mn, par[cur].second), cur = par[cur].first;
        }
    }
    return make_pair(par, cap);
}
int compute_max_flow(int s, int t, const pair<vii, vvi> &gh) {
    if (s == t) return 0;
    int cur = INF, at1 = s;
    while (gh.second[at1][t] == -1)
        cur = min(cur, gh.first[at1].second), at1 = gh.first[at1].first;
    return min(cur, gh.second[at1][t]);
}

void test() {
    int N,M,source,sink,cap;
    cout<<"Enter the vertices and edges";
    cin>>N>>M;


    flow_network g(N);
    pair<vii, vvi> gh;

cout<<"Now enter the edges and their capacity";
    for(int i=0; i < M; i++) {
            cin>>source;
            cin>>sink;
            cin>>cap;
        g.add_edge(source, sink, cap, cap);
        assert_equal(g.max_flow(source, sink), compute_max_flow(source, sink, gh));
    }
gh = construct_gh_tree(g);
for(int i = 0; i < N; ++i) {
    for(int j = 0; j < N; ++j) {
        assert_equal(g.max_flow(i, j), compute_max_flow(i, j, gh));
    }
}
}


int main()
{
    test();
    return 0;
}

Also, another.cpp

#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

#define MAXV 2000

int q[MAXV], d[MAXV];

struct flow_network {
    struct edge {
        int v, cap, nxt;
        edge() { }
        edge(int _v, int _cap, int _nxt) : v(_v), cap(_cap), nxt(_nxt) { }
    };
    int n, ecnt, ecnt1, *head, *curh;
    vector<edge> e, e_store;
    flow_network(int _n, int m = -1) : n(_n), ecnt(0) {
        e.reserve(2 * (m == -1 ? n : m));
        head = new int[n], curh = new int[n];
        memset(head, -1, n * sizeof(int));
    }
    void destroy() { delete[] head; delete[] curh; }

    void reset() { e = e_store; }

    void add_edge(int u, int v, int uv, int vu = 0) {
        e.push_back(edge(v, uv, head[u]));
        head[u] = ecnt++;
        e.push_back(edge(u, vu, head[v]));
        head[v] = ecnt++;
        //cout<<ecnt;
    }
    int augment(int v, int t, int f) {
        if (v == t) return f;
        for (int &i = curh[v], ret; i != -1; i = e[i].nxt)
            if (e[i].cap > 0 && d[e[i].v] + 1 == d[v])
                if ((ret = augment(e[i].v, t, min(f, e[i].cap))) > 0)
                    return (e[i].cap -= ret, e[i^1].cap += ret, ret);
        return 0;
    }
    int max_flow(int s, int t, bool res = true) {
        if(s == t) return 0;
        e_store = e;
        int f = 0, x, l, r;
        while (true) {
            memset(d, -1, n * sizeof(int));
            l = r = 0, d[q[r++] = t] = 0;
            while (l < r)
                for (int v = q[l++], i = head[v]; i != -1; i = e[i].nxt)
                    if (e[i^1].cap > 0 && d[e[i].v] == -1)
                        d[q[r++] = e[i].v] = d[v]+1;
            if (d[s] == -1) break;
            memcpy(curh, head, n * sizeof(int));
            while ((x = augment(s, t, 0)) != 0) f += x;
        }
        if (res) reset();
        return f;
    }
};

When I compile the code and run it, the input doesn't stop. What could be the error? basically, I am trying to compile the gom.cpp file, run the test and finally display the results. Also, I am not able to display the results.

The input is as follows:

6 8 -> vertices and edges
0 1 2 -> edge from 0-1 with capacity 2
and so on -> 8 edges present.

I am getting segmentation fault on the input.

Answer 1

I entered "6 8" to the first prompt and "0 1 2" to the 2nd. It's in an infinite loop in max_flow(). In particular, this line

    if (d[s] == -1) break;

never breaks. In my example, s is the 0 input to the 2nd prompt.

Here's the line that would assign d[s]:

    d[q[r++] = e[i].v] = d[v]+1;

I got as far as determining that d[0] is assigned 1 and that never changes.

Answer 2

You are getting a segmentation fault at this line: gh.second[at1][t] in gom.cpp because gh is never initialized.

I imagine you mean to put g.add_edge(source, sink, cap, cap); before compute_max_flow(source, sink, gh) is called.

Here are some hints to help you out...

1. You should never include a .cpp file. Only include .h(header) files. Put the declarations in a header files and the definitions in the .cpp.
2. Simple cout statements can tell you where your segmentation fault occurred.
3. Always explicitly use parenthesis to mark the beginning and end of code blocks.

GOOD:

int x =1;
if(x==1)
{
  std::cout<<"x is 1"<<std::endl;
}
else
{
  std::cout<<"x is not 1"<<std::endl;
}

BAD HABIT:

int x=1;
if(x==1)
  std::cout<<"x is 1"<<std::endl;
else
  std::cout<<"x is not 1"<<std::endl;

4. Use gdb to debug issues with your code:

GDB is program that helps you debug issues with your c/c++ programs. To run your program in gdb, just type gdb <your_program>

Running this program in gdb I got a SIGSEGV:

Program received signal SIGSEGV, Segmentation fault.
0x00000000004029a8 in std::vector<int, std::allocator<int> >::operator[](unsigned long) const ()
Missing separate debuginfos, use: debuginfo-install glibc-2.16-34.fc18.x86_64 libgcc-4.7.2-8.fc18.x86_64 libstdc++-4.7.2-8.fc18.x86_64
(gdb) bt
#0  0x00000000004029a8 in std::vector<int, std::allocator<int> >::operator[](unsigned long) const ()
#1  0x0000000000401488 in compute_max_flow(int, int, std::pair<std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > > const&) ()
#2  0x00000000004015bd in test() ()
#3  0x000000000040171f in main ()

To further narrow down where your segmentation fault occurred, I used simple cout statements to locate the exact error.

Edit:

Change

pair<vii, vvi> gh;

cout<<"Now enter the edges and their capacity";
    for(int i=0; i < M; i++) {
            cin>>source;
            cin>>sink;
            cin>>cap;
        g.add_edge(source, sink, cap, cap);
        assert_equal(g.max_flow(source, sink), compute_max_flow(source, sink, gh));
    }
gh = construct_gh_tree(g); 

To

    pair<vii, vvi> gh;

cout<<"Now enter the edges and their capacity";
    for(int i=0; i < M; i++) {
            cin>>source;
            cin>>sink;
            cin>>cap;
        g.add_edge(source, sink, cap, cap);
        gh = construct_gh_tree(g);
        assert_equal(g.max_flow(source, sink), compute_max_flow(source, sink, gh));
    }

But, after this, you still have an infinite loop in max_flow that you need to deal with...