Seg fault errors

[stdeez]

Can someone help me identify the reason why I am getting a seg fault run error? I hate to bother but I've been trying for several days now to fix the same function.

class adjacencyList
{
public:
    explicit adjacencyList(int size);
    void buildGraph(Edge inEdge);
    void print();
    
private:
    
    struct neighbor
    {
        neighbor* next;
        int cost, vertexId;
        
        neighbor(int theCost, int vertex) : cost(theCost), vertexId(vertex), next(NULL){}
    };
    
    struct vertex
    {
        neighbor *next;
    };
    
    vector<vertex> list;
};



void adjacencyList::buildGraph(Edge inEdge)
{


    neighbor tempIt, temp2;
    
    
    if (list[inEdge.first()-1].next == NULL  && list[inEdge.second()-1].next == NULL)
    {
        list[inEdge.first()-1].next = neighbor(inEdge.edgeWeight(), inEdge.second());

        list[inEdge.second()-1].next = neighbor(inEdge.edgeWeight(), inEdge.first());

    }
    
    
    else if (list[inEdge.first()-1].next == NULL && list[inEdge.second()-1].next != NULL)
    {
        list[inEdge.first()-1].next = new neighbor(inEdge.edgeWeight(), inEdge.second());

        tempIt = list[inEdge.second()-1].next;
        
        while(list[inEdge.second()-1].next != NULL)
        {
            list[inEdge.second()-1].next = list[inEdge.second()-1].next->next;
        }
        
        list[inEdge.second()-1].next = new neighbor(inEdge.edgeWeight(), inEdge.first());
        
        list[inEdge.second()-1].next = tempIt;


    }
    
    
    else if (list[inEdge.first()-1].next != NULL && list[inEdge.second()-1].next == NULL)
    {
        
        list[inEdge.second()-1].next = neighbor(inEdge.edgeWeight(), inEdge.first());

        tempIt = list[inEdge.first()-1].next;
        while(list[inEdge.first()-1].next != NULL)
        {
            list[inEdge.first()-1].next = list[inEdge.first()-1].next->next;
        }
        
        list[inEdge.first()-1].next = neighbor(inEdge.edgeWeight(), inEdge.second());
        
        list[inEdge.first()-1].next = tempIt;

    }

    
    else
    {
        tempIt = list[inEdge.first()-1].next;
        while(list[inEdge.first()-1].next != NULL)
        {
            list[inEdge.first()-1].next = list[inEdge.first()-1].next->next;
        }
        
        list[inEdge.first()-1].next = neighbor(inEdge.edgeWeight(), inEdge.second());
        
        list[inEdge.first()-1].next = tempIt;

        
        
        tempIt = list[inEdge.second()-1].next;
        while(list[inEdge.second()-1].next != NULL)
        {
            list[inEdge.second()-1].next = list[inEdge.second()-1].next->next;
        }
        
        list[inEdge.second()-1].next = neighbor(inEdge.edgeWeight(), inEdge.first());
                
        list[inEdge.second()-1].next = tempIt;

        
    }
    
    

}

constructor for the list:

adjacencyList::adjacencyList(int size = 0) : list(size)
{
    for (int i=0; i<list.size(); i++)
        list[i].next = NULL;
}

and my main input is :

while (getline (inputFile, line))
        { 
        inputFile>>v1>>v2>>w;
        edge = Edge(v1,v2,w);
        edgeHeap.insert(edge);
        list.buildGraph(edge);
        }

[ac517]

Can you show us the main function and any data that is getting passed that causes it?

I have a feeling you aren't adding anything to the vector<vertex> list; before calling buildGraph()

Your buildGraph just starts referencing indexes in the list and I don't see any code that actually puts anything in the list first.

class MyClass {
public:
   void doIt() {
      v[10]=7;
      v[267]=4;
      v[12]=9;
   }
private:
   vector<int> v;
};

int main() {
    MyClass mc;
    mc.doIt(); //KABOOM
}

Since the vector is private you need to either need a constructor that fills it, a method that fills it, or fill it within buildGraph() before you start referencing indexes in the list. Unless there is some other code that is doing it not included here.

[stdeez]

It seems that the seg fault happens when I set

obj.next = obj.next.next

Should i overload assignment operator for obj?

edit: Honestly I don't know what is working and what isn't. Netbeans has always been very unreliable for me on windows.
For example: each call to neighbor(..) in my code above was made using the "new" operator yesterday and that wouldn't work for me. Just now I inserted "new" into each call to neighbor(..) again, and the code compiles and runs. The debugger doesn't pick up on any errors either.

The way it works If I save and exit and come back later; there's a good chance that it will have run errors again using the same exact code I have now.. So I'm sorry if I ask too much but half the time my IDE gives me problems when my code is right, and half the time it compiles and runs code that is absolutely not right....

I've ran code on linux at my school that ran with no issues that refused to run on my personal pc.

[ac517]

This skips the first line for me when I try it:

while (getline (inputFile, line))
{ 
    inputFile>>v1>>v2>>w;
    edge = Edge(v1,v2,w);
    edgeHeap.insert(edge);
    list.buildGraph(edge);
}

you could do

while (inputFile>>v1>>v2>>w)
{ 
    edge = Edge(v1,v2,w);
    edgeHeap.insert(edge);
    list.buildGraph(edge);
}

Moving on,

list[inEdge.first()-1].next = neighbor(inEdge.edgeWeight(), inEdge.second());

is assigning a neighbor to a neighbor*, are you sure this is compiling without any errors? When I make the necessary Edge class and other items and try to compile I get a whole bunch of errors in the buildGraph method.

The line numbers don't mean anything to you cause I copied it into a file graph.cpp, made an Edge class with necessary functions so I don't get warnings and then try to compile and this is what i get:

graph.cpp: In member function ‘void adjacencyList::buildGraph(Edge)’:
graph.cpp:57:14: error: no matching function for call to ‘adjacencyList::neighbor::neighbor()’
neighbor tempIt, temp2;
^
graph.cpp:57:14: note: candidates are:
graph.cpp:42:9: note: adjacencyList::neighbor::neighbor(int, int)
neighbor(int theCost, int vertex) : cost(theCost), vertexId(vertex), next(NULL){}
^
graph.cpp:42:9: note: candidate expects 2 arguments, 0 provided
graph.cpp:37:12: note: adjacencyList::neighbor::neighbor(const adjacencyList::neighbor&)
struct neighbor
^
graph.cpp:37:12: note: candidate expects 1 argument, 0 provided
graph.cpp:57:22: error: no matching function for call to ‘adjacencyList::neighbor::neighbor()’
neighbor tempIt, temp2;
^
graph.cpp:57:22: note: candidates are:
graph.cpp:42:9: note: adjacencyList::neighbor::neighbor(int, int)
neighbor(int theCost, int vertex) : cost(theCost), vertexId(vertex), next(NULL){}
^
graph.cpp:42:9: note: candidate expects 2 arguments, 0 provided
graph.cpp:37:12: note: adjacencyList::neighbor::neighbor(const adjacencyList::neighbor&)
struct neighbor
^
graph.cpp:37:12: note: candidate expects 1 argument, 0 provided
graph.cpp:62:37: error: cannot convert ‘adjacencyList::neighbor’ to ‘adjacencyList::neighbor*’ in assignment
list[inEdge.first()-1].next = neighbor(inEdge.edgeWeight(), inEdge.second());
^
graph.cpp:64:38: error: cannot convert ‘adjacencyList::neighbor’ to ‘adjacencyList::neighbor*’ in assignment
list[inEdge.second()-1].next = neighbor(inEdge.edgeWeight(), inEdge.first());
^
graph.cpp:73:16: error: no match for ‘operator=’ (operand types are ‘adjacencyList::neighbor’ and ‘adjacencyList::neighbor*’)
tempIt = list[inEdge.second()-1].next;
^
graph.cpp:73:16: note: candidate is:
graph.cpp:37:12: note: adjacencyList::neighbor& adjacencyList::neighbor::operator=(const adjacencyList::neighbor&)
struct neighbor
^
graph.cpp:37:12: note: no known conversion for argument 1 from ‘adjacencyList::neighbor*’ to ‘const adjacencyList::neighbor&’
graph.cpp:82:38: error: cannot convert ‘adjacencyList::neighbor’ to ‘adjacencyList::neighbor*’ in assignment
list[inEdge.second()-1].next = tempIt;
^
graph.cpp:91:38: error: cannot convert ‘adjacencyList::neighbor’ to ‘adjacencyList::neighbor*’ in assignment
list[inEdge.second()-1].next = neighbor(inEdge.edgeWeight(), inEdge.first());
^
graph.cpp:93:16: error: no match for ‘operator=’ (operand types are ‘adjacencyList::neighbor’ and ‘adjacencyList::neighbor*’)
tempIt = list[inEdge.first()-1].next;
^
graph.cpp:93:16: note: candidate is:
graph.cpp:37:12: note: adjacencyList::neighbor& adjacencyList::neighbor::operator=(const adjacencyList::neighbor&)
struct neighbor
^
graph.cpp:37:12: note: no known conversion for argument 1 from ‘adjacencyList::neighbor*’ to ‘const adjacencyList::neighbor&’
graph.cpp:99:37: error: cannot convert ‘adjacencyList::neighbor’ to ‘adjacencyList::neighbor*’ in assignment
list[inEdge.first()-1].next = neighbor(inEdge.edgeWeight(), inEdge.second());
^
graph.cpp:101:37: error: cannot convert ‘adjacencyList::neighbor’ to ‘adjacencyList::neighbor*’ in assignment
list[inEdge.first()-1].next = tempIt;
^
graph.cpp:108:16: error: no match for ‘operator=’ (operand types are ‘adjacencyList::neighbor’ and ‘adjacencyList::neighbor*’)
tempIt = list[inEdge.first()-1].next;
^
...
...
...


I think you want something like this, this compiles without errors:

void adjacencyList::buildGraph(Edge inEdge)
{


    neighbor *tempIt,*temp2;
    
    
    if (list[inEdge.first()-1].next == NULL  && list[inEdge.second()-1].next == NULL)
    {
        list[inEdge.first()-1].next = new neighbor(inEdge.edgeWeight(), inEdge.second());

        list[inEdge.second()-1].next = new neighbor(inEdge.edgeWeight(), inEdge.first());

    }
    
    
    else if (list[inEdge.first()-1].next == NULL && list[inEdge.second()-1].next != NULL)
    {
        list[inEdge.first()-1].next = new neighbor(inEdge.edgeWeight(), inEdge.second());

        tempIt = list[inEdge.second()-1].next;
        
        while(list[inEdge.second()-1].next != NULL)
        {
            list[inEdge.second()-1].next = list[inEdge.second()-1].next->next;
        }
        
        list[inEdge.second()-1].next = new neighbor(inEdge.edgeWeight(), inEdge.first());
        
        list[inEdge.second()-1].next = tempIt;


    }
    
    
    else if (list[inEdge.first()-1].next != NULL && list[inEdge.second()-1].next == NULL)
    {
        
        list[inEdge.second()-1].next = new neighbor(inEdge.edgeWeight(), inEdge.first());

        tempIt = list[inEdge.first()-1].next;
        while(list[inEdge.first()-1].next != NULL)
        {
            list[inEdge.first()-1].next = list[inEdge.first()-1].next->next;
        }
        
        list[inEdge.first()-1].next = new neighbor(inEdge.edgeWeight(), inEdge.second());
        
        list[inEdge.first()-1].next = tempIt;

    }

    
    else
    {
        tempIt = list[inEdge.first()-1].next;
        while(list[inEdge.first()-1].next != NULL)
        {
            list[inEdge.first()-1].next = list[inEdge.first()-1].next->next;
        }
        
        list[inEdge.first()-1].next = new neighbor(inEdge.edgeWeight(), inEdge.second());
        
        list[inEdge.first()-1].next = tempIt;

        
        
        tempIt = list[inEdge.second()-1].next;
        while(list[inEdge.second()-1].next != NULL)
        {
            list[inEdge.second()-1].next = list[inEdge.second()-1].next->next;
        }
        
        list[inEdge.second()-1].next = new neighbor(inEdge.edgeWeight(), inEdge.first());
                
        list[inEdge.second()-1].next = tempIt;

        
    }
    
}

[ac517]

You were assigning a struct to a pointer to a struct.

I still have my reservations that this will work correctly.

what if you have a file like this

1 2 9
1 3 6
2 1 8
2 3 5
3 1 7


the vertex 1 get stored at list[0], and vertex 2 is its neighbor, the edge has cost 9. Then we get to line 2 in the file and there is an edge from vertex 1 to vertex 3 with cost 6. Won't your code as it stands now overwrite the neighbor at list[0] so that it now points to vertex 3 with cost 6?

I'm not sure what you are trying for but what if you stored the data in a vector<vector<pair<int,int>>> adj; so that if I wanted to know all the ways out of say vertex 1 I would iterate through all the pairs at adj[0]:

for(int i=0;i<adj[0].size();++i)
{
      int toVertex = adj[0][i].first;
      int cost = adj[0][i].second;
}

That way you aren't messing around with pointers and new. Just a thought.

[stdeez]

For the first reply. Yes, I changed the calls to neighbor to be pointer value. (Netbeans is proving inconsistent on my pc)


Supposed line one of you sample input is stored in an edge and called by bulidgraph(Edge).

If both vertex1 and 2 are empty, then the code should assign vector[0] and vector[1] a new neighbor.

The other conditions are for if one or both vector[i-1] representing the vertices in the line have neighbors already.

Shouldn't I be able to just attach a linked list to each element in the vector<vertex> list?

My compiler is accepting my current code which is identical to your earlier comment. After adding all edges I wrote a print function to test it's validity:

void adjacencyList::print()
{
    neighbor *temp;
    
    for (int i=0; i<list.size(); i++)
    {
        temp = list[i].next;
        cout<<i+1<<" ";
        while(list[i].next != NULL)
        {
            cout<<list[i].next->vertexId<<" ";
            list[i].next = list[i].next->next;
        }
        
        list[i].next = temp;

        cout<<endl;
    }
}

For reference here is my input data:

vertex1 vertex2 weight respectively

1 2 45
1 3 4
2 3 16
2 4 6
3 4 8

The output I get is:

(for each line the first number is the vertices and each other is a neighbor)

1 2
2 1
3 1
4 2

but it should be this:

1 2 3
2 1 3 4
3 1 2 4
4 2 3


Note: Not to sound stupid, but, is anything in my code doing some kind of shallow copy assignment? I don't know if that makes sense to you haha, I'm just a bit rusty because I had to take a semester off. This is like my second real computer science class

[ac517]

Here is what I was talking about, its super simplistic, no error handling or checking, you can add that. But it displays the idea that you don't need to mess around with pointers and homegrown linked lists and complex logic. This assumes your files has vertices numbered numbered 1 .. N, they can appear in any order in the file, the vector will grow as needed.

#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

class adjList 
{
public:
	
	void addEdge(int from, int to, int cost)
	{
		while(from-1>=adj.size())
		{
			vector<pair<int,int> > vp;
			adj.push_back(vp);
		}
		adj[from-1].push_back(make_pair(to,cost));
	}
	
	int size()
	{
		return adj.size();
	}
	
	vector<pair<int,int> > operator[](int from)
	{
		return adj[from-1];
	}
	
private:
	vector<vector<pair<int,int> > > adj;

};


int main()
{
	string f;
	cout << "File name : ";
	cin >> f;
	
	ifstream infile(f.c_str());
	int v1,v2,w;
	adjList al;
	while(infile >> v1 >> v2 >> w)
	{
		al.addEdge(v1,v2,w);
		al.addEdge(v2,v1,w); //take this line out if they are one-way directed edges
	}
	
	cout << "From -> To = Cost" << endl;
	cout << "-----------------" << endl;
	for(int i=1;i<=al.size();++i)
	{
		vector<pair<int,int> > dest = al[i];
		for(int j=0;j<dest.size();++j)
		{
			cout << i << " -> " << dest[j].first << " = " << dest[j].second << endl;
		}
	}
		
	return 0;

}

Input
-------
1 2 9
2 1 8
3 1 7
1 3 6
2 3 5
4 5 13
5 3 12
6 1 8
1 5 9
9 8 4
8 7 3
7 3 9

Output
---------
From -> To = Cost
-----------------
1 -> 2 = 9
1 -> 2 = 8
1 -> 3 = 7
1 -> 3 = 6
1 -> 6 = 8
1 -> 5 = 9
2 -> 1 = 9
2 -> 1 = 8
2 -> 3 = 5
3 -> 1 = 7
3 -> 1 = 6
3 -> 2 = 5
3 -> 5 = 12
3 -> 7 = 9
4 -> 5 = 13
5 -> 4 = 13
5 -> 3 = 12
5 -> 1 = 9
6 -> 1 = 8
7 -> 8 = 3
7 -> 3 = 9
8 -> 9 = 4
8 -> 7 = 3
9 -> 8 = 4