Im having some problems with using the vector pushback method through a structure. The push back method works in one part of the code and not the other. Ive been staring at it for hours and testing different things and i cannot get it to pushback in the section of code i need it to. Any ideas about what is going on? Comments in the code point to the problem. The program reads a txt file that looks like this:
3
1 2 0.5
1 3 1.2
2 3 0.6
The first number is the number of edges in a directed graph. The other lines are a source vertex followed by the destination vertex followed by the weight of the path. The pushback is pushing the end vertex and the weight of the path onto the source vertex's outgoing edge list.
Note:Sorry for the long post
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include "DirectGraph.cpp"
#include "DirectGraph.h"
using namespace std;
int main()
{
vector<int> vertexTrack(100,0);
int numberVertex = 0;
DirectGraph directedGraph;
int edge;
ifstream infile("C:\\Users\\Vance\\Documents\\UTC\\Algorithm Analysis\\vertex-text.txt");
if(infile.is_open())
{
while(infile.good())
{
string word;
string strSource;
string strEnd;
string strWeight;
int numSource;
string edgeString;
getline(infile, word);
if(word.length()==1)
{
stringstream convert(word);
if(!(convert>>edge))
edge = 0;
}
else
{
int pos;
string strEnd;
int numEnd;
pos = word.find(" ");
strSource = word.substr(0, pos);
edgeString = word.substr(pos+1);
pos = edgeString.find(" ");
strEnd = edgeString.substr(0, pos);
if(strSource != "")
{
stringstream convert(strSource);
if(!(convert>>numSource))
numSource = 0;
}
if(strEnd != "")
{
stringstream convert(strEnd);
if(!(convert>>numEnd))
numSource = 0;
}
if(vertexTrack[numSource] == 0)
{
Vertex vert;
vert.dist = 10000;
vert.known = false;
vert.vertNum = numSource;
vert.path = 0;
//pushback method works here when the Vertex is being created for the first time
vert.edgeList.push_back(edgeString);
directedGraph.addVertex(numSource, vert);
vertexTrack[numSource] = 1;
if(numSource > numberVertex)
{
numberVertex = numSource;
}
}
else
{
//pushback method does not work here when i want to add something new to the structures vector
directedGraph[numSource].edgeList.push_back(edgeString);
}
if(vertexTrack[numEnd] == 0)
{
Vertex vert;
vert.dist = 10000;
vert.known = false;
vert.vertNum = numEnd;
vert.path = 0;
directedGraph.addVertex(numEnd, vert);
vertexTrack[numEnd] = 1;
if(numEnd > numberVertex)
{
numberVertex = numEnd;
}
}
}
}
infile.close();
int sourceVertex;
cout<<"Please specify the source vertex to find the shortest paths from: "<<endl;
cin>>sourceVertex;
directedGraph.shortPath(sourceVertex, numberVertex);
for(int i = 1; i<numberVertex+1; i++)
{
directedGraph.printPath(i);
cout<<endl;
}
}
return 0;
}#include <iostream>
#include "DirectGraph.h"
#include <string>
#include <list>
#include <vector>
#include <sstream>
#include <fstream>
DirectGraph::DirectGraph(): vertexList(100)
{
}
//Dijkstra's algorithm
void DirectGraph::shortPath(int sourceVertex, int numberVertex)
{
//set source distance to 0
vertexList[sourceVertex].dist = 0;
//index used to refer to the vertex currently being used
int vertIndex;
for(int j = 0; j < numberVertex; j++)
{
for(int i = 1; i < numberVertex+1; i++)
{
//int smallest = smallestUnknown();
if(j==0)
{
vertIndex = sourceVertex;
}
else
{
int smallest = smallestUnknown(numberVertex);
vertIndex = smallest;
}
}
std::cout<<"iteration "<<j<<std::endl;
std::cout<<"vertIndex "<<vertIndex<<std::endl;
vertexList[vertIndex].known = true;
std::cout<<"known after: "<<vertexList[vertIndex].known<<std::endl;
for(int i = 0; i < vertexList[vertIndex].edgeList.size(); i++)
{
std::cout<<"edgelist size "<<vertexList[vertIndex].edgeList.size()<<std::endl;
std::string edge;
std::string strNum;
std::string strCost;
double cost;
int num;
int pos;
edge = vertexList[vertIndex].edgeList[i];
pos = edge.find(" ");
strNum = edge.substr(0,pos);
strCost = edge.substr(pos+1);
if(strNum != "")
{
std::stringstream convert(strNum);
if(!(convert>>num))
num = 0;
}
if(strCost != "")
{
std::stringstream convert(strCost);
if(!(convert>>cost))
cost = 0;
}
std::cout<<"bool "<<vertexList[num].known<<std::endl;
if(!vertexList[num].known)
{
double sum = vertexList[vertIndex].dist + cost;
std::cout<<"sum "<<sum<<std::endl<<std::endl;
if(sum < vertexList[num].dist)
{
vertexList[num].dist = vertexList[vertIndex].dist + cost;
vertexList[num].path = vertIndex;
}
}
}
}
}
void DirectGraph::printPath(int source)
{
if(vertexList[source].path != 0)
{
printPath(vertexList[source].path);
std::cout<<" to ";
}
std::cout<<vertexList[source].vertNum;
}
void DirectGraph::addVertex(int index, Vertex vert)
{
vertexList[index] = vert;
}
Vertex DirectGraph::operator[](int i)
{
return vertexList[i];
}
double DirectGraph::smallestUnknown(int numberVertex)
{
double smallest = 10001;
for(int k = 1; k < numberVertex+1; k++)
{
if(vertexList[k].dist < smallest && !vertexList[k].known)
{
smallest = vertexList[k].vertNum;
}
}
return smallest;
}#ifndef DIRECTGRAPH_H_INCLUDED
#define DIRECTGRAPH_H_INCLUDED
#include <list>
#include <string>
#include <vector>
#include <string>
struct Vertex
{
std::vector<std::string> edgeList;
bool known;
double dist;
double cost;
int vertNum;
int path;
};
class DirectGraph
{
public:
DirectGraph();
void printPath(int source);
void addVertex(int index, Vertex vert);
void shortPath(int sourceVertex, int edge);
Vertex operator[](int i);
private:
std::vector<Vertex> vertexList;
double smallestUnknown(int numberVertex);
};
#endif // DIRECTGRAPH_H_INCLUDED