Segmentation fault for a particular value

Question

I wrote a code which first takes dimensions(n X m) of a matrix as input, and then its elements which are 0s and 1s. Now I am trying to build a graph(adjacency list representation) using this matrix such that all 1s are connected to all other 1s they are adjacent to(i.e.,vertically, horizontally or diagonally). Elements of matrix are numbered in row major fashion, in order to represent them as vertices of the graph.

Here is the code:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <list>
#include <deque>

using namespace std;

class Graph
{
 public:

    list<int> *adjlist;
    int v;

    Graph(int v)
    {
        this->v=v;
        adjlist=new list<int> [v];      
    }

    void add_edge(int src, int dest)
    {
        cout<<src<<" "<<dest<<"\n";
        adjlist[src].push_back(dest);
    }

    void dfs_util(int src, bool *visited)
    {
        if(!visited[src])
        {
            cout<<src<<" ";
            visited[src]=true;
            list<int>::iterator i;
            for(i=adjlist[src].begin(); i!=adjlist[src].end(); i++)
            {
                if(!visited[*i])
                {
                    dfs_util(*i, visited);
                }
            }
        }
    }

    void dfs(int src)
    {
        bool visited[v];
        int i;
        for(i=0; i<v; i++)
            visited[i]=false;
        dfs_util(src, visited);
    }

    void bfs(int src)
    {
        int j;
        bool visited[v];
        for(j=0; j<v; j++)
        {
            visited[j]=false;
        }

        int front;
        deque<int> q;
        q.push_back(src);
        list<int>::iterator i;
        visited[src]=true;


        while(!q.empty())
        {
            front=q.front();
            q.pop_front();
            cout<<front<<" ";

            for(i=adjlist[front].begin(); i!=adjlist[front].end(); i++)
            {
                cout<<*i<<"\n";
                if(!visited[*i])
                {
                    visited[*i]=true;
                    q.push_back((*i));
                }
            }
        }
    }

    void display()
    {
        list<int>::iterator it;
        int i;
        //list<int>::iterator it;

        for(i=0; i<v; i++)
        {           
            cout<<"Adj list for "<<i<<"\n";
            for(it=adjlist[i].begin(); it != adjlist[i].end(); ++it)
            {
                cout<<*it<<"->";
            }
            cout<<"\n";
        }
    }
};


int main() {
    int arr[11][11], n, m, i, j, node;
    cin>>n;
    cin>>m;

    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            cin>>arr[i][j];
        }
    }

    Graph g(n*m-1);

    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            node=m*i+j;
            if(arr[i][j]==1)
            {
                if((i-1)>=0 && arr[i-1][j]==1)
                    g.add_edge(node, m*(i-1)+j);

                if((i-1)>=0 && (j+1)<m && arr[i-1][j+1]==1)
                    g.add_edge(node, m*(i-1)+(j+1));

                if((j+1)<m && arr[i][j+1]==1)
                    g.add_edge(node, m*(i)+(j+1));

                if((i+1)<n && (j+1)<m && arr[i+1][j+1]==1)
                    g.add_edge(node, m*(i+1)+(j+1));

                if((i+1)<n && arr[i+1][j]==1)
                    g.add_edge(node, m*(i+1)+(j));

                if((i+1)<n && (j-1)>=0 && arr[i+1][j-1]==1)
                    g.add_edge(node, m*(i+1)+(j-1));

                if((j-1)>=0 && arr[i][j-1]==1)
                    g.add_edge(node, m*(i)+(j-1));

                if((i-1)>=0 && (j-1)>=0 && arr[i-1][j-1]==1)
                    g.add_edge(node, m*(i-1)+(j-1));
            }
        }       
    }

    //g.bfs(0);
    //g.dfs(0);
    g.display();
    return 0;
}

Now this code gave me segmentation fault on calling g.bfs(0) or g.dfs(0). So I wrote a simple display function to narrow down the error, but even calling g.display() gives me segmentation fault.

However when I change the outer loop in display() function to:

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

it works perfectly fine and doesn't give a segmentation fault.

I can't understand why am I getting these segmentation faults and how changing the outer loop's initialization to 1 prevents it. Can anyone please explain the reasons?

Here is the sample input that I used:

5
5
1 1 0 0 0
0 1 1 0 0
0 0 1 0 1
1 0 0 0 1
0 1 0 1 1

Answer 1

Problem

Your adjacency list is an array, instead of a list or a vector:

list<int> *adjlist;

You initialize it in the constructor on the base of the argument v:

adjlist=new list<int> [v];      

So when constructing your graph you need to provide in advance how many adjacency lists you have ? So better not make a mistake !

Unfortunately, in main(), you initialize it with a missing item

Graph g(n*m - 1);   //  <----- why -1 ?  Don't you have n*m nodes ?

Solution

Just call the constructor with the correct size

Graph g(n*m);   //  n*m nodes ! 

You could help yourself in case of problems like this by adding some bound checking:

void add_edge(int src, int dest)   // src should be smaller than v 
{
    if (src>=v) {         // nice diagnostic message in case of problem
       cout <<"FAILURE: "<<src<<" out of bound ("<<v<<")"<<endl; 
    }
    else {
        cout<<src<<" "<<dest<<"\n";
        adjlist[src].push_back(dest);
    }
}

Without always implementing nice error messages like that, it should become a reflex to at least assert that the preconditions are met:

assert (src<v && dest<v);   

Better would be to make your adjacency list adjlist a vector or a map, and let it grow dynamically.