Hi I was wondering if anyone could help
I'm receiving a segmentation fault whenever I go to run
my main.cpp on my program. I've never encountered this before
and was wondering if anyone knew how it can be fixed.
The program consist of equiv.h, equiv.cpp, graph.h, graph.cpp, and main.cpp
here are the files
equiv.h
const int maxVertices = 50;
/*******************************************
* Equiv *
*******************************************
* Equiv is a structure type that holds a *
* pointer to an array of integers and an *
* integer of the size of that array. *
*******************************************/
struct Equiv
{
int* arrayIntegers;
int arraySize;
};
bool together(Equiv& e, int x, int y);
void combine(Equiv& e, int x, int y);equiv.cpp
#include <iostream>
#include <fstream>
#include "equiv.h"
/**********************************************
* together *
**********************************************
* together returns true if x and y are in the*
* same set as object e. *
**********************************************/
bool together(Equiv& e, int x, int y)
{
bool sameX = false;
bool sameY = false;
for(int i = 0; i < e.arraySize; i++)
{
if(e.arrayIntegers[i] == x)
sameX = true;
if(e.arrayIntegers[i] == y)
sameY = true;
if(sameX && sameY)
break;
}
return (sameX && sameY);
}
/**********************************************
* combine *
**********************************************
* combine puts x and y together by combining *
* the two into the same set. *
**********************************************/
void combine(Equiv& e, int x, int y)
{
if(together(e, x, y))
return;
bool switchX = false;
bool switchY = false;
if(e.arraySize > 0)
{
for(int i = 0; i < e.arraySize; i++)
{
if(x == e.arrayIntegers[i])
switchX = true;
if(y == e.arrayIntegers[i])
switchY = true;
if(switchX && switchY)
break;
}
}
else
{
e.arraySize = 0;
e.arrayIntegers = new int[maxVertices];
}
if(!switchX && !switchY)
{
if(x < y)
{
e.arrayIntegers[e.arraySize] = x;
e.arrayIntegers[e.arraySize+1] = y;
}
else
{
e.arrayIntegers[e.arraySize] = y;
e.arrayIntegers[e.arraySize+1] = x;
}
switchX = switchY = true;
e.arraySize += 2;
}
if(!switchX)
e.arrayIntegers[e.arraySize++] = x;
if(!switchY)
e.arrayIntegers[e.arraySize++] = y;
}graph.h
#include <iostream>
const int maxEdges = 100;
/**********************************************
* Edge *
**********************************************
* Edge is a structure that holds two vertices*
* and the weight. *
**********************************************/
struct Edge
{
int vertOne;
int vertTwo;
int weight;
};
/**********************************************
* Graph *
**********************************************
* Graph is a structure that holds the number *
* of vertices, the number of edges, and a *
* pointer to the array of edges. *
**********************************************/
struct Graph
{
int numVert;
int numEdges;
Edge * arrayEdges;
~Graph()
{
delete [] arrayEdges;
}
};
void readGraph(Graph& g);
void printGraph(Graph& g);
void kruskalAlg(Graph& g);
int totalWeight(Graph& g);graph.cpp
#include <iostream>
#include <fstream>
#include "graph.h"
#include "equiv.h"
using namespace std;
/**********************************************
* readGraph *
**********************************************
* readGraph reads in information about graph *
* g from standard input then sets the edges *
* to the maximum number of edges avaliable. *
**********************************************/
void readGraph(Graph& g)
{
int input;
cin >> g.numVert;
bool finished;
finished = false;
if(g.numEdges > 0)
delete [] g.arrayEdges;
g.arrayEdges = new Edge[maxEdges];
int k = 0;
while(!finished)
{
cin >> input;
if(input==0) break;
g.arrayEdges[k].vertOne = input;
cin >> g.arrayEdges[k].vertTwo;
cin >> g.arrayEdges[k].weight;
k++;
}
g.numEdges = k;
}
/************************************************
* printGraph *
************************************************
* printGraph prints out each vertice and weight*
* of graph g from the standard input. *
**********************************************/
void printGraph(Graph& g)
{
cout << "Vertices Weight" << endl;
for(int k=0; k < g.numEdges; k++)
cout << g.arrayEdges[k].vertOne << " " << g.arrayEdges[k].vertTwo<< "\t " << g.arrayEdges[k].weight << endl;
}
/**********************************************
* kruskalAlg *
**********************************************
* kruskalAlg computes the minimal spanning *
* tree using Kruskal's algorithm, it takes *
* graph g as a parameter and yields it to *
* graph k. *
**********************************************/
void kruskalAlg(Graph& g)
{
Graph k;
Equiv e;
k.numVert = g.numVert;
k.numEdges = 0;
k.arrayEdges = new Edge[maxEdges];
e.arraySize = 0;
e.arrayIntegers = 0;
int a = g.numEdges-1;
while(a > 1)
{
for(int i = 0; i < a; i++)
{
if(g.arrayEdges[i].weight > g.arrayEdges[i+1].weight)
{
Edge edgeOne = g.arrayEdges[i+1];
g.arrayEdges[i+1] = g.arrayEdges[i];
g.arrayEdges[i] = edgeOne;
}
}
a--;
}
for(int i = 0; i < g.numEdges; i++)
{
if(!together(e, g.arrayEdges[i].vertOne, g.arrayEdges[i].vertTwo))
{
combine(e, g.arrayEdges[i].vertOne, g.arrayEdges[i].vertTwo);
k.arrayEdges[k.numEdges++] = g.arrayEdges[i];
}
}
g.numEdges = k.numEdges;
delete [] g.arrayEdges;
g.arrayEdges = new Edge[maxEdges];
for(int i = 0; i < k.numEdges; i++)
g.arrayEdges[i] = k.arrayEdges[i];
}
/**********************************************
* totalWeight *
**********************************************
* totalWeight computes the total weight of *
* graph g. *
**********************************************/
int totalWeight(Graph& g)
{
int total = 0;
for(int k = 0; k < g.numEdges; k++)
total += g.arrayEdges[k].weight;
return total;
}main.cpp
#include <cstdlib>
#include <iostream>
#include "graph.h"
using namespace std;
int main()
{
Graph g;
readGraph(g);
cout << endl << "The input graph has " << g.numVert << " vertices, and its edges are as follows:" << endl << endl;
printGraph(g);
kruskalAlg(g);
cout << endl << "A minimal spanning tree uses the following edges." << endl << endl;
printGraph(g);
cout << endl << "The total weight of the spanning tree is " << totalWeight(g) << endl << endl;
}