SIGSEGV, Segmentation fault error

[sparky]

Hello,

I am trying to create a graph but I get the following error when debugging my program using Code::Blocks (please see below). Any assistance will be appreciated:

Program received signal SIGSEGV, Segmentation fault. Do you want to view the backtrace?

Here is the backtrace:

#0 004017FC UnorderedLinkList::insertLast(this=0x3e24f4, newItem=@0x22fd74) (C:/Documents and Settings/.../Desktop/Graphs/Graphs/UnorderedLinkList.cpp:119)
#1 00402469 GraphType::createGraph(this=0x22ff50) (C:/Documents and Settings/.../Desktop/Graphs/Graphs/GraphType.cpp:49)
#2 0040208B main() (C:/Documents and Settings/.../Desktop/Graphs/Graphs/main.cpp:11)

And here are lines 119...

void UnorderedLinkList::insertLast(const int& newItem)
{
    NodeType *newNode;
    newNode = new NodeType;
    newNode->info = newItem;
    newNode->link= NULL;

    if(first == NULL)
    {
        first = newNode;
        last = newNode;
        count++;
    }
    else
    {
        last->link = newNode; // ################ LINE 119 ##########################
        last = newNode;
        count++;
    }
}

line 49...

void GraphType::createGraph()
{
        ifstream infile;
        char fileName[50];
        int index;
        int vertex;
        int adjacentVertex;

        if(gSize != 0)
            clearGraph();

        cout << "Enter input file name: ";
        cin >> fileName;
        cout << endl;
        infile.open(fileName);
        if(!infile)
        {
                cout << "Cannot open input file." << endl;
                return;
        }

        infile >> gSize;

        for(index = 0; index < gSize; index++)
        {
                infile >> vertex;
                infile >> adjacentVertex;

                while(adjacentVertex != -999)
                {
                    graph[ vertex ].insertLast(adjacentVertex);// ############### LINE 49 ######################
                    infile >> adjacentVertex;
                }
        }
        infile.close();
}

and line 11

#include <iostream>
# include "GraphType.h"

using namespace std;

int main()
{
    GraphType g;
    g.createGraph(); // ############ LINE 11 ####################
    return 0;
}

[PanGalactic]

Are you sure UnorderedLinkList::first and UnorderedLinkList::last are being properly initialized by the constructor? (Does the error happen for the first node or later?)

Why does UnorderedLinkList::insertLast() take its parameter by const &? There is not much point in that for integral types.

[gcampton]

line 49 is trying to access an array element that does not exist, that is why you get SEGfaults.

[sparky]

Thanks for replying PanGalactic

The error happens at the very last node!

Here is how first and last were initialized in the constructor:

UnorderedLinkList::UnorderedLinkList()
{
    first = NULL;
    last = NULL;
    count = 0;
}

Here is the insertFirst function:

void UnorderedLinkList::insertFirst(const int& newItem)
{
    NodeType *newNode;
    newNode = new NodeType;
    newNode->info = newItem;
    newNode->link = first;
    first = newNode;

    count++;

    if(last == NULL)
        last = newNode;
}

And here is the insertLast function:

void UnorderedLinkList::insertLast(const int& newItem)
{
    NodeType *newNode;
    newNode = new NodeType;
    newNode->info = newItem;
    newNode->link= NULL;

    if(first == NULL)
    {
        first = newNode;
        last = newNode;
        count++;
    }
    else
    {
        last->link = newNode;
        last = newNode;
        count++;
    }
}

I removed the "&" but II still got same error.

[sparky]

Thanks for your reply gcampton.

Regrading line 49, here is the header file for GraphType showing the graph pointer:

//GraphType.h

# ifndef H_GraphType
# define H_GraphType
# include "UnorderedLinkList.h"
# include "LinkListIterator.h"

class GraphType
{
    public:
        bool isEmpty() const;
        void createGraph();
        void clearGraph();
        void printGraph()const;
        void depthFirstTraversal();
        void dftAtVertex(int vertex);
        void breadthFirstTraversal();// left this out for now
        GraphType(int size = 0);
        ~GraphType();
    protected:
        int maxSize;
        int gSize;
        UnorderedLinkList *graph; //############ Note graph here #############

    private:
        void dft(int v, bool visited[]);
};
# endif 

And here is the constructor:

GraphType::GraphType(int size)
{
    maxSize = size;
    gSize = 0;
    graph = new UnorderedLinkList[size];
}

I am trying to learn how to implement graphs but the example in the book I am following make it so complicated by inheriting all these extra classes... I wish I could find a simpler example...

[sparky]

I've uploaded this project to rapidshare incase you would like to compile it:

http://rapidshare.com/files/316597387/Graphs.rar.html

Or you can download it from here (see attachments at the bottom of the page):
http://www.cpp-home.com/forum/viewtopic.php?f=7&t=16561

[gcampton]

shouldn't double post, or at least if you are add a link in the original topic. it's against the rules in almost every forum. anyway that said are you still having the same errors? or do you just need help figuring out how to implement graphs?

[PanGalactic]

You should probably assert(vertex<maxSize) before line 49.

[sparky]

Yes, I am still having the same error. And Yes I would really like to get this program working because I have to submit it soon.

When I compile the program, I am prompted to enter the input file name (which is 'Network.txt'). After entering this, I got this windows error message:

Graphs.exe
Graphs.exe has encountered a problem and needs to close. We are sorry for the inconvenience. If you were in the middle of something, the information you were working on might be lost.
Please tell Microsoft about this problem. We have created an error report that you can send to us. We will tteat this report as confidential and anonymous.

This is when the codeblock's debugger found the

SIGSEGV, Segmentation fault error

Here is the Microsoft error report:

<?xml version="1.0" encoding="UTF-16"?>
<DATABASE>
<EXE NAME="Graphs.exe" FILTER="GRABMI_FILTER_PRIVACY">
<MATCHING_FILE NAME="Graphs.exe" SIZE="725180" CHECKSUM="0x4C414BDA" MODULE_TYPE="WIN32" PE_CHECKSUM="0xC09CA" LINKER_VERSION="0x10000" LINK_DATE="12/05/2009 02:50:03" UPTO_LINK_DATE="12/05/2009 02:50:03" />
</EXE>
<EXE NAME="kernel32.dll" FILTER="GRABMI_FILTER_THISFILEONLY">
<MATCHING_FILE NAME="kernel32.dll" SIZE="989696" CHECKSUM="0x2D998938" BIN_FILE_VERSION="5.1.2600.5781" BIN_PRODUCT_VERSION="5.1.2600.5781" PRODUCT_VERSION="5.1.2600.5781" FILE_DESCRIPTION="Windows NT BASE API Client DLL" COMPANY_NAME="Microsoft Corporation" PRODUCT_NAME="Microsoft® Windows® Operating System" FILE_VERSION="5.1.2600.5781 (xpsp_sp3_gdr.090321-1317)" ORIGINAL_FILENAME="kernel32" INTERNAL_NAME="kernel32" LEGAL_COPYRIGHT="© Microsoft Corporation. All rights reserved." VERFILEDATEHI="0x0" VERFILEDATELO="0x0" VERFILEOS="0x40004" VERFILETYPE="0x2" MODULE_TYPE="WIN32" PE_CHECKSUM="0xFE572" LINKER_VERSION="0x50001" UPTO_BIN_FILE_VERSION="5.1.2600.5781" UPTO_BIN_PRODUCT_VERSION="5.1.2600.5781" LINK_DATE="03/21/2009 14:06:58" UPTO_LINK_DATE="03/21/2009 14:06:58" VER_LANGUAGE="English (United States) [0x409]" />
</EXE>
</DATABASE>

PanGalactic, would assert close the program in the event of an error? I would really like to fix the program. Any other ideas? Any would be really appreciated.


Thanks for letting me know about double posting gcampton.

[guestgulkan]

With your program I downloaded on Saturday Dec 5 @ 19:30 hrs - I found the following issue:

Problem with GraphType constructor.
The constructor looks like this:

GraphType::GraphType(int size)//note size has a default size of zero
{
    maxSize = size;
    gSize = 0;
    graph = new UnorderedLinkList[size];
}

and in main.cpp you do this:

    GraphType g;
    g.createGraph();
 

You create a graph object g with UnorderedLinkList array of zero size. You then call g.createGraph(); function which tries to use this 0 size array.

I don't think you should create the UnorderedLinkList array in the constructor. It would best be done in the creategraph() function once you have read the required size from the file.

Problem in creategraph() function
Your creategraph() function looks like this:

void GraphType::createGraph()
{
        ifstream infile;
        char fileName[50];

        int index;
        int vertex;
        int adjacentVertex;

        if(gSize != 0)
            clearGraph();

        cout << "Enter input file name: ";
        cin >> fileName;
        cout << endl;

        infile.open(fileName);

        if(!infile)
        {
                cout << "Cannot open input file." << endl;
                return;
        }

        infile >> gSize;

        for(index = 0; index < gSize; index++)
        {
                infile >> vertex;//<=================
                infile >> adjacentVertex;

                while(adjacentVertex != -999)
                {
                    graph[ vertex ].insertLast(adjacentVertex);// 
                    infile >> adjacentVertex;
                }
        }
        infile.close();
}

Your network.txt file looks like this:

10
1 2 3 10 -999
2 1 3 -999
3 2 1 10 9 4 -999
4 3 9 5 -999
5 4 9 7 6 -999
6 5 7 8 -999
7 5 8 9 -999
8 9 7 6 -999
9 10 3 4 5 7 8 -999
10 1 3 9 -999

You have 10 lists - the first number in each line is basically the array index.
An array of 10 in c++ are numbered 0 - 9 NOT 1 -10.
So in fact :

        for(index = 0; index < gSize; index++)
        {
                infile >> vertex;//<=================
                infile >> adjacentVertex;

                while(adjacentVertex != -999)
                {
                    graph[ vertex ].insertLast(adjacentVertex);// <=========
                    infile >> adjacentVertex;
                }
        }

You are ignoring UnorderedLinkList[0].
You will be using UnorderedLinkList[10]. This is OUT OF BOUNDS ARRAY ACCESS

[sparky]

guestgulkan,

It worked and I cannot thank you enough!

I changed the vertex numbers (0-9 instead of 1-10) and adjacent vertex in Network.txt as follows:

10
0 1 2 9 -999
1 0 2 -999
2 0 1 9 8 3 -999
3 2 8 5 -999
4 3 8 6 5 -999
5 4 6 7 -999
6 4 7 8 -999
7 8 6 5 -999
8 9 2 3 4 6 7 -999
9 0 2 8 -999

and I also created the graph object after getting the size of the graph size (10) in createGraph() instead of the constructor like this:

void GraphType::createGraph()
{
        ifstream infile;
        char fileName[50];

        int index;
        int vertex;
        int adjacentVertex;

        if(gSize != 0)
            clearGraph();

        cout << "Enter input file name: ";
        cin >> fileName;
        cout << endl;

        infile.open(fileName);

        if(!infile)
        {
                cout << "Cannot open input file." << endl;
                return;
        }

        infile >> gSize;

        graph = new UnorderedLinkList[gSize]; // <======================

        for(index = 0; index < gSize; index++)
        {
                infile >> vertex;
                infile >> adjacentVertex;

                while(adjacentVertex != -999)
                {
                    graph[ vertex ].insertLast(adjacentVertex);
                    infile >> adjacentVertex;
                }
        }
        infile.close();
}

And finally I deleted the creation of the graph object in the constructor:

GraphType::GraphType(int size)
{
    maxSize = size;
    gSize = 0;    
}

Thank you so much