Segmentation Fault before main
so I've been running into a problem where somehow my code is causing segmentation faults before any of my main actually runs. I've never had this happen before and I hardly have a quarter's worth of coding experience so I'm not sure if there's something I'm doing wrong. Everything compiles, at least on my computer, but upon running it my main is never reached.
Context: I'm trying to connect Vertices and Edges in an adjacency matrix and then use Prim's algorithm to build an MST, but that's for later. I built a header file, which originally contained only typdef calls for the structures and the functions. However, I switched the structure definitions to the header file because I was getting memory errors; hence why I think there's an issue with the structs.
graph.h:
//Leland Wong 00000897031
//graph header file
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#ifndef GRAPH_H
#define GRAPH_H
typedef struct vertex
{
double longitude;
double latitude;
char city[30];
int index;
int visited; //0: not visited, 1: visited, 2: visited
struct edge* nexte;
struct vertex* nextv;
double projected;
}VERTEX;
typedef struct edge
{
struct vertex* start;
struct vertex* destination;
double distance;
struct edge* nexte;
}EDGE;
typedef struct graph
{
struct vertex* list[756];
struct edge* matrix[756][756];
}GRAPH;
/*
typedef struct vertex VERTEX;
typedef struct edge EDGE;
typedef struct graph GRAPH;
*/
double findDistance(VERTEX* v1, VERTEX* v2); //compute the distance between two locations
EDGE* connect(VERTEX* v1, VERTEX* v2); //connects two vertices and returns the connecting EDGE
GRAPH primMatrix(GRAPH *g); //connects all vertices using Prim's Algorithm in an adjacency matrix
//void lPrimConnect(VERTEX v); //connects all vertices using Prim's Algorithm in an adjacency list
EDGE* findSmallestEdge(VERTEX v, GRAPH *g); //finds the smallest EDGE connected to v
#endif
graph.c: contains the implementations of all my functions
//functions
//computes the distance between v1 and v2
double findDistance(VERTEX* v1, VERTEX* v2)
{
printf("findDistance");
double long1 = v1->longitude;
double long2 = v2->longitude;
double lat1 = v1->latitude;
double lat2 = v2->latitude;
double distance = 0;
if(long1 < 0)
long1 += 360;
if(long2 < 0)
long2 += 360;
distance = powf((long1-long2), 2) + powf((lat1 - lat2), 2);
distance = sqrt(distance);
return distance;
}
//creates and returns an edge that connects v1 and v2
EDGE* connect(VERTEX* v1, VERTEX* v2)
{
printf("connect");
EDGE *new;
new->start = v1;
new->destination = v2;
new->distance = findDistance(v1, v2);
return new;
}
//finds smallest edge connected to v in GRAPH g
EDGE* findSmallestEdge(VERTEX v, GRAPH *g)
{
printf("findSmallestEdge");
EDGE *tempe;
int i, index;
index = v.index;
//set tempe equal to the first edge connected to v
tempe = g->matrix[index][0];
//find smallest edge connected to v
for(i = 0; i < 756; i++)
{
if(g->matrix[index][i] -> distance < tempe->distance && g->list[index]->visited == 0)
{
tempe = g->matrix[index][i];
}
}
return tempe;
}
//creates an MST out of GRAPH g using Prim's algorithm
GRAPH primMatrix(GRAPH *g)
{
printf("primMatrix");
GRAPH new; // = malloc(sizeof(GRAPH));
EDGE *smallest;
EDGE *tempe;
int i, x;
i = 1;
x = 0;
new.list[0] = g->list[0]; //add root node to MST
g->list[0]->visited = 2;
smallest = findSmallestEdge(*new.list[0], g);
new.matrix[0][smallest->destination->index] = smallest;
//MST will contain all 756 nodes, so run this 755 times to ensure all nodes are reached
while(i < 756)
{
x = 0;
smallest = findSmallestEdge(*new.list[i], g);
//i = number of vertices already reached
while(x < i)
{
tempe = findSmallestEdge(*new.list[x], g);
if(tempe -> distance < smallest -> distance)
{
smallest = tempe;
}
x++;
}
new.list[i] = smallest -> destination;
smallest -> destination -> visited = 2;
new.matrix[smallest->start->index][smallest->destination->index] = smallest;
i++;
}
return new;
}
graphmatrixmain.c: my main function which builds the graphs
#include "graph.h"
int main(int argc, char* argv[])
{
FILE *fp;
static GRAPH g;
char buffer[200];
int i, j;
char city[30];
char *long1;
char *lat1;
if(argc == 1)
{
printf("could not open file\n");
return 0;
}
else
fp = fopen(argv[1], "r");
//read in line of data from txt file, build a new vertex, and insert into list
while(fgets(buffer, 200, fp) != NULL)
{
VERTEX *new = malloc(sizeof(VERTEX));
printf("%s", buffer);
sscanf(buffer, "%s %s %s", city, long1, lat1);
//sscanf(buffer, "%[^\t]\t%[^\t]\t%s", city, long1, lat1);
printf("scanned in data\n");
new->longitude = atof(long1);
new->latitude = atof(lat1);
new->index = i;
g.list[i] = new;
printf("%s: (%lf, %lf)", new->city, new->longitude, new->latitude);
i++;
}
//create EDGE and make connects between every VERTEX in list
for(i = 0; i < 756; i++)
{
for(j = 0; j < 756; j++)
{
g.matrix[i][j] = connect(g.list[i], g.list[j]);
if(j == 0)
{
g.list[i]->nexte = g.matrix[i][j];
}
}
}
return 0;
}
In case its necessary, this is the file i'm reading in from: cities.txt it contains 756 entries total but as far as the code is concerned size shouldn't be relevant
Shanghai 121.47 31.23
Bombay 72.82 18.96
Karachi 67.01 24.86
Buenos Aires -58.37 -34.61
Delhi 77.21 28.67
Istanbul 29 41.1
Manila 120.97 14.62
Sao Paulo -46.63 -23.53
Moscow 37.62 55.75
Answer
I've been running into a problem where somehow my code is causing segmentation faults before any of my main actually runs.
Usually, this means that the data structures that your main tries to place in the automatic storage area overflow the stack. In your situation, it looks like the GRAPH is a suitable suspect to do just that: it has a 2D array with 571536 pointers, which could very well overflow the stack before your main gets a chance to start.
One solution to this problem would be moving the GRAPH into the static area: since you allocate it in the main, it's going to be only one instance of it anyway, so declaring it static should fix the problem:
static GRAPH g;
You might also want to allocate it in the dynamic area using malloc, but in this case it probably does not matter.