Hey guys, I have been working on this program for my entire semester. I got it down to do what I want I think... except when I compile it, I get no errors or warnings (using Dev) and when I execute it runs through half of it and it stops and gives me a error saying the program stopped responding.
I tried debuging it but I don't know what it's telling me when it sends me to a if loop. Anyone have any suggestions, the program is displayed below and the text file is attached.
#include<iostream> //File input/ouput include files
#include<fstream>
#include<iomanip>
#include<set>
#include<list>
using namespace std; //C++ standard libraries
const int NUMARCS = 16; //Need to use const ints for array declaration
const int NUMNODES = 8;
int i;
int main() //Main function
{
ifstream readin("fstarin.txt", ios::in); //open input file
ofstream readout("hw5out.txt", ios::out); //open output file
if (!readin) {
cerr << "File could not be opened" << endl; //Make sure file opens
exit(1);
}
//declare arrays to be used
int tail[NUMARCS+1], head[NUMARCS+1], cost[NUMARCS+1], cap[NUMARCS+1];
//Initilize point[i] = 0... this will be a useful condition later
int point[NUMNODES+2] = {0};
int i = 1;
/*This is a fairly concise loop to read the input file and assign
the input stream to the arrays created. This same loop outputs the
arrays as well. Note that setw() is for formatting output*/
while (readin >> tail[i] >> head[i] >> cost[i] >> cap[i])
i++;
readout << setiosflags(ios::left) << setw(7) << "Arc #" << setw(7) << "Tail"<< setw(7)<< "Head" << setw(7)<< "Cost" << "Capacity" << endl;
for (i = 1; i <= NUMARCS; i++)
{
readout << setiosflags(ios::left) << setw(7) << i << setw(7) << tail[i]
<< setw(7) << head[i]
<< setw(7) << cost[i]
<< cap[i] << endl;
}
/*Now I use a loop to assign the point vector to the first arc in the
forward star having the same tail node. Note that nodes with no
emanating arcs will still have point[i] = 0*/
for (i = 1; i<= NUMARCS+1; i++)
{
if (point[tail[i]] == 0)
{
point[tail[i]] = i;
}
}
//Now I clean up those nodes with no emanating arcs
for (i = 1; i<=NUMNODES; i++)
{
if (point[i] == 0)
{
point[i] = point[i+1];
}
}
/*Lastly, we can set the pointer for the n+1 node, we can do it this
simply wlog becasue this condition will hold for all forward star
representations*/
point[NUMNODES+1] = NUMARCS +1;
//Output the pointer vector
readout << endl;
readout << "The point vector is: [";
for (i = 1; i <= NUMNODES+1; i++)
{
readout << point[i] << " ";
}
readout << "]";
readout << endl;
readout << endl;
/*This is the initialization phase of Dijkstra's: we need to construct the
temporary and permenently labeled node sets. The Perm set is initially empty,
the temporary initially contains all nodes. We then declare and initialize
the label and predecessor vector*/
//There are containers called sets with predefined operations that are useful
//in this context
set<int> Perm;
set<int> Temp;
set<int>::iterator it;
for (i = 1; i <= NUMNODES; i++)
{
Temp.insert(i);
}
int label[NUMNODES+1], pred[NUMNODES+1], lownode, lowlabel;
for (i = 1; i <=NUMNODES; i++)
{
label[i] = 1000;
}
label[1] = 0;
pred[1] = 0;
/*We enter the main loop, checking that not all nodes are permanently labeled*/
while (Perm.size() < NUMNODES)
{
lownode = 0;
lowlabel = 100000;
/*The first loop now checks for the lowest temporary distance label. This is
an easy, loop-based check*/
for (it = Temp.begin(); it != Temp.end() ; it++)
{
if (label[*it] < lowlabel)
{
lowlabel = label[*it];
lownode = *it;
}
}
//Remove the node from the temp set, add it to the permanent set
Temp.erase(lownode);
Perm.insert (Perm.end(),lownode);
/*Now, using the forward star, identify those arcs emanating from our newly
permanently labeled noede and update distance labels and pred vector as
appropriate*/
for (i= point[lownode]; i < point[lownode+1]; i++)
{
if (label[head[i]] > label[lownode] + cost[i])
{
label[head[i]] = label[lownode] + cost[i];
pred[head[i]] = lownode;
}
}
}
//Output the distance labels and predecessor vector
readout << "The optimal distance labels are:" << "[";
for (i = 1; i <=NUMNODES; i++)
{
readout << " " << label[i];
}
readout << "]" << endl << endl;
readout << "The predecessor vector is:" << "[";
for (i = 1; i <=NUMNODES; i++)
{
readout << " " << pred[i];
}
readout << "]" << endl << endl;
/*Now we can identify the shortest path from 1 to all. Use the list container
as lists do not automatically sort the contents*/
list<int> path;
list<int>::iterator iter;
for (i = 2; i <=NUMNODES; i++)
{
readout << "The shortest path from node 1 to node " << i << " is: 1";
int current = i;
path.erase(path.begin(), path.end());
while (pred[current] != 0 )
{
path.insert(path.begin(), current);
current = pred[current];
}
for (iter = path.begin(); iter !=path.end(); iter++)
{
readout << "-" << *iter;
}
readout << endl;
}
return 0;
}here is the text, it's also attached
1 2 2 4
1 3 3 7
2 4 2 6
2 5 6 8
2 6 8 8
3 2 5 5
3 5 3 8
3 8 5 9
4 3 2 4
4 5 3 4
4 6 3 9
4 7 1 5
5 7 6 4
5 8 1 2
7 6 1 5
8 7 2 9
