Graph implementation

graph.cpp

// graph.cpp
//
// Author: Jon Gautsch
//
// Contact: [email protected]
//
// Course: CSE 30331, Fall 2013

#include "graph.h"
#include <sstream>

using namespace std;

Graph::Graph() {}

void Graph::addNode(string name)
{
	if (!my_graph.count(name)) {
		Node temp;
		temp.name = name;
		my_graph[name] = temp;
	}
}


void Graph::removeNode(string name)
{
	if (this -> nodeExists(name)) {
		this -> removeAllEdgesFrom(name);
		this -> removeAllEdgesTo(name);
		my_graph.erase(name);
	}
}


void Graph::removeAllEdgesFrom(string name)
{
	if (this -> nodeExists(name)) {
		(my_graph.find(name) -> second).connections.clear();
	}

}


void Graph::removeAllEdgesTo(string name)
{
	for(main_iterator = my_graph.begin(); main_iterator != my_graph.end(); main_iterator++) {
		if ((main_iterator -> second).connections.count(name)) {
			(main_iterator -> second).connections.erase(name);
		}
	}
}


bool Graph::nodeExists(string name) {
	if (my_graph.count(name) != 0)
		return true;
	else
		return false;
}


bool Graph::edgeExists(string from, string to)
{
	if (this -> nodeExists(from) && this -> nodeExists(to)) {
		if ((my_graph.find(from) -> second).connections.count(to))
			return true;
		else
			return false;
	}
	return false;
}


void Graph::addOrUpdateEdge(string from, string to, int distance)
{
	if (this -> nodeExists(from) && this -> nodeExists(to)) {
		// If that connection already exists, update distance
		if (this -> edgeExists(from, to)) {
			((my_graph.find(from) -> second).connections.find(to) -> second).distance = distance;
		} else {
			// connection doesn't exist, so create it
			Edge temp;
			temp.distance = distance;
			temp.to = to;
			temp.from = from;
			(my_graph.find(from) -> second).connections[to] = temp;
		}
	}
}



int Graph::getEdgeDistance(string from, string to)
{
	if (this -> edgeExists(from, to)) {
		Edge *temp = this -> getEdge(from, to);
		return temp ->distance;
	}
	return 0;
}

Edge* Graph::getEdge(string from, string to)
{
	if (this -> edgeExists(from, to)) {
		return &((my_graph.find(from) -> second).connections.find(to) -> second);
	}
}


void Graph::removeEdge(string from, string to)
{
	if (my_graph.count(from)) {
		if (this -> edgeExists(from, to)) {
			(my_graph.find(from) -> second).connections.erase(to);
		}
	}
}


void Graph::print()
{
	cout << "size: " << my_graph.size() << endl;
	cout << "Nodes:" << endl;
	for(main_iterator = my_graph.begin(); main_iterator != my_graph.end(); main_iterator++) {
		cout << " - " << (main_iterator -> second).name << endl;
	}
	cout << "Edges:" << endl;
	for(main_iterator = my_graph.begin(); main_iterator != my_graph.end(); main_iterator++) {
		if ((main_iterator -> second).connections.size() != 0) {
			Node temp = (main_iterator -> second);
			for(sub_iterator = temp.connections.begin(); sub_iterator != temp.connections.end(); sub_iterator++) {
				cout << " - ";
				cout << temp.name << " -> " << (sub_iterator -> second).to << "; " << (sub_iterator -> second).distance << endl;
			}
		}
	}
}


/**************************************************************/
// 		QUEUE RELATED FUNCTIONS
/**************************************************************/
void Graph::addToStationedQueue(string node, string value)
{
	(my_graph.find(node) -> second).stationed.push_back(value);
}

string Graph::getNodeQueueFront(string node)
{
	if ( !(my_graph.find(node) -> second).stationed.empty() )
		return (my_graph.find(node) -> second).stationed.front();
	else
		return "";
}

void Graph::addToTravelingQueue(string from, string to, string value)
{
	Edge *temp = this -> getEdge(from, to);
	(temp -> traveling).push_back(value);
}

string Graph::getEdgeQueueFront(string from, string to)
{
	if ( !((this -> getEdge(from, to)) -> traveling).empty() )
		return ((this -> getEdge(from, to)) -> traveling).front();
	else
		return "";
}

void Graph::popFrontNodeQueue(string node)
{
	if ( !(my_graph.find(node) -> second).stationed.empty() )
		(my_graph.find(node) -> second).stationed.pop_front();
}

void Graph::popFrontEdgeQueue(string from, string to)
{
	if ( !((this -> getEdge(from, to)) -> traveling).empty() )
		((this -> getEdge(from, to)) -> traveling).pop_front();
}

void Graph::findAndEliminateNodeQueueValue(string value)
{
	deque<string>::iterator i;

	for(main_iterator = my_graph.begin(); main_iterator != my_graph.end(); main_iterator++) {
		Node *temp = &(main_iterator -> second);
		for( i = (temp -> stationed).begin(); i != (temp -> stationed).end();) {
			if ((*i) == value) {
				i = (temp -> stationed).erase(i); // erase returns the next iterator
			} else
				++i;
		}
	}
}

graph.h

// graph.h
//
// Author: Jon Gautsch
//
// Contact: [email protected]
//
// Course: CSE 30331, Fall 2013

#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <map>

using namespace std;

struct Edge {
	string to;
	string from;
	int distance;
	deque<string> traveling;
};

struct Node {
	string name;
	map<string, Edge> connections;
	deque<string> stationed;
};

class Graph {
public:


	Graph();
	Edge* getEdge(string from, string to);
	Node getNode(string name);

	void addNode(string name);
	void removeNode(string name);
	void removeAllEdgesFrom(string name);
	void removeAllEdgesTo(string name);
	bool nodeExists(string name);
	bool edgeExists(string from, string to);
	void addOrUpdateEdge(string from, string to, int distance);
	int getEdgeDistance(string from, string to);
	void removeEdge(string from, string to);
	void print();

	void addToStationedQueue(string node, string value);
	string getNodeQueueFront(string node);
	void addToTravelingQueue(string from, string to, string value);
	string getEdgeQueueFront(string from, string to);
	void popFrontNodeQueue(string node);
	void popFrontEdgeQueue(string from, string to);
	void findAndEliminateNodeQueueValue(string value);

private:

	map<string, Node>::iterator main_iterator;
	map<string, Edge>::iterator sub_iterator;

	map<string, Node> my_graph;

};

my_train_sim.h

// train_sim.h
// Jon Gautsch
// Author: Raul Santelices
//
// Contact: [email protected]
//
// In this file you can add variables, functions, classes, etc. as needed.
// Do NOT remove or modify variables, functions, etc. already provided here.
//
// Course: CSE 30331, Fall 2013


#ifndef TRAIN_SIM_H
#define TRAIN_SIM_H

#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <utility>
#include <vector>
#include <map>
#include "graph.h"

using namespace std;


// Class representing a network of train stations and trains stationed or moving among connected stations
// Rules for PA3:
//  1. For the network of stations, you must either (a) write your own graph code from scratch or (b) use the Boost graph library
//  2. You must use the Train struct (defined below) to store each train's information
//  3. You must use stl::queue containers to store trains (or pointers to trains) and place them in station vertices in your graph
//       (Hint: if you use Boost graphs, use vertex properties to associate the queues to vertices)
//  4. In addition to train_sim.cxx, you can modify train_sim.h (do NOT change what is already here though) and the Makefile and even add new files
class TrainSimulator {
public:
	// *** DO NOT MODIFY ANY OF THE FOLLOWING TYPEDEFS AND FUNCTIONS ***

	// TYPEDEFS
	typedef unsigned int uint;
	typedef uint Distance;

	// CONSTRUCTORS
	TrainSimulator(); // *** NOT GRADED because it's given to you

	// SIMULATION ACTIONS
	void step();
	void departNextTrain(const string& fromStation, const string& toStation);

	// STATION CREATION, CONNECTIVITY, & REMOVAL
	void addStation(const string& name);
	void removeStation(const string& name);
	void connectStations(const string& from, const string& to, Distance distance);
	void disconnectStations(const string& from, const string& to);

	// STATION-SPECIFIC QUERIES
	bool stationExists(const string& name);
	bool stationsConnected(const string& from, const string& to);
	Distance connectionLength(const string& from, const string& to);

	// TRAIN INSERTION, MODIFICATION, & REMOVAL
	void addTrain(const string& name, uint wagons, const string& station);
	void removeTrain(const string& name);
	void addWagon(const string& train);
	void removeWagon(const string& train);

	// TRAIN-SPECIFIC QUERIES
	bool trainExists(const string& name) const;
	bool trainTraveling(const string& name) const;
	uint numberWagons(const string& train) const;
	const string& whereStationed(const string& train) const;
	const string& trainOrigin(const string& train) const;
	const string& trainDestination(const string& train) const;
	Distance distanceTraveled(const string& train) const;

	void resetTrainFlags(const string& train);

	void print(ostream& outs = cout);  // *** NOT GRADED; use it to help yourself visualize your solution

	//  *** you can add your own public members variables, as needed

private:
	// PRIVATE TYPES
	struct Train {  // *** IMPORTANT: You must use this structure to handle trains and to store them (or pointers to them) in stl::queue containers ***

		//  *** do NOT change the following three variables
		string name; 				// name of the train; doesn't change
		uint wagons; 				// number of wagons in this train; always greater than 0
		Distance traveled; 			// distance traveled so far (if traveling)

		bool traveling;				// boolean for if the train is traveling
		bool flagged_for_removal;	// flag for if the train will be removed upon arriving at station
		bool flagged_for_wagon_removal; // flagged for removing wagon

		string station;				// the station it's at, or traveling to
		string destination_station; // the station it's traveling to
		string origin_station;		// the station it originated from
		int distance_left;			// the distance to the station it's traveling to
	};

	map<string, Train> trains_map;
	map<string, Train>::iterator it_type;

	Graph stations_graph;

};

#endif // TRAIN_SIM_H