1. yes, It shuld be less than 1000 lines. 2. The error has now changed (funny enough xd)
The way I read the nodes into the graph don't matter anymore, now all that matters is if I load the font or not... If I dont load the font I dont get errors, If I do, then voila! (also, the error now seems to be a dequeue an empty queue error, which I'm not causing myself for sure!).
Anyway, submitting my code below:
Source.cpp
#include "Graph.h"
#include <SFML\Window.hpp>
#include <fstream>
int main(){
Graph graph;
std::ifstream graphFile;
std::string nodeFile="C:\\nodes.txt", edgeFile="C:\\edges.txt";
graphFile.open(nodeFile);
if(!graphFile.is_open()){
std::cout<<"failed to open file: "<<nodeFile<<"\n";
system("pause");
return 0;
}
while(!graphFile.eof()){
double x, y;
std::string name;
graphFile>>name;
graphFile>>x;
graphFile>>y;
graph.addNode(name, x, y);
}
graphFile.close();
graphFile.open(edgeFile);
if(!graphFile.is_open()){
std::cout<<"failed to open file: "<<edgeFile<<"\n";
system("pause");
return 0;
}
while(!graphFile.eof()){
int start, stop;
double cost;
graphFile>>start;
graphFile>>stop;
graphFile>>cost;
graph.addEdge(start, stop, cost);
}
graphFile.close();
std::string from="Dublin", to="London";
if(graph.pathFrom(from, to))
std::cout<<"There is a path from "<<from<<" to "<<to<<"!";
else
std::cout<<"There is no path from "<<from<<" to "<<to<<"!";
int num=graph.sPathFrom(from, to);
if(num>0){
std::cout<<"\nThe shortest path from "<<from<<" to "<<to<<" is on "<<num<<" flight(s)!\n";
std::stack<std::string> rout;
rout=graph.cPath(from, to);
std::cout<<"This is the cheapest rout:\n";
int lim=rout.size();
for(int n=0; n<lim; n++){
std::cout<<rout.top();
rout.pop();
if(rout.size()>0)
std::cout<<"->";
}
}
sf::RenderWindow window(sf::VideoMode(1000, 800), "Plot!");
window.setPosition(sf::Vector2i(500, 100));
window.setFramerateLimit(45);
sf::View view(sf::Vector2f(400, 400), sf::Vector2f(1000, 1000));
sf::Vector2i mousePos;
float dx=1, dy=1;
window.setView(view);
bool clicked=false;
while(window.isOpen()){
sf::Event event;
while(window.pollEvent(event))
{
if(event.type==sf::Event::MouseButtonPressed){
if(event.mouseButton.button==sf::Mouse::Left)
clicked=true;
}
if(event.type==sf::Event::MouseButtonReleased){
if(event.mouseButton.button==sf::Mouse::Left)
clicked=false;
}
if(event.type==sf::Event::MouseMoved&&clicked){
view.move(-dx*(event.mouseMove.x-mousePos.x), -dy*(event.mouseMove.y-mousePos.y));
}
if(event.type == sf::Event::MouseWheelMoved)
view.zoom(1.f+event.mouseWheel.delta*0.1f);
if(event.type==sf::Event::Closed)
window.close();
}
if(sf::Keyboard::isKeyPressed(sf::Keyboard::Q))
view.zoom(1.0309);
if(sf::Keyboard::isKeyPressed(sf::Keyboard::E))
view.zoom(0.97);
if(sf::Keyboard::isKeyPressed(sf::Keyboard::W))
view.move(0, -5);
if(sf::Keyboard::isKeyPressed(sf::Keyboard::S))
view.move(0, 5);
if(sf::Keyboard::isKeyPressed(sf::Keyboard::A))
view.move(-5, 0);
if(sf::Keyboard::isKeyPressed(sf::Keyboard::D))
view.move(5, 0);
mousePos=sf::Mouse::getPosition(window);
window.setView(view);
window.clear();
graph.draw(window);
window.display();
}
return 0;
}
Graph.h
#ifndef GRAPH_INCLUDE
#define GRAPH_INCLUDE
#include <vector>
#include <string>
#include <iostream>
#include <cstdlib>
#include <string>
#include <sstream>
#include <SFML\Window.hpp>
#include <SFML\Graphics.hpp>
#include <SFML\Graphics\Shape.hpp>
#include <cmath>
#include <queue>
#include <stack>
struct Node;
struct Edge{
double size;
Node *start, *end;
};
struct Node{
std::string name;
double x, y;
std::vector<Edge*> edges;
int num;
};
class Graph{
public:
Graph();
~Graph();
int numNodes();
void addNode(std::string name, double x, double y);
void addEdge(int start, int end, double size);
void draw(sf::RenderWindow& window);
bool pathFrom(std::string from, std::string target);
int sPathFrom(std::string from, std::string target);
std::stack<std::string> cPath(std::string from, std::string target);
private:
std::vector<Node*> nodes;
sf::Font font;
sf::Text tempTxt;
bool dFirst(int num, std::string target, std::vector<int>& visited);
int bFirst(std::queue<int>& q, std::string target, std::vector<int>& visited, int num, int steps, int addedThisLevel, int addedNextLevel, int level);
bool contains(int num, std::vector<int> visited);
int* heu(int end);
void aStar(std::vector<int>& open, std::vector<int>& closed, int* heuristic, double* fValue, int* pointers, double* gScore, int target, int start);
};
Graph::Graph(){
font.loadFromFile("C:\\Windows\\Fonts\\Calibri.ttf");
;
}
std::stack<std::string> Graph::cPath(std::string from, std::string target){
bool test1=true, test2=true;
int num1, num2;
std::stack<std::string> ret;
for(int n=0; n<nodes.size(); n++){
if(nodes.at(n)->name==from){
test1=false;
num1=n;
}
if(nodes.at(n)->name==target){
test2=false;
num2=n;
}
}
int* heuristic;
int* pointers = new int [nodes.size()];
double* gScore = new double[nodes.size()];
double* fValue = new double [nodes.size()];
std::vector<int> open;
std::vector<int> closed;
for(int n=0; n<nodes.size(); n++){
pointers[n]=-1;
fValue[n]=100000000;
gScore[n]=0;
}
heuristic=heu(num2);
open.push_back(num1);
aStar(open, closed, heuristic, fValue, pointers, gScore, num2, num1);
int n=num2;
while(n!=num1){
ret.push(nodes.at(n)->name);
n=pointers[n];
}
ret.push(nodes.at(n)->name);
delete [] gScore;
delete [] heuristic;
delete [] pointers;
delete [] fValue;
return ret;
}
void Graph::aStar(std::vector<int>& open, std::vector<int>& closed, int* heuristic, double* fValue, int* pointers, double* gScore, int target, int start){
fValue[start]=heuristic[start];
while(!open.empty()){
double checkF=fValue[open.at(0)];
int current, nCur;
for(int n=0; n<open.size(); n++){
if(fValue[open.at(n)]<=checkF){
checkF=fValue[open.at(n)];
current=open.at(n);
nCur=n;
}
}
if(current==target)
return;
open.erase(open.begin()+nCur);
closed.push_back(current);
for(int n=0; n<nodes.at(current)->edges.size(); n++){
double tentGScore=gScore[current]+nodes.at(current)->edges.at(n)->size;
double tentFScore=tentGScore+heuristic[nodes.at(current)->edges.at(n)->end->num];
if(contains(nodes.at(current)->edges.at(n)->end->num, closed)&&tentFScore>=fValue[nodes.at(current)->edges.at(n)->end->num])
continue;
else if(!contains(nodes.at(current)->edges.at(n)->end->num, open) || tentFScore<fValue[nodes.at(current)->edges.at(n)->end->num]){
pointers[nodes.at(current)->edges.at(n)->end->num]=current;
gScore[nodes.at(current)->edges.at(n)->end->num]=tentGScore;
fValue[nodes.at(current)->edges.at(n)->end->num]=tentFScore;
if(!contains(nodes.at(current)->edges.at(n)->end->num, open))
open.push_back(nodes.at(current)->edges.at(n)->end->num);
}
}
}
}
int* Graph::heu(int end){
int* a = new int [nodes.size()];
for(int n=0; n<nodes.size(); n++)
a[n]=sPathFrom(nodes.at(n)->name, nodes.at(end)->name);
return a;
}
int Graph::sPathFrom(std::string from, std::string target){
bool test1=true, test2=true;
int num;
std::vector<int> visited;
std::queue<int> q;
for(int n=0; n<nodes.size(); n++){
if(nodes.at(n)->name==from){
test1=false;
num=n;
}
if(nodes.at(n)->name==target)
test2=false;
}
if(test1||test2)
return -1;
return bFirst(q, target, visited, num, 0, 0, 0, 0);
}
int Graph::bFirst(std::queue<int>& q, std::string target, std::vector<int>& visited, int num, int steps, int addedThisLevel, int addedNextLevel, int level){
q.pop();
Node node=*nodes.at(num);
if(node.name==target)
return level;
if(node.edges.empty()&&q.empty())
return -1;
for(int n=0; n<node.edges.size(); n++){
if(!contains(node.edges.at(n)->end->num, visited)){
q.push(node.edges.at(n)->end->num);
visited.push_back(node.edges.at(n)->end->num);
addedNextLevel++;
}
}
if(steps==addedThisLevel){
level++;
addedThisLevel=addedNextLevel;
addedNextLevel=0;
steps=0;
}
return bFirst(q, target, visited, q.front(), steps+1, addedThisLevel, addedNextLevel, level);
}
bool Graph::pathFrom(std::string from, std::string target){
bool test1=true, test2=true;
int num;
std::vector<int> visited;
for(int n=0; n<nodes.size(); n++){
if(nodes.at(n)->name==from){
test1=false;
num=n;
}
if(nodes.at(n)->name==target)
test2=false;
}
if(test1||test2)
return false;
return dFirst(num, target, visited);
}
bool Graph::dFirst(int num, std::string target, std::vector<int>& visited){
Node node=*nodes.at(num);
if(node.name==target)
return true;
if(node.edges.empty())
return false;
for(int n=0; n<node.edges.size(); n++){
if(!contains(node.edges.at(n)->end->num, visited)){
visited.push_back(node.edges.at(n)->end->num);
if(dFirst(node.edges.at(n)->end->num, target, visited))
return true;
}
}
return false;
}
bool Graph::contains(int num, std::vector<int> visited){
for(int n=0; n<visited.size(); n++){
if(visited.at(n)==num)
return true;
}
return false;
}
Graph::~Graph(){
for(int n=0; n<nodes.size(); n++){
for(int i=0; i<nodes.at(n)->edges.size(); i++)
delete nodes.at(n)->edges.at(i);
delete nodes.at(n);
}
}
int Graph::numNodes(){
return nodes.size();
}
void Graph::addNode(std::string name, double x, double y){
Node* temp = new Node;
temp->name=name;
temp->x=x;
temp->y=y;
temp->num=nodes.size();
nodes.push_back(temp);
}
void Graph::addEdge(int start, int end, double size){
if(!(end<nodes.size()&&start<nodes.size()))
return;
Edge* temp = new Edge;
temp->size=size;
temp->start=nodes.at(start);
temp->end=nodes.at(end);
nodes.at(start)->edges.push_back(temp);
}
void Graph::draw(sf::RenderWindow& window){
for(int j=0; j<nodes.size(); j++){
for(int i=0; i<nodes.at(j)->edges.size(); i++){
double startX=nodes.at(j)->edges.at(i)->start->x;
double startY=nodes.at(j)->edges.at(i)->start->y;
double endX=nodes.at(j)->edges.at(i)->end->x;
double endY=nodes.at(j)->edges.at(i)->end->y;
sf::Vertex line[2]={
sf::Vertex(sf::Vector2f(startX, startY)),
sf::Vertex(sf::Vector2f(endX, endY))
};
window.draw(line, 2, sf::Lines);
sf::CircleShape temp(5, 3);
temp.setOrigin(5, 5);
temp.setPosition(endX, endY);
double theta;
if(endX==startX&&startY<endY)
theta=3.1415/2;
else if(endX==startX&&endY<startY)
theta=3*3.1415/2;
else{
theta=atan((endY-startY)/(startX-endX));
if(endX>startX)
theta=3.1415-theta;
if(endY>startY)
theta=-theta;
if(endX>startX&&endY<startY)
theta=-theta;
if(endX<startX&&endY>startY)
theta=atan((endY-startY)/(startX-endX));
}
temp.rotate(30);
temp.rotate(-180/3.1415*theta);
temp.move(10*cos(theta), -10*sin(theta));
window.draw(temp);
std::ostringstream strs;
strs << nodes.at(j)->edges.at(i)->size;
std::string str = strs.str();
tempTxt.setFont(font);
tempTxt.setString(str);
tempTxt.setPosition((startX+endX)/2+(startX-endX)/5, (startY+endY)/2+(startY-endY)/5);
tempTxt.setCharacterSize(30);
tempTxt.setColor(sf::Color(0, 255, 255, 255));
window.draw(tempTxt);
}
}
for(int j=0; j<nodes.size(); j++){
sf::CircleShape temp(5, 60);
temp.setOrigin(5, 5);
temp.setPosition(sf::Vector2f(nodes.at(j)->x, nodes.at(j)->y));
temp.setFillColor(sf::Color(255, 0, 0, 255));
window.draw(temp);
tempTxt.setFont(font);
tempTxt.setString(nodes.at(j)->name);
tempTxt.setPosition(sf::Vector2f(nodes.at(j)->x, nodes.at(j)->y-20));
tempTxt.setCharacterSize(30);
tempTxt.setColor(sf::Color(255, 255, 0, 255));
window.draw(tempTxt);
}
}
#endif
EDIT:
Also, the nodes.txt is on the form:
"nodeName" xPosition yPosition
"nodeName" xPosition yPosition
and the edges.txt is on the form:
startNode endNode size
startNode endNode size
where I'm pretty sure my bad practise of sometimes calling the cost of an edge it's "size", which is a dumb thing to do...
