I am writing a program that will build a graph and then find the lowest costs between any given vertices. I have the program building the graph just fine, but now I just started to write the part that will find lowest costs and I get a seg fault error. After using cout's I have found that the entire program will run. But then right at the end when it should end, it suddenly hits a seg fault. Right now I am thinking it has something to do with the initialize function since this problem occured when that function was written. Any ideas? Thanks.
// Main program
#include <iostream>
#include "graph.cc"
using namespace std;
main ()
{
graph flightfares;
flightfares.build_graph();
flightfares.print_graph();
flightfares.find_shortest_dist();
// My program will get right here then hit seg fault
}
// Class and implementation program
// graph.cc
#include <iostream>
#include <vector>
#include <string>
#include <float.h>
using namespace std;
struct costpair
{
int vnum;
float fare;
costpair(int v = 0, float f = 0):vnum(v), fare(f){};
};
struct node
{
costpair info;
node * next;
};
class graph
{
public:
graph();
~graph();
void build_graph();
void print_graph();
void find_shortest_dist();
private:
// Attributes
vector<string> vnames;
vector<node*> adjlist;
double dist[];
int pred[];
bool undecided[];
// Member functions
int index(string name);
void insert_edge(string name1, string name2, float fare);
int add_vertice(string name);
void add_edge(int index1, costpair temp);
node * createnode(costpair temp);
void initialize();
};
// Constructor
graph::graph()
{
}
// Destructor
graph::~graph()
{
for (int i = 0; i < vnames.size(); i++) // This loop will run and delete all lists
{
node * p = adjlist.at(i);
node * temp;
while (p!=NULL)
{
temp = p->next; // Saves pointer to rest of list
delete p;
p = temp;
}
}
}
void graph::build_graph()
{
string name1, name2;
int index1, index2;
float fare;
cin >> name1 >> name2 >> fare; //Priming Read
while(name1 != "zzz") // Runs till end of file
{
insert_edge (name1, name2, fare);
// This if checks for EOF and reads next line if present
if(!(cin >> name1 >> name2 >> fare))
{
break;
}
}
}
// Returns the index of given name
int graph::index(string name)
{
for (int i = 0; i < vnames.size(); i++)
{
if (vnames.at(i) == name) return i;
}
return (-1); // Name was not found
}
// Function to insert new edge
// Called once two names and a fare have been read
void graph::insert_edge(string name1, string name2,
float fare)
{
int index1 = index(name1);
// Next if checks if first name needs to be added
if (index1 == -1) index1 = add_vertice(name1);
int index2 = index(name2);
// Next if checks if second name needs to be added
if (index2 == -1) index2 = add_vertice(name2);
// At this point, index1 and index2 contain the indices of name1 and name2
// This adds the edge
add_edge(index1, costpair(index2, fare));
}
// This functin addes a name to the name vector
// and pushes the adjacency vector back.
// Then the new index of the name is returned
int graph::add_vertice(string name)
{
vnames.push_back(name);
adjlist.push_back(NULL);
return (vnames.size()-1);
}
// Here a node is added to the adjacency vector
void graph::add_edge(int index1, costpair temp)
{
node * p = createnode(temp); // Creates node
// Adds node to appropriate list
p->next = adjlist.at(index1);
adjlist.at(index1) = p;
}
// This function creates a node and adds info to node
node * graph::createnode(costpair temp)
{
node * p = new node;
p->info = temp;
p->next = NULL;
return p;
}
// This fuction prints all vertices along with edges
void graph::print_graph()
{
for (int i = 0; i < vnames.size(); i++) // Runs for all vertices
{
cout << "The vertex is " << vnames.at(i) << endl;
node * p = adjlist.at(i); // Pointer to traverse list
if (p == NULL) // Checks if list is empty or not
{
cout << "This vertex has no neighbors" << endl;
}
else
{
cout << "The neighbors of this node are " << endl;
while (p!=NULL)
{
cout << vnames.at(p->info.vnum) << "(" << p->info.fare << ")" << endl;
p = p->next;
}
}
}
}
void graph::find_shortest_dist()
{
initialize(); // Will initialize the several arrays needed
}
void graph::initialize()
{
dist[vnames.size()];
pred[vnames.size()];
undecided[vnames.size()];
for (int i = 0; i < vnames.size(); i++)
{
dist[i] = DBL_MAX;
pred[i] = -1;
undecided[i]= false;
}
}