I am writing a program in which I am trying to build a graph data structure using an adjacency list. The vertices in the graph structure have an ID, x and y coordinates, and an associated adjacency list which contain information about what the child vertices are, and the weight it costs to reach them.
I have tried debugging using print statements, such as the for loop in the Graph class, but I am unable to print any information about the vertices that I have push_back'ed into the vector called graph. Additionally, I know that all the contents of the coordinate file has been read in, but whenever I try to create the adjacency list from the edges file, I receive a Segmentation fault (core dumped). I attempted to use the debugger on Visual Studio Code, but it said the program was able to run without any errors, albeit I am getting a segmentation fault after compiling.
How can I stop getting this segmentation fault? I have also tried resizing my array, but this does not work either. I hit the segmentation fault in the for loop I tried to create. I am not sure why the vertex objects are not added to the vector I have created. Could someone please instruct me on how to actually add them?
#ifndef VERTEX_H
#define VERTEX_H
#include <vector>
#define INF 1000000000
using namespace std;
class Vertex {
public:
int id;
Vertex* parent;
bool visited; // Flag to see if this vertex has been visited
vector<pair<Vertex*, int>> children; // Connecting vertices to this vertex
float g; // Path cost from source vertex to this vertex
float h; // Heuristic ost from this node to goal node
int x; // x-coordinate of vertex in graph space
int y; // y-coordinate of vertex in graph space
// Constructor
Vertex(int id, int x, int y) {
this->id = id;
this->x = x;
this->y = y;
this->g = INF;
this->h = INF;
parent = NULL;
visited = false;
}
// Add an edge to the vertex, populate the adjacency list
void addEdge(Vertex* child, int weight) {
children.push_back(make_pair(child, weight));
}
// Generic heuristic value calculation
float f() {
return g h;
}
};
#endif
#ifndef GRAPH_H
#define GRAPH_H
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include <sstream>
#include <vector>
using std::ifstream;
#include "Vertex.h"
using namespace std;
class Graph {
public:
vector<Vertex*> graph;
int vertexCount;
string edges;
string coordinates;
// Constructor
Graph(string edges, string coordinates, int vertexCount) {
this->edges = edges;
this->coordinates = coordinates;
this->vertexCount = vertexCount;
this->graph = createGraph(edges, coordinates, vertexCount);
};
vector<Vertex*> createGraph(string edges, string coordinates, int vertexCount) {
vector<Vertex*> graph;
// Read in coordinate information of vertices
ifstream coordinateInput(coordinates);
string line1, tempString1, tempString2, tempString3;
int vertex; // Member ID of the vertex
float x, y;
while (getline(coordinateInput, line1)) {
stringstream ss(line1);
getline(ss, tempString1, ',');
if (tempString1 == "--------------") break;
vertex = stoi(tempString1);
if (vertex >= graph.size()) {
graph.resize(vertex 1); // Resize
}
getline(ss, tempString2, ',');
x = stof(tempString2);
getline(ss, tempString3, ',');
y = stof(tempString3);
graph.push_back(new Vertex(vertex, x, y));
}
coordinateInput.close();
for (Vertex* v : graph) {
std::cout << "here" << endl;
std::cout << v->id << ' ' << v->x << v->y << endl;
}
std::cout << "Finished" << endl;
// Read in edge information and add them to the graph
ifstream edgeInput(edges);
int src, dest, weight;
string line2, tempString4, tempString5, tempString6;
while (getline(edgeInput, line2)) {
stringstream ss(line2);
getline(ss, tempString4, ',');
if (tempString4 == "--------------") break;
src = stoi(tempString4);
getline(ss, tempString5, ',');
dest = stoi(tempString5);
getline(ss, tempString6, ',');
weight = stoi(tempString6);
std::cout << graph[src]->id << endl;
std::cout << src << ' ' << dest << ' ' << weight << endl;
graph[src]->addEdge(graph[dest], weight);
}
edgeInput.close();
return graph;
}
};
#endif
Data I am trying to read in: Coordinates:
1,42.66,73.78
2,33.76,84.40
3,30.30,97.75
4,42.32,71.09
5,42.90,78.85
6,51.00,114.00
7,35.21,80.83
8,41.84,87.68
9,41.48,81.67
10,32.80,96.79
11,39.73,104.97
12,41.59,93.62
13,31.79,106.42
14,48.87,-2.33
15,32.74,97.33
16,29.76,95.38
17,39.79,86.15
18,30.32,81.66
19,35.68,220.23
20,39.08,94.56
21,24.56,81.78
22,30.19,82.64
23,36.19,115.22
24,34.03,118.17
25,42.33,122.86
26,35.12,89.97
27,25.79,80.22
28,44.96,93.27
29,37.3,120.9
30,45.50,73.67
31,29.97,90.06
32,40.70,73.92
33,28.53,81.38
34,40.72,76.12
35,33.53,112.08
36,38.07,122.81
37,45.52,122.64
38,35.82,78.64
39,39.53,119.82
40,38.56,121.47
41,29.45,98.51
42,37.76,122.44
43,37.30,121.87
44,46.49,84.35
45,47.63,122.33
46,37.69,97.34
47,39.76,84.20
48,35.27,120.66
49,27.97,82.46
50,30.45,84.27
51,43.65,79.38
52,38.91,77.01
53,40.75,111.89
--------------
Edges:
1,30,226
1,2,1003
1,32,153
1,4,166
1,5,212
2,4,1075
2,26,456
2,50,308
3,16,186
3,13,577
3,15,190
3,41,79
3,31,511
4,5,455
4,32,215
4,30,161
4,28,1391
5,51,105
5,9,191
6,52,605
6,32,829
6,51,2116
7,18,432
7,38,165
7,8,987
8,28,511
8,46,361
9,34,476
9,47,214
9,51,292
9,10,1341
10,11,792
10,15,20
10,16,248
10,41,374
11,46,523
11,35,466
11,35,386
12,44,135
12,28,246
12,4,933
12,26,789
12,50,310
12,13,1132
13,41,580
13,35,320
13,35,328
14,34,3939
14,19,5313
15,44,314
15,17,413
16,15,101
16,31,321
17,18,1014
17,20,502
17,50,432
18,33,146
18,22,113
19,36,5131
19,48,5451
20,44,249
20,46,190
20,21,1092
20,22,1231
21,49,446
21,22,2341
21,29,892
22,27,902
22,49,169
22,50,104
22,23,421
23,24,275
23,53,486
23,39,439
24,43,124
24,48,182
24,29,328
25,37,275
25,36,365
26,44,413
27,33,235
27,49,282
27,21,159
28,32,463
28,25,1920
29,40,80
30,51,401
30,29,1080
31,50,388
31,32,1901
32,34,101
32,53,1311
32,24,1531
33,49,84
33,32,1343
34,14,3548
34,52,147
35,43,518
36,37,642
36,24,962
36,42,635
36,40,115
36,48,271
37,45,174
37,53,777
38,52,371
39,53,520
39,40,133
40,41,140
40,42,95
41,48,895
41,42,2093
42,43,50
42,48,232
43,48,168
44,32,882
44,51,436
45,52,115
46,53,335
47,17,165
47,46,795
47,9,212
48,51,2751
48,50,133
48,52,232
51,18,486
52,51,2095
49,50,275
49,51,1335
49,53,2328
50,11,795
50,52,2095
51,15,201
51,16,248
52,41,373
52,19,4869
53,52,2084
53,26,1243
53,51,2343
36,43,519
15,32,643
46,24,962
46,42,633
38,40,113
26,48,222
16,19,3431
27,40,123
35,43,1131
25,45,220
15,11,341
25,42,1232
--------------
CodePudding user response：
Here's a stripped down version with embedded data that demonstrates how I might approach this problem. I had to make some modifications due to the embedded dataset, but you should be able to adapt this pretty easily to read from files. A stream is a steam after all.
One modification you should pay attention to from the Vertex class:
int x; // x-coordinate of vertex in graph space
int y; // y-coordinate of vertex in graph space
Vertex(int id, int x, int y) {
I changed the member types and constructor arguments to float. The data was being parsed as floats but then truncated when passed to the constructor. If you intend for that to happen that's fine, but it seemed odd to me.
There was nothing particularly wrong with that way you were parsing data, I just changed it to show an alternative. You should be aware that stoi and stof will throw an exception if the data can't be parsed. You also don't need the last line in the files and if (tempString4 == "--------------") break; since std::getline will fail and break the loop when it reaches the end.
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#define INF 1000000000
using namespace std;
class Vertex {
public:
int id;
vector<pair<Vertex*, int>> children; // Connecting vertices to this vertex
float x; // x-coordinate of vertex in graph space
float y; // y-coordinate of vertex in graph space
Vertex(int id, float x, float y) {
this->id = id;
this->x = x;
this->y = y;
}
void addEdge(Vertex* child, int weight) {
children.push_back(make_pair(child, weight));
}
};
class Graph {
public:
vector<Vertex*> graph;
int vertexCount;
Graph(std::istream& edges, std::istream& coordinates) {
graph = createGraph(edges, coordinates);
vertexCount = static_cast<int>(graph.size()) - 1;
};
~Graph()
{
for (auto& v : graph)
{
delete v;
}
}
vector<Vertex*> createGraph(std::istream& edges, std::istream& coordinates) {
vector<Vertex*> ret(1);
string line;
while (getline(coordinates, line)) {
stringstream ss(line);
int vertex;
float x;
float y;
char comma;
if (ss >> vertex >> comma >> x >> comma >> y && ss.eof())
{
ret.push_back(new Vertex(vertex, x, y));
}
else
{
std::cout << "Data error parsing vertex from '" << line << "'\n";
}
}
for (Vertex* v : ret) {
if (v)
{
std::cout << v->id << ' ' << v->x << ", " << v->y << endl;
}
}
while (getline(edges, line)) {
stringstream ss(line);
int src;
int dest;
int weight;
char comma;
if (ss >> src >> comma >> dest >> comma >> weight && ss.eof())
{
if (src < static_cast<int>(ret.size()) && ret[src])
{
//hack to force dest into range 1, 10 of limited dataset
dest = 1 dest % 10;
ret[src]->addEdge(ret[dest], weight);
}
else
{
std::cout << "Data error: src " << src << " invalid\n";
}
}
else
{
std::cout << "Data error parsing edge from '" << line << "'\n";
}
}
return ret;
}
};
int main()
{
std::istringstream coordinates(
"1, 42.66, 73.78\n"
"2, 33.76, 84.40\n"
"3, 30.30, 97.75\n"
"4, 42.32, 71.09\n"
"5, 42.90, 78.85\n"
"6, 51.00, 114.00\n"
"7, 35.21, 80.83\n"
"8, 41.84, 87.68\n"
"9, 41.48, 81.67\n"
"10, 32.80, 96.79");
std::istringstream edges(
"1, 20, 226\n1, 2, 1003\n1, 32, 153\n1, 4, 166\n1, 5, 212\n"
"2, 4, 1075\n2, 26, 456\n2, 50, 308\n"
"3, 16, 186\n3, 13, 577\n3, 15, 190\n3, 41, 79\n3, 31, 511\n"
"4, 5, 455\n4, 32, 215\n4, 30, 161\n4, 28, 1391\n"
"5, 51, 105\n5, 9, 191\n"
"6, 52, 605\n6, 32, 829\n6, 51, 2116\n7, 18, 432\n7, 38, 165\n7, 8, 987\n"
"8, 28, 511\n8, 46, 361\n"
"9, 34, 476\n9, 47, 214\n9, 51, 292\n9, 10, 1341\n"
"10, 11, 792\n10, 15, 20\n10, 16, 248\n10, 41, 374"
);
Graph g(edges, coordinates);
for (const auto& v : g.graph)
{
if (v)
{
std::cout << "\n";
std::cout << v->id << ", " << v->x << ", " << v->y << "\n";
for (const auto& e : v->children)
{
std::cout << "\t";
std::cout << e.first->id << ", " << e.first->x << ", " << e.first->y << ", " << e.second << "\n";
}
}
}
}