Skip to content

Instantly share code, notes, and snippets.

@yuuniverse4444

yuuniverse4444/PathFinder.cpp

Created January 8, 2014 08:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yuuniverse4444/8313427 to your computer and use it in GitHub Desktop.
Save yuuniverse4444/8313427 to your computer and use it in GitHub Desktop.
Download ZIP
Sample C++ Code I had
Raw
PathFinder.cpp
/*
Name Zhou Yu
File:pathfinder.cpp
Section Leader: Snir & Rohan
*/
#include"pqueue.h"
#include"helpFunc.h"
#include "genlib.h"
#include "extgraph.h"
#include <iostream>
#include <cmath>
#include"map.h"
#include"set.h"
#include"vector.h"
#include"stack.h"
#include"fstream"
const int FONT_SIZE = 9; // for node name labels
const string ARC_COLOR = "Dark gray"; // normal arc color
const string NODE_COLOR = "Black"; // normal node color
const string HIGHLIGHT_COLOR = "Red"; // color of chosen path/nodes
const double PAUSE_TIME = .05; // time to pause when animating algorithm
void DrawFilledCircleWithLabel(coordT center, string color, string label = "")
{
MovePen(center.x + CIRCLE_RADIUS, center.y);
SetPenColor(color);
StartFilledRegion(1.0);
DrawArc(CIRCLE_RADIUS, 0, 360);
EndFilledRegion();
if (!label.empty()) {
MovePen(center.x + CIRCLE_RADIUS, center.y);
SetFont("Helvetica");
SetPointSize(FONT_SIZE);
DrawTextString(label);
}
}
void DrawLineBetween(coordT start, coordT end, string color)
{
SetPenColor(color);
MovePen(start.x, start.y);
DrawLine(end.x - start.x, end.y - start.y);
}
coordT GetMouseClick()
{
coordT where;
WaitForMouseDown();
WaitForMouseUp();
where.x = GetMouseX();
where.y = GetMouseY();
return where;
}
/*Function: drawMap()
Draw all arcs in the graph in the data structure drawMap*/
void drawMap(Map<Node> & mymap)
{
Map<Node>::Iterator iter=mymap.iterator();
while(iter.hasNext()){
string key=iter.next();
// string key2=iter.next();
Node * pnode=&mymap[key];
Arcs * parc;
DrawFilledCircleWithLabel(pnode->location,"Black",pnode->name);
for(int i=0;i<pnode->vec.size();i++){
parc=pnode->vec[i];
string destination=parc->city2->name;//The name of destionation
DrawLineBetween(pnode->location,mymap[destination].location,"Black");
}
}
}
/*Function:drawLine()
draw line between the two cities linked by Arce * p with color "nodecolor"*/
void drawLine(Arcs * p,Map<Node> & mymap,string nodecolor)
{
string key1=p->city1->name;
string key2=p->city2->name;
DrawFilledCircleWithLabel(mymap[key2].location,nodecolor,key2);
DrawLineBetween(mymap[key2].location,mymap[key1].location,"red");
}
/*Function: ShortestPathInterface().
Implement the interface and function
to find the shortestPath by calling the function findShortestDistance.*/
void shortestPathInterface(Map<Node> & mymap,string pictureName)
{
InitGraphics();
DrawNamedPicture(pictureName);
drawMap(mymap);
cout<<"Click on starting location...";
coordT startCoor=GetMouseClick();
string start=findName(startCoor,mymap);
//From mymap to find the name of the start location according to startCoor
DrawFilledCircleWithLabel(mymap[start].location,"red", start);
cout<<start<<" chosen"<<endl;
cout<<"Click on ending location...";
coordT endCoor=GetMouseClick();
string end=findName(endCoor,mymap);
//From mymap to find the name of the destination according to endCoor
DrawFilledCircleWithLabel(mymap[end].location,"red",end);
cout<<end<<" chosen"<<endl;
Stack<Arcs *> optimal;//Stack optimal contains the optimal paths
PQueue<Stack<Arcs *> > myqueue(compareFuncStack);//compareFuncStack is the compare function
optimal=findShortestDistance(start,end,mymap,myqueue);//Stack optimal contains the optimal paths
double totalDistance=0;//Calculate the total distance
while(!optimal.isEmpty()){
Arcs * p=optimal.pop();
drawLine(p,mymap,"red");
totalDistance+=p->distance;//Calculate the total distance
}
cout<<"Done!The shortest path from "<< start << " to " << end
<< "is " << totalDistance<<" miles"<<endl;
}
/*The function to search miniSpannTree by using PQueue<Arcs *> */
void miniSpanTree(Map<Node> & mymap,string pictureName)
{
PQueue<Arcs * > myq(compareFuncArcs);//Use to contains arcs for Minimal Spanning Tree
Vector<Set<string> > myvec;//It contains the set of names of cities, just like contain set of nodes
InitGraphics();//Initiate graph again
DrawNamedPicture(pictureName);
Map<Node>::Iterator iter=mymap.iterator();
while(iter.hasNext()){//I put all names of cities into Vector<Set<string> >myvec as set of cities
//and link them by arcs from PQueue<Arcs *> until they are all combined into one set
//i.e when myvec.size()==1
string key=iter.next();
Node * pnode=&mymap[key];
DrawFilledCircleWithLabel(pnode->location,"Black",pnode->name);
Set<string> set;
set.add(key);
myvec.add(set);
for(int i=0;i<mymap[key].vec.size();i++){
myq.enqueue(mymap[key].vec[i]);//Put all arcs into PQueue<Arcs*> myq
}
}
while(myvec.size()>1){//When it size become 1, all nodes are in one set, we are done
if(myq.size()==0) break;
Arcs * parc=myq.extractMax();
Set<string> set2;//This set equals the set of myvec contains city2 Node
int number1=-1;//This number equals the index of myvec contains city1 Node, which we will union with other set
int number2=-1;//This number equals the index of myvec contains city2 Node, which we will delete
for(int i=0;i<myvec.size();i++){
if(myvec[i].contains(parc->city1->name))
number1=i;
if(myvec[i].contains(parc->city2->name)){
number2=i;
set2=myvec[i];
}
if(number1!=-1 && number2!=-1) break;
}
if(number1!=number2) {//Two cities are in different sets, they haven't linked yet
myvec[number1].unionWith(set2);
myvec.removeAt(number2);
drawLine(parc,mymap,"black");
}
}
}
/*************************************************************************
This function delete all pointers in Map<Node>, which is created in readFile
*************************************************************************/
void destructMap(Map<Node> & mymap)
{
Map<Node>::Iterator iter=mymap.iterator();
while(iter.hasNext()){
string key=iter.next();
Node * pnode=&mymap[key];
for(int i=0;i<pnode->vec.size();i++){//Delete all Arcs * pointer in Vector<Arcs *>
Arcs * parc=pnode->vec[i];
Node * p1=parc->city1;
Node * p2=parc->city2;
delete p1;delete p2;//Delete the Node * on both side of Arcs*
delete parc;//Delete the Arcs* in Vector
}
delete pnode;//Delete the node of mymap[key]
}
}
/*************************************************************************
This is the interface function, having the loop for the user interface
*************************************************************************/
void interFace()
{
MovePen(0,0);
string mapname;
string filename,pictureName;
int choice=0;
while(true){
Map<Node> mymap;
if(choice==4) {
destructMap(mymap);//Delete all stuff in mymap
break;//choice==4, user want to break;
}
InitGraphics();
while(true){//While loop for read in name of file to be open
cout<<endl<<endl<<"Please enter name of graph data file:";
cin>>filename;
if(filename=="USA"){
pictureName="USA.bmp";//File name
DrawNamedPicture(pictureName);
break;
}
else if (filename=="Stanford"){
pictureName="Stanford.gif";
DrawNamedPicture(pictureName);
break;
}
else cout<<"This file doesn't exist!";
}//While loop for read in name stopped
filename=filename+".txt";
int i=0;
char charfile[20];//Make the file name to be a char array so that I can use open and read in file.
for(;i<filename.size();i++)
charfile[i]=filename[i];
charfile[i]='\0';//The last character as '\0' as end
readFile(mymap,charfile,mapname);
while(true){//While loop for Dijkstra algorithm and minimal spanning tree
InitGraphics();
DrawNamedPicture(pictureName);//Initiate again so that we can implement new function
drawMap(mymap);
char ch;//For getline function use
cout<<"Your options are:"<<endl<<
"(1) Choose a new graph data file"<<endl<<
"(2) Find shortest path using Dijkstra's algorithm"<<endl<<
"(3) Compute the minimal spanning tree using Kruskal's algorithm"<<endl<<
"(4) Quit"<<endl<<
"Enter choice:";
cin>>choice;
ch=getchar();//There is a '\n' in input stream
if(choice==1) break;//Out of Dijkstra algorithm and minimal spanning tree loop
else if(choice==2){//ShortestpathInterface
shortestPathInterface(mymap,pictureName);
cout<<"Hit return to continue"<<endl;
while(true){
ch=getchar();
if(ch=='\n') break;
}
continue;
}
else if(choice==3){
miniSpanTree(mymap,pictureName);
cout<<"Minimal spanning tree now displayed."<<endl<<
"Hit return to continue"<<endl;
while(true){
ch=getchar();//Get enter key
if(ch=='\n') break;
}
continue;
}
else if(choice==4) break;
else {
cout<<"Invalid choice! Please try again!"<<endl;
continue;
}
}
}
}
int main()
{
InitGraphics();
SetWindowTitle("CS106 Pathfinder");
cout << "This masterful piece of work is a graph extravaganza!" << endl
<< "The main attractions include a lovely visual presentation of the graph" << endl
<< "along with an implementation of Dijkstra's shortest path algorithm and" << endl
<< "the computation of a minimal spanning tree. Enjoy!" << endl;
interFace();//Interface function
return (0);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment