CISC 220 Final Project

.gitignore

# Prerequisites
*.d

# Compiled Object files
*.slo
*.lo
*.o
*.obj

# Precompiled Headers
*.gch
*.pch

# Compiled Dynamic libraries
*.so
*.dylib
*.dll

# Fortran module files
*.mod
*.smod

# Compiled Static libraries
*.lai
*.la
*.a
*.lib

# Executables
*.exe
*.out
*.app

README.md

CISC220-Final-Project

Using Data Structures To Avoid Walking To Class™

Building and running the project

To build the project, just run

make

To run the project, run

./main locations.txt classsections.txt <residence hall>

Optionally, add "verbose" to the end of the command to see the data structures used in detail.

classsections.txt

32
EGGG101 010 480 540 TR Trabant
EGGG101 011 570 630 TR Trabant
ENGL110 080 935 1010 MW Memorial
ENGL110 081 610 660 MWF Alison
ENGL110 082 570 645 TR Alison
ENGL110 083 675 725 MWF Alison
ENGL110 084 805 855 MWF Memorial
ENGL110 085 480 555 TR Memorial
ENGL110 086 545 595 MWF Purnell
ENGL110 087 840 315 TR Alison
ENGL110 088 480 530 MWF Memorial
ENGL110 089 740 790 MWF Alison
ENGL110 090 750 825 TR Memorial
ENGL110 091 930 1005 TR Memorial
ENGL110 092 660 735 TR Memorial
MATH241 010 480 530 MWF Kirkbride
MATH241 011 740 790 MWF Kirkbride
MATH241 012 675 725 MWF Kirkbride
MATH241 014 870 920 MWF Kirkbride
MATH241 015 480 530 MWF Willard
MATH241 016 675 725 MWF Memorial
MATH241 017 805 855 MWF Kirkbride
MATH241 018 805 855 MWF Kirkbride
MATH241 019 935 985 MWF Purnell
CISC108 010 675 725 MWF Memorial
CISC108 011 805 855 MWF Gore
CISC108 080 520 595 MW Alison
ANTH101 010 870 920 MWF Smith
ANTH101 011 750 825 TR Willard
ANTH101 012 480 555 TR Purnell
ANTH101 013 675 725 MWF Brown
ANTH101 014 610 660 MWF Purnell

Coordinates.cpp

#include "Coordinates.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <vector>
#include <limits>

using namespace std;

void line_populate_coordinates(vector<string> &record, const string& line, char delimiter) {
  int linepos=0;
  char c;
  int i;
  int linemax=line.length();
  string curstring;
  record.clear();

  while(line[linepos]!=0 && linepos < linemax) {
    c = line[linepos];
    if (c==delimiter) {
      //end of field
      record.push_back( curstring );
      curstring="";
    }
    else if ((c=='\r' || c=='\n')) {
      record.push_back( curstring );
      return;
    }
    else {
      curstring.push_back(c);
    }
    linepos++;
  }
  record.push_back( curstring );
  return;
}

bool readUnorderedMapFromFile(std::unordered_map<std::string, Coordinates*> & m, char * fileName) {
  ifstream inFile(fileName);
  if (!inFile) {
    cerr << "File could not be opened" << endl;
    return false;
  }
  if (inFile.fail()) {
    cerr << "File not found" <<endl;
    return false;
  }

  vector<string> row;
  string line;
  int numCoordinates;

  int state = 0; // 0 for vertex #, 1 for edges #, > 1 for all else

  while(getline(inFile, line, '\n') && inFile.good() ) {
    line_populate_coordinates(row, line, ' ');
    
    if (state == 0) {
      numCoordinates = atoi(row[0].c_str());
      state++;
    }
    else if (numCoordinates > 0) {
      string label = row[0];
      double lon;
      double lat;
      sscanf(row[1].c_str(), "%lf", &lon);
      sscanf(row[2].c_str(), "%lf", &lat);
      double a = 39.123456789;

      Coordinates * c = new Coordinates(lon, lat);
      std::pair<string, Coordinates*> location (label, c);
      m.insert(location); 
      numCoordinates--;
    }
  }

  return true;
}
#include "Coordinates.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <vector>
#include <limits>

using namespace std;

void line_populate_coordinates(vector<string> &record, const string& line, char delimiter) {
  int linepos=0;
  char c;
  int i;
  int linemax=line.length();
  string curstring;
  record.clear();

  while(line[linepos]!=0 && linepos < linemax) {
    c = line[linepos];
    if (c==delimiter) {
      //end of field
      record.push_back( curstring );
      curstring="";
    }
    else if ((c=='\r' || c=='\n')) {
      record.push_back( curstring );
      return;
    }
    else {
      curstring.push_back(c);
    }
    linepos++;
  }
  record.push_back( curstring );
  return;
}

bool readUnorderedMapFromFile(std::unordered_map<std::string, Coordinates*> & m, char * fileName) {
  ifstream inFile(fileName);
  if (!inFile) {
    cerr << "File could not be opened" << endl;
    return false;
  }
  if (inFile.fail()) {
    cerr << "File not found" <<endl;
    return false;
  }

  vector<string> row;
  string line;
  int numCoordinates;

  int state = 0; // 0 for vertex #, 1 for edges #, > 1 for all else

  while(getline(inFile, line, '\n') && inFile.good() ) {
    line_populate_coordinates(row, line, ' ');
    
    if (state == 0) {
      numCoordinates = atoi(row[0].c_str());
      state++;
    }
    else if (numCoordinates > 0) {
      string label = row[0];
      double lon;
      double lat;
      sscanf(row[1].c_str(), "%lf", &lon);
      sscanf(row[2].c_str(), "%lf", &lat);
      double a = 39.123456789;

      Coordinates * c = new Coordinates(lon, lat);
      std::pair<string, Coordinates*> location (label, c);
      m.insert(location); 
      numCoordinates--;
    }
  }

  return true;
}

Coordinates.h

#ifndef COORDINATES_H_
#define COORDINATES_H_

#ifndef NULL
#define NULL 0
#endif

#include <vector>
#include <cmath>
#include <iostream>
#include <sstream>
#include <unordered_map>

using namespace std;

class Coordinates {
	public:
		double longitude;
		double latitude;

		Coordinates(double lo, double la) {
			longitude = lo;
			latitude = la;
		}

		string toString() const {
			stringstream s;
			s.precision(8);
			s << "(";
			s << longitude;
			s << ", ";
			s << latitude;
			s << ")";
			s << endl;
			return s.str();
		}

};

bool readUnorderedMapFromFile(unordered_map<string, Coordinates*> & m, char * fileName);

#endif // COORDINATES_H_

CourseSection.cpp

#include "CourseSection.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <vector>
#include <limits>

using namespace std;

void line_populate_course_section(vector<string> &record, const string& line, char delimiter) {
  int linepos=0;
  char c;
  int i;
  int linemax=line.length();
  string curstring;
  record.clear();

  while(line[linepos]!=0 && linepos < linemax) {
    c = line[linepos];
    if (c==delimiter) {
      //end of field
      record.push_back( curstring );
      curstring="";
    }
    else if ((c=='\r' || c=='\n')) {
      record.push_back( curstring );
      return;
    }
    else {
      curstring.push_back(c);
    }
    linepos++;
  }
  record.push_back( curstring );
  return;
}

bool readCourseSectionMapFromFile(std::unordered_map<std::string, CourseSection*> & m, char * fileName) {
  ifstream inFile(fileName);
  if (!inFile) {
    cerr << "File could not be opened" << endl;
    return false;
  }
  if (inFile.fail()) {
    cerr << "File not found" <<endl;
    return false;
  }

  vector<string> row;
  string line;
  int numCourseSections;

  int state = 0; // 0 for vertex #, 1 for edges #, > 1 for all else

  while(getline(inFile, line, '\n') && inFile.good() ) {
    line_populate_course_section(row, line, ' ');
    
    if (state == 0) {
      numCourseSections = atoi(row[0].c_str());
      state++;
    }
    else if (numCourseSections > 0) {
      CourseSection * cs = new CourseSection(
		      row[0].c_str(), row[1].c_str(), 
		      atoi(row[2].c_str()), atoi(row[3].c_str()), 
		      row[4].c_str(), row[5].c_str());

      string label = cs->courseAndSectionNumber();

      std::pair<string, CourseSection*> courseSection (label, cs);
      m.insert(courseSection); 
      numCourseSections--;
    }
  }

  return true;
}

CourseSection.h

#ifndef COURSESECTION_H_
#define COURSESECTION_H_

#ifndef NULL
#define NULL 0
#endif

#include <vector>
#include <cmath>
#include <iostream>
#include <sstream>
#include <unordered_map>

using namespace std;

class CourseSection {
public:
    string course;
    string section;
    int startTime;
    int endTime;
    string days;
    string location;
    
    
    CourseSection(string c, string s, int st, int et, string d, string l) {
        course = c;
        section = s;
        startTime = st;
        endTime = et;
        days = d;
        location = l;
    }
    
    bool startsAfter(CourseSection * cs) {
	    //cout << toString() << " starts after " << cs->toString() << ": " << ((startTime > cs->endTime) || (days[0] == 'T' && cs->days[0] == 'M')) << endl;
	return (startTime > cs->endTime) || (days[0] == 'T' && cs->days[0] == 'M');
    }
    
    string toString() const {
        stringstream s;
        s << "(";
        s << course;
        s << section;
        s << ", ";
        s << startTime;
        s << ", ";
        s << endTime;
        s << ", ";
        s << days;
        s << ", ";
        s << location;
        s << ")";
        return s.str();
    }

    string courseAndSectionNumber() {
	    stringstream s;
	    s << course << section;
	    return s.str();
    }
    
};

bool readCourseSectionMapFromFile(unordered_map<string, CourseSection*> & m, char * fileName);

#endif // COURSESECTION_H_

gistfile1.txt

#ifndef COORDINATES_H_
#define COORDINATES_H_

#ifndef NULL
#define NULL 0
#endif

#include <vector>
#include <cmath>
#include <iostream>
#include <sstream>
#include <unordered_map>

using namespace std;

class Coordinates {
	public:
		double longitude;
		double latitude;

		Coordinates(double lo, double la) {
			longitude = lo;
			latitude = la;
		}

		string toString() const {
			stringstream s;
			s.precision(8);
			s << "(";
			s << longitude;
			s << ", ";
			s << latitude;
			s << ")";
			s << endl;
			return s.str();
		}

};

bool readUnorderedMapFromFile(unordered_map<string, Coordinates*> & m, char * fileName);

#endif // COORDINATES_H_

gistfile2.txt

#include "CourseSection.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <vector>
#include <limits>

using namespace std;

void line_populate_course_section(vector<string> &record, const string& line, char delimiter) {
  int linepos=0;
  char c;
  int i;
  int linemax=line.length();
  string curstring;
  record.clear();

  while(line[linepos]!=0 && linepos < linemax) {
    c = line[linepos];
    if (c==delimiter) {
      //end of field
      record.push_back( curstring );
      curstring="";
    }
    else if ((c=='\r' || c=='\n')) {
      record.push_back( curstring );
      return;
    }
    else {
      curstring.push_back(c);
    }
    linepos++;
  }
  record.push_back( curstring );
  return;
}

bool readCourseSectionMapFromFile(std::unordered_map<std::string, CourseSection*> & m, char * fileName) {
  ifstream inFile(fileName);
  if (!inFile) {
    cerr << "File could not be opened" << endl;
    return false;
  }
  if (inFile.fail()) {
    cerr << "File not found" <<endl;
    return false;
  }

  vector<string> row;
  string line;
  int numCourseSections;

  int state = 0; // 0 for vertex #, 1 for edges #, > 1 for all else

  while(getline(inFile, line, '\n') && inFile.good() ) {
    line_populate_course_section(row, line, ' ');
    
    if (state == 0) {
      numCourseSections = atoi(row[0].c_str());
      state++;
    }
    else if (numCourseSections > 0) {
      CourseSection * cs = new CourseSection(
		      row[0].c_str(), row[1].c_str(), 
		      atoi(row[2].c_str()), atoi(row[3].c_str()), 
		      row[4].c_str(), row[5].c_str());

      string label = cs->courseAndSectionNumber();

      std::pair<string, CourseSection*> courseSection (label, cs);
      m.insert(courseSection); 
      numCourseSections--;
    }
  }

  return true;
}

gistfile3.txt

#ifndef COURSESECTION_H_
#define COURSESECTION_H_

#ifndef NULL
#define NULL 0
#endif

#include <vector>
#include <cmath>
#include <iostream>
#include <sstream>
#include <unordered_map>

using namespace std;

class CourseSection {
public:
    string course;
    string section;
    int startTime;
    int endTime;
    string days;
    string location;
    
    
    CourseSection(string c, string s, int st, int et, string d, string l) {
        course = c;
        section = s;
        startTime = st;
        endTime = et;
        days = d;
        location = l;
    }
    
    bool startsAfter(CourseSection * cs) {
	    //cout << toString() << " starts after " << cs->toString() << ": " << ((startTime > cs->endTime) || (days[0] == 'T' && cs->days[0] == 'M')) << endl;
	return (startTime > cs->endTime) || (days[0] == 'T' && cs->days[0] == 'M');
    }
    
    string toString() const {
        stringstream s;
        s << "(";
        s << course;
        s << section;
        s << ", ";
        s << startTime;
        s << ", ";
        s << endTime;
        s << ", ";
        s << days;
        s << ", ";
        s << location;
        s << ")";
        return s.str();
    }

    string courseAndSectionNumber() {
	    stringstream s;
	    s << course << section;
	    return s.str();
    }
    
};

bool readCourseSectionMapFromFile(unordered_map<string, CourseSection*> & m, char * fileName);

#endif // COURSESECTION_H_

gistfile4.txt

#include "Graph.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <vector>
#include <limits>

using namespace std;

void line_populate(vector<string> &record, const string& line, char delimiter) {
  int linepos=0;
  char c;
  int i;
  int linemax=line.length();
  string curstring;
  record.clear();

  while(line[linepos]!=0 && linepos < linemax) {
    c = line[linepos];
    if (c==delimiter) {
      //end of field
      record.push_back( curstring );
      curstring="";
    }
    else if ((c=='\r' || c=='\n')) {
      record.push_back( curstring );
      return;
    }
    else {
      curstring.push_back(c);
    }
    linepos++;
  }
  record.push_back( curstring );
  return;
}

bool readDirectedGraphFromFile(Graph & g, char * fileName) {
  ifstream inFile(fileName);
  if (!inFile) {
    cerr << "File could not be opened" << endl;
    return false;
  }
  if (inFile.fail()) {
    cerr << "File not found" <<endl;
    return false;
  }

  vector<string> row;
  string line;
  int numVertices;
  int numEdges;

  int state = 0; // 0 for vertex #, 1 for edges #, > 1 for all else

  while(getline(inFile, line, '\n') && inFile.good() ) {
    line_populate(row, line, ' ');
    
    if (state == 0) {
      numVertices = atoi(row[0].c_str());
      state++;
    }
    else if (state == 1) {
      numEdges = atoi(row[0].c_str());
      state++;
    }
    else if (numVertices > 0) {
      string label = row[0];
      g.vertices[label] = new Vertex(g.vertices.size(), label);
      numVertices--;
    }
    else if (numEdges > 0) {
      string id1 = row[0];
      string id2 = row[1];
      double weight = atof(row[2].c_str());

      Vertex* v1 = g.vertices[id1];
      Vertex* v2 = g.vertices[id2];
      v1->edges.push_back(new Edge(v1,v2,weight));
      //v2->edges.push_back(new Edge(v2,v1,weight));
      numEdges--;
    }
  }

  return true;
}

gistfile5.txt

#ifndef GRAPH_H_
#define GRAPH_H_

#ifndef NULL
#define NULL 0
#endif

#include <vector>
#include <cmath>
#include <iostream>
#include <string>
#include <sstream>
#include <unordered_map>

// not always the best idea but we're lazy today
using namespace std;

// Reserve the name for each Class to allow recursive definition
class Vertex;
class Edge;

#ifndef DEFAULT_VERTEX_STATUS
#define UNKNOWN 0
#define IDENTIFIED 1
#define VISITED 2
#define DEFAULT_VERTEX_STATUS 0
#endif

class Edge {
  public:
    Vertex * source;
    Vertex * target;
    double weight;

    Edge(Vertex * pSource, Vertex * pTarget, double pWeight)
        : source(pSource), target(pTarget), weight(pWeight){ }

    ~Edge() {}
};

// a simple Vertex that has an id and label and status marker
class Vertex {
  public:
  int id; // id represents the order this Vertex was added to a graph
  string label; // label must be unique
  int status; // sometimes called color in algorithms, helps with processing

  vector<Edge*> edges;
  Vertex(int pId, string pLabel) :
    id(pId), label(pLabel), status(DEFAULT_VERTEX_STATUS) {}

  ~Vertex() {
    for (auto iter = edges.begin();
          iter != edges.end(); iter++) {
      Edge * l = *iter;
      delete l;
    }
  }
};

// a Graph is just a lookup "table" of vertex label to Vertex
class Graph {
  public:
  unordered_map<string,Vertex*> vertices;

  Graph(){}
  ~Graph() {
    for (auto iter = vertices.begin();
              iter != vertices.end(); iter++) {
      Vertex * v = iter->second;
      delete v;
    }
  }

  string toString() const {
    stringstream s;
    for (auto iterV = vertices.begin();
          iterV != vertices.end(); iterV++) {
      Vertex * v = iterV->second;
      s << v->label << ": ";
      for (auto iterE = v->edges.begin();
            iterE != v->edges.end(); iterE++) {
          Edge * e = *iterE;
          s << e->target->label << "(" << e->weight << ") ";
      }
      s << endl;
    }

    return s.str();

  }
};

bool readDirectedGraphFromFile(Graph & g, char * fileName);
//bool createDirectedGraph(Graph & g, unordered_map<std::string, Coordinates*> locations, unordered_map<std::string, CourseSection*> courseSections);

#endif // GRAPH_H_

gistfile6.txt

#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <limits>
#include <algorithm>
#include <stack>
#include "Graph.h"
#include "Coordinates.h"
#include "CourseSection.h"

#define NUM_COURSES_PER_SEMESTER 5

using namespace std;

float distance(Coordinates* c1, Coordinates* c2) {
	double PI = 4.0 * atan(1.0);

	double dlat1 = c1->latitude * (PI/180);
	double dlat2 = c2->latitude * (PI/180);
	double dlon1 = c1->longitude * (PI/180);
	double dlon2 = c2->longitude * (PI/180);

	double delLon = dlon1 - dlon2;
	double delLat = dlat1 - dlat2;

	double aHarv = pow(sin(delLat/2.0),2.0)+cos(dlat1)*pow(sin(delLon/2),2);
	double cHarv = 2*atan2(sqrt(aHarv), sqrt(1.0-aHarv));

	const double earthRadius = 3963.19;

	double result = earthRadius*cHarv;
	return fabs(result);
}

float distanceBetweenBuildings(
		string building1, 
		string building2, 
		unordered_map<string, Coordinates*> locations) {
	//cout << distance(locations[building1], locations[building2]) << endl;
	return distance(locations[building1], locations[building2]);
}

bool createDirectedGraph(
		Graph & g, 
		unordered_map<std::string, Coordinates*> locations, 
		unordered_map<std::string, CourseSection*> courseSections) {
	for (auto it : courseSections) {
		g.vertices[it.first] = new Vertex(g.vertices.size(), it.first);		
	}
	
	for (auto v : g.vertices) {
		for (auto otherV : g.vertices) {
			if (courseSections[v.second->label]->course !=
			    courseSections[otherV.second->label]->course &&
			    courseSections[otherV.second->label]->startsAfter(
				    courseSections[v.second->label])) {
				v.second->edges.push_back(
						new Edge(
							v.second, 
							otherV.second, 
							distance(
								locations[courseSections[v.second->label]->location], 
								locations[courseSections[otherV.second->label]->location])));
			}
		}
	}
}

bool isInside(string str, char c)
{
	return str.find(c) != std::string::npos;
}

string scheduleToString(vector<string> & classesInThisSchedule);

float findPathLength(
		vector<string> & classesInThisSchedule, 
		unordered_map<string, Coordinates *> locations, 
		unordered_map<string, CourseSection *> courseSections, 
		string placeOfResidence) {
	float totalDistance = 0.0;
	char currentDay = 'M'; //;
	string currentLocation = placeOfResidence;
	while (currentDay != 'S') {
		for (auto courseSection : classesInThisSchedule) {
			//if (courseSections[courseSection]->days[0] != currentDay) {
			//	totalDistance += distanceBetweenBuildings(
			//			placeOfResidence, 
			//			courseSections[courseSection]->location, 
			//			locations);
			//}
			//cout << "distance from " << currentLocation << " to " << courseSections[courseSection]->location << ": " << distanceBetweenBuildings(
			//		currentLocation,
			//		courseSections[courseSection]->location,
			//	locations)
//<< endl;
			if (isInside(courseSections[courseSection]->days, currentDay)) {
				totalDistance += distanceBetweenBuildings(
					currentLocation,
					courseSections[courseSection]->location,
				locations);
				currentLocation = courseSections[courseSection]->location;
			}
		}
		totalDistance += distanceBetweenBuildings(
			currentLocation,
			placeOfResidence,
			locations);
		currentLocation = placeOfResidence;
		switch(currentDay) {
			case 'M':
				currentDay = 'T';
				break;
			case 'T':
				currentDay = 'W';
				break;
			case 'W':
				currentDay = 'R';
				break;
			case 'R':
				currentDay = 'F';
				break;
			case 'F':
				currentDay = 'S';
				break;
			default:
				currentDay = 'S';
				break;
		}
	}
	//cout << "Path " << scheduleToString(classesInThisSchedule) << " length: " << totalDistance << endl;
	return totalDistance;
	
}

bool labelInList(string word, vector<string> & lst) {
	bool result = false;
	for (auto i : lst) {
		result = result | 0 == strcmp(
				word.substr(0, 7).c_str(), 
				i.substr(0, 7).c_str());
	}
	return result;
}

string scheduleToString(vector<string> & classesInThisSchedule) {
	stringstream s;
	for (auto i : classesInThisSchedule) {
		s << i;
		s << ", ";
	}
	return s.str();

}

bool noScheduleConflicts(
		string courseSection, 
		vector<string> classesInThisSchedule,
		unordered_map<string, CourseSection *> courseSections) {
	for (auto c : classesInThisSchedule) {
		if (courseSections[c]->startsAfter(courseSections[courseSection]) ||
				courseSections[courseSection]->startsAfter(courseSections[c])) {

		} else {
			return false;
		}
	}
}

float shortestScheduleStartingAtVertex(
		Vertex * v, 
		vector<string> & classesInThisSchedule, 
		vector<string> & classesInShortestSchedule, 
		float runningMin, 
		unordered_map<string, Coordinates *> locations, 
		unordered_map<string, CourseSection *> courseSections, 
		string placeOfResidence) {
	//cout << "At vertex: " << v->label << endl;
	//cout << "runningMin: " << runningMin << endl;
	for (auto e : v->edges) {
		if (!labelInList(e->target->label, classesInThisSchedule) &&
				noScheduleConflicts(e->target->label, classesInThisSchedule, courseSections)) {
			classesInThisSchedule.push_back(e->target->label);
			
			if (classesInThisSchedule.size() == NUM_COURSES_PER_SEMESTER) {
	//cout << "Course list is: " << classesInThisSchedule.size()<< ": "  << scheduleToString(classesInThisSchedule) << endl;
				float x = findPathLength(
						classesInThisSchedule, 
						locations, 
						courseSections, 
						placeOfResidence);
				//cout << x << endl;
				if (x < runningMin) {
					//cout << "old shortest path: " << runningMin << endl;
					//cout << "new shortest path: " << x << endl;
					runningMin = x;
					classesInShortestSchedule = classesInThisSchedule;
				}
			} else {
				runningMin = shortestScheduleStartingAtVertex(
						e->target, 
						classesInThisSchedule, 
						classesInShortestSchedule, 
						runningMin, 
						locations, 
						courseSections, 
						placeOfResidence);
			}
			classesInThisSchedule.pop_back();
		}
	}
	//cout << "end foreach" << endl;
	return runningMin;
}

float findShortestPath(
		Graph & g, 
		unordered_map<string, Coordinates*> & locations, 
		unordered_map<string, CourseSection*> & courseSections, 
		vector<string> & classesInShortestSchedule, 
		string placeOfResidence) {
	vector<string> classesInThisSchedule;
	float minWalkingDistance = numeric_limits<float>::max();


	vector<string> tmpClassesInShortestSchedule;
	for (auto v : g.vertices) {
		//cout << "Starting at vertex: " << v.second->label << ", the shortest path is:" ; 
		classesInThisSchedule.push_back(v.second->label);
		float distance = shortestScheduleStartingAtVertex(
				v.second, 
				classesInThisSchedule, 
				tmpClassesInShortestSchedule, 
				numeric_limits<float>::max(), 
				locations, 
				courseSections, 
				placeOfResidence);
		//cout << distance << endl;
		if (distance < minWalkingDistance) {
			minWalkingDistance = distance;
			classesInShortestSchedule = tmpClassesInShortestSchedule;
		}	
		classesInThisSchedule.pop_back();
	}

	return minWalkingDistance;
}


int main(int argc, char **argv) {
	cout.precision(8);

	string placeOfResidence = argv[3];
	 
	bool verbose = false;
	if (argc > 4) {
		verbose = (strcmp(argv[4], "verbose") == 0);
		verbose = verbose | strcmp(argv[4], "v") == 0;
	}

	Graph g;

	if (verbose) {
		cout << argv[1] << endl;
		cout << argv[2] << endl;
		cout << argv[3] << endl;
		cout << endl;
	}

	unordered_map<std::string, Coordinates*> locations;
	
	readUnorderedMapFromFile(locations, argv[1]);
	if (verbose) {
		for (auto iter = locations.begin(); iter != locations.end(); ++iter) {
			cout << iter->first << ": " << iter->second->toString();
		}
	}

	unordered_map<std::string, CourseSection*> courseSections;	
	readCourseSectionMapFromFile(courseSections, argv[2]);

	if (verbose) {
		for (auto iter = courseSections.begin(); iter != courseSections.end(); ++iter) {
			cout << iter->first << ": " << iter->second->toString() << endl;
		}
	}

	createDirectedGraph(g, locations, courseSections);
	
	if (verbose) {
		cout << g.toString() << endl;
	}

	vector<string> classesInShortestSchedule;


	float distanceWalked = findShortestPath(
			g, 
			locations, 
			courseSections, 
			classesInShortestSchedule, 
			placeOfResidence);
	cout << "The class schedule that requires the minimum distance travelled is " << 
		scheduleToString(classesInShortestSchedule);
	cout << "and this schedule requires walking " << distanceWalked << " miles." << endl;

	for (auto i: classesInShortestSchedule) {
		cout << courseSections[i]->toString() << endl;
	}
	

	locations.clear();
	courseSections.clear();
	return 0;
}

gistfile7.txt

#CXX = g++
CXXFLAGS = -O2 -std=c++11

LIBS =
LDLIBS =
INCLUDES =

# force clean build every time
all: clean main

main: Graph.o Coordinates.o CourseSection.o main.o
	$(CXX) $^ -o $@

# name a variable cources for all source files
%.o: %.cpp
	$(CXX) $(CXXFLAGS) -c $< -o $@

clean: 
	rm -f *.o
	rm -f *.exe

gistfile8.txt

# CISC220-Final-Project
Using Data Structures To Avoid Walking To Class™

# Building and running the project
To build the project, just run 
```
make
```
To run the project, run 
```
./main locations.txt classsections.txt <residence hall>
```
Optionally, add "verbose" to the end of the command to see the data structures used in detail.

Graph.cpp

#include "Graph.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <vector>
#include <limits>

using namespace std;

void line_populate(vector<string> &record, const string& line, char delimiter) {
  int linepos=0;
  char c;
  int i;
  int linemax=line.length();
  string curstring;
  record.clear();

  while(line[linepos]!=0 && linepos < linemax) {
    c = line[linepos];
    if (c==delimiter) {
      //end of field
      record.push_back( curstring );
      curstring="";
    }
    else if ((c=='\r' || c=='\n')) {
      record.push_back( curstring );
      return;
    }
    else {
      curstring.push_back(c);
    }
    linepos++;
  }
  record.push_back( curstring );
  return;
}

bool readDirectedGraphFromFile(Graph & g, char * fileName) {
  ifstream inFile(fileName);
  if (!inFile) {
    cerr << "File could not be opened" << endl;
    return false;
  }
  if (inFile.fail()) {
    cerr << "File not found" <<endl;
    return false;
  }

  vector<string> row;
  string line;
  int numVertices;
  int numEdges;

  int state = 0; // 0 for vertex #, 1 for edges #, > 1 for all else

  while(getline(inFile, line, '\n') && inFile.good() ) {
    line_populate(row, line, ' ');
    
    if (state == 0) {
      numVertices = atoi(row[0].c_str());
      state++;
    }
    else if (state == 1) {
      numEdges = atoi(row[0].c_str());
      state++;
    }
    else if (numVertices > 0) {
      string label = row[0];
      g.vertices[label] = new Vertex(g.vertices.size(), label);
      numVertices--;
    }
    else if (numEdges > 0) {
      string id1 = row[0];
      string id2 = row[1];
      double weight = atof(row[2].c_str());

      Vertex* v1 = g.vertices[id1];
      Vertex* v2 = g.vertices[id2];
      v1->edges.push_back(new Edge(v1,v2,weight));
      //v2->edges.push_back(new Edge(v2,v1,weight));
      numEdges--;
    }
  }

  return true;
}

Graph.h

#ifndef GRAPH_H_
#define GRAPH_H_

#ifndef NULL
#define NULL 0
#endif

#include <vector>
#include <cmath>
#include <iostream>
#include <string>
#include <sstream>
#include <unordered_map>

// not always the best idea but we're lazy today
using namespace std;

// Reserve the name for each Class to allow recursive definition
class Vertex;
class Edge;

#ifndef DEFAULT_VERTEX_STATUS
#define UNKNOWN 0
#define IDENTIFIED 1
#define VISITED 2
#define DEFAULT_VERTEX_STATUS 0
#endif

class Edge {
  public:
    Vertex * source;
    Vertex * target;
    double weight;

    Edge(Vertex * pSource, Vertex * pTarget, double pWeight)
        : source(pSource), target(pTarget), weight(pWeight){ }

    ~Edge() {}
};

// a simple Vertex that has an id and label and status marker
class Vertex {
  public:
  int id; // id represents the order this Vertex was added to a graph
  string label; // label must be unique
  int status; // sometimes called color in algorithms, helps with processing

  vector<Edge*> edges;
  Vertex(int pId, string pLabel) :
    id(pId), label(pLabel), status(DEFAULT_VERTEX_STATUS) {}

  ~Vertex() {
    for (auto iter = edges.begin();
          iter != edges.end(); iter++) {
      Edge * l = *iter;
      delete l;
    }
  }
};

// a Graph is just a lookup "table" of vertex label to Vertex
class Graph {
  public:
  unordered_map<string,Vertex*> vertices;

  Graph(){}
  ~Graph() {
    for (auto iter = vertices.begin();
              iter != vertices.end(); iter++) {
      Vertex * v = iter->second;
      delete v;
    }
  }

  string toString() const {
    stringstream s;
    for (auto iterV = vertices.begin();
          iterV != vertices.end(); iterV++) {
      Vertex * v = iterV->second;
      s << v->label << ": ";
      for (auto iterE = v->edges.begin();
            iterE != v->edges.end(); iterE++) {
          Edge * e = *iterE;
          s << e->target->label << "(" << e->weight << ") ";
      }
      s << endl;
    }

    return s.str();

  }
};

bool readDirectedGraphFromFile(Graph & g, char * fileName);
//bool createDirectedGraph(Graph & g, unordered_map<std::string, Coordinates*> locations, unordered_map<std::string, CourseSection*> courseSections);

#endif // GRAPH_H_

locations.txt

12
Trabant 39.682292 -75.754065 
Memorial 39.679067 -75.752003
Alison 39.678654 -75.750741
Purnell 39.680401 -75.755116
Kirkbride 39.681234 -75.754315
Willard 39.683443 -75.755109
Gore 39.680383 -75.752911
Smith 39.680513 -75.754176
Brown 39.679627 -75.751337
Redding 39.676439, -75.747139
Read 39.690543, -75.758259
Sharp 39.682065, -75.752072
12
Trabant 39.682292 -75.754065 
Memorial 39.679067 -75.752003
Alison 39.678654 -75.750741
Purnell 39.680401 -75.755116
Kirkbride 39.681234 -75.754315
Willard 39.683443 -75.755109
Gore 39.680383 -75.752911
Smith 39.680513 -75.754176
Brown 39.679627 -75.751337
Redding 39.676439, -75.747139
Read 39.690543, -75.758259
Sharp 39.682065, -75.752072

main.cpp

#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <limits>
#include <algorithm>
#include <stack>
#include "Graph.h"
#include "Coordinates.h"
#include "CourseSection.h"

#define NUM_COURSES_PER_SEMESTER 5

using namespace std;

float distance(Coordinates* c1, Coordinates* c2) {
	double PI = 4.0 * atan(1.0);

	double dlat1 = c1->latitude * (PI/180);
	double dlat2 = c2->latitude * (PI/180);
	double dlon1 = c1->longitude * (PI/180);
	double dlon2 = c2->longitude * (PI/180);

	double delLon = dlon1 - dlon2;
	double delLat = dlat1 - dlat2;

	double aHarv = pow(sin(delLat/2.0),2.0)+cos(dlat1)*pow(sin(delLon/2),2);
	double cHarv = 2*atan2(sqrt(aHarv), sqrt(1.0-aHarv));

	const double earthRadius = 3963.19;

	double result = earthRadius*cHarv;
	return fabs(result);
}

float distanceBetweenBuildings(
		string building1, 
		string building2, 
		unordered_map<string, Coordinates*> locations) {
	//cout << distance(locations[building1], locations[building2]) << endl;
	return distance(locations[building1], locations[building2]);
}

bool createDirectedGraph(
		Graph & g, 
		unordered_map<std::string, Coordinates*> locations, 
		unordered_map<std::string, CourseSection*> courseSections) {
	for (auto it : courseSections) {
		g.vertices[it.first] = new Vertex(g.vertices.size(), it.first);		
	}
	
	for (auto v : g.vertices) {
		for (auto otherV : g.vertices) {
			if (courseSections[v.second->label]->course !=
			    courseSections[otherV.second->label]->course &&
			    courseSections[otherV.second->label]->startsAfter(
				    courseSections[v.second->label])) {
				v.second->edges.push_back(
						new Edge(
							v.second, 
							otherV.second, 
							distance(
								locations[courseSections[v.second->label]->location], 
								locations[courseSections[otherV.second->label]->location])));
			}
		}
	}
}

bool isInside(string str, char c)
{
	return str.find(c) != std::string::npos;
}

string scheduleToString(vector<string> & classesInThisSchedule);

float findPathLength(
		vector<string> & classesInThisSchedule, 
		unordered_map<string, Coordinates *> locations, 
		unordered_map<string, CourseSection *> courseSections, 
		string placeOfResidence) {
	float totalDistance = 0.0;
	char currentDay = 'M'; //;
	string currentLocation = placeOfResidence;
	while (currentDay != 'S') {
		for (auto courseSection : classesInThisSchedule) {
			//if (courseSections[courseSection]->days[0] != currentDay) {
			//	totalDistance += distanceBetweenBuildings(
			//			placeOfResidence, 
			//			courseSections[courseSection]->location, 
			//			locations);
			//}
			//cout << "distance from " << currentLocation << " to " << courseSections[courseSection]->location << ": " << distanceBetweenBuildings(
			//		currentLocation,
			//		courseSections[courseSection]->location,
			//	locations)
//<< endl;
			if (isInside(courseSections[courseSection]->days, currentDay)) {
				totalDistance += distanceBetweenBuildings(
					currentLocation,
					courseSections[courseSection]->location,
				locations);
				currentLocation = courseSections[courseSection]->location;
			}
		}
		totalDistance += distanceBetweenBuildings(
			currentLocation,
			placeOfResidence,
			locations);
		currentLocation = placeOfResidence;
		switch(currentDay) {
			case 'M':
				currentDay = 'T';
				break;
			case 'T':
				currentDay = 'W';
				break;
			case 'W':
				currentDay = 'R';
				break;
			case 'R':
				currentDay = 'F';
				break;
			case 'F':
				currentDay = 'S';
				break;
			default:
				currentDay = 'S';
				break;
		}
	}
	//cout << "Path " << scheduleToString(classesInThisSchedule) << " length: " << totalDistance << endl;
	return totalDistance;
	
}

bool labelInList(string word, vector<string> & lst) {
	bool result = false;
	for (auto i : lst) {
		result = result | 0 == strcmp(
				word.substr(0, 7).c_str(), 
				i.substr(0, 7).c_str());
	}
	return result;
}

string scheduleToString(vector<string> & classesInThisSchedule) {
	stringstream s;
	for (auto i : classesInThisSchedule) {
		s << i;
		s << ", ";
	}
	return s.str();

}

bool noScheduleConflicts(
		string courseSection, 
		vector<string> classesInThisSchedule,
		unordered_map<string, CourseSection *> courseSections) {
	for (auto c : classesInThisSchedule) {
		if (courseSections[c]->startsAfter(courseSections[courseSection]) ||
				courseSections[courseSection]->startsAfter(courseSections[c])) {

		} else {
			return false;
		}
	}
}

float shortestScheduleStartingAtVertex(
		Vertex * v, 
		vector<string> & classesInThisSchedule, 
		vector<string> & classesInShortestSchedule, 
		float runningMin, 
		unordered_map<string, Coordinates *> locations, 
		unordered_map<string, CourseSection *> courseSections, 
		string placeOfResidence) {
	//cout << "At vertex: " << v->label << endl;
	//cout << "runningMin: " << runningMin << endl;
	for (auto e : v->edges) {
		if (!labelInList(e->target->label, classesInThisSchedule) &&
				noScheduleConflicts(e->target->label, classesInThisSchedule, courseSections)) {
			classesInThisSchedule.push_back(e->target->label);
			
			if (classesInThisSchedule.size() == NUM_COURSES_PER_SEMESTER) {
	//cout << "Course list is: " << classesInThisSchedule.size()<< ": "  << scheduleToString(classesInThisSchedule) << endl;
				float x = findPathLength(
						classesInThisSchedule, 
						locations, 
						courseSections, 
						placeOfResidence);
				//cout << x << endl;
				if (x < runningMin) {
					//cout << "old shortest path: " << runningMin << endl;
					//cout << "new shortest path: " << x << endl;
					runningMin = x;
					classesInShortestSchedule = classesInThisSchedule;
				}
			} else {
				runningMin = shortestScheduleStartingAtVertex(
						e->target, 
						classesInThisSchedule, 
						classesInShortestSchedule, 
						runningMin, 
						locations, 
						courseSections, 
						placeOfResidence);
			}
			classesInThisSchedule.pop_back();
		}
	}
	//cout << "end foreach" << endl;
	return runningMin;
}

float findShortestPath(
		Graph & g, 
		unordered_map<string, Coordinates*> & locations, 
		unordered_map<string, CourseSection*> & courseSections, 
		vector<string> & classesInShortestSchedule, 
		string placeOfResidence) {
	vector<string> classesInThisSchedule;
	float minWalkingDistance = numeric_limits<float>::max();


	vector<string> tmpClassesInShortestSchedule;
	for (auto v : g.vertices) {
		//cout << "Starting at vertex: " << v.second->label << ", the shortest path is:" ; 
		classesInThisSchedule.push_back(v.second->label);
		float distance = shortestScheduleStartingAtVertex(
				v.second, 
				classesInThisSchedule, 
				tmpClassesInShortestSchedule, 
				numeric_limits<float>::max(), 
				locations, 
				courseSections, 
				placeOfResidence);
		//cout << distance << endl;
		if (distance < minWalkingDistance) {
			minWalkingDistance = distance;
			classesInShortestSchedule = tmpClassesInShortestSchedule;
		}	
		classesInThisSchedule.pop_back();
	}

	return minWalkingDistance;
}


int main(int argc, char **argv) {
	cout.precision(8);

	string placeOfResidence = argv[3];
	 
	bool verbose = false;
	if (argc > 4) {
		verbose = (strcmp(argv[4], "verbose") == 0);
		verbose = verbose | strcmp(argv[4], "v") == 0;
	}

	Graph g;

	if (verbose) {
		cout << argv[1] << endl;
		cout << argv[2] << endl;
		cout << argv[3] << endl;
		cout << endl;
	}

	unordered_map<std::string, Coordinates*> locations;
	
	readUnorderedMapFromFile(locations, argv[1]);
	if (verbose) {
		for (auto iter = locations.begin(); iter != locations.end(); ++iter) {
			cout << iter->first << ": " << iter->second->toString();
		}
	}

	unordered_map<std::string, CourseSection*> courseSections;	
	readCourseSectionMapFromFile(courseSections, argv[2]);

	if (verbose) {
		for (auto iter = courseSections.begin(); iter != courseSections.end(); ++iter) {
			cout << iter->first << ": " << iter->second->toString() << endl;
		}
	}

	createDirectedGraph(g, locations, courseSections);
	
	if (verbose) {
		cout << g.toString() << endl;
	}

	vector<string> classesInShortestSchedule;


	float distanceWalked = findShortestPath(
			g, 
			locations, 
			courseSections, 
			classesInShortestSchedule, 
			placeOfResidence);
	cout << "The class schedule that requires the minimum distance travelled is " << 
		scheduleToString(classesInShortestSchedule);
	cout << "and this schedule requires walking " << distanceWalked << " miles." << endl;

	for (auto i: classesInShortestSchedule) {
		cout << courseSections[i]->toString() << endl;
	}
	

	locations.clear();
	courseSections.clear();
	return 0;
}

Makefile

#CXX = g++
CXXFLAGS = -O2 -std=c++11

LIBS =
LDLIBS =
INCLUDES =

# force clean build every time
all: clean main

main: Graph.o Coordinates.o CourseSection.o main.o
	$(CXX) $^ -o $@

# name a variable cources for all source files
%.o: %.cpp
	$(CXX) $(CXXFLAGS) -c $< -o $@

clean: 
	rm -f *.o
	rm -f *.exe