#include <limits>
#include <iostream>
#include <fstream>
#include <strstream>
#include <exception>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <list>
using namespace std;

const int INFINITY=INT_MAX;

class Vertex {
private:
	typedef list< pair<Vertex*, int> > AList;
	string name;
	AList adjacent;
// gebruikt door shortest-path algoritmes
	Vertex* prev;
	int dist;
	unsigned int scratch;
public:
	Vertex(const string& name);
	void addEdge(Vertex* v, int cost);
// gebruikt door shortest-path algoritmes
	typedef AList::const_iterator const_iterator;
	const_iterator begin() const;
	const_iterator end() const;
	void reset();
	int distance() const;
	void setDistance(int d);
	unsigned int getScratch() const;
	void scratchInc();
	void scratchDec();
	void setPrev(Vertex* v);
	void printPath() const;
};

class Graph {
public:
	Graph();
	~Graph();
	void addEdge(const string& sourceName, const string& destName, int cost);
	void printPath(const string& destName) const;
	void unweighted(const string& startName);
	void dijkstra(const string& startName);
	void negative(const string& startName);
	void acyclic(const string& startName);
private:
	Vertex* getVertex(const string& vertexName);
	Vertex* findVertex(const string& vertexName) const;
	void reset();
	typedef map<string, Vertex*> VMap;
	VMap vm;
	Graph(const Graph& rhs);
	Graph& operator=(const Graph& rhs);
};

Vertex::Vertex(const string& name): name(name) {
	reset();
}

void Vertex::reset() {
	dist=INFINITY;
	prev=0;
	scratch=0;
}

void Vertex::addEdge(Vertex* v, int cost) {
	adjacent.push_back(make_pair(v, cost));
}

int Vertex::distance() const {
	return dist;
}

unsigned int Vertex::getScratch() const {
	return scratch;
}

void Vertex::setDistance(int d) {
	dist=d;
}

void Vertex::scratchInc() {
	++scratch;
}

void Vertex::scratchDec() {
	--scratch;
}

void Vertex::setPrev(Vertex* v) {
	prev=v;
}

void Vertex::printPath() const {
	if (prev) {
		prev->printPath();
		cout<<" to ";
	}
	cout<<name;
}

Vertex::const_iterator Vertex::begin() const {
	return adjacent.begin();
}

Vertex::const_iterator Vertex::end() const {
	return adjacent.end();
}

Graph::Graph() {
}

Graph::~Graph() {
	for (VMap::const_iterator itr(vm.begin()); itr!=vm.end(); ++itr)
		delete itr->second;
}

void Graph::reset() {
	for (VMap::const_iterator itr(vm.begin()); itr!=vm.end(); ++itr)
		itr->second->reset();
}

Vertex* Graph::getVertex(const string& vertexName) {
	VMap::const_iterator itr(vm.find(vertexName));
	if (itr==vm.end()) {
		Vertex* newv(new Vertex(vertexName));
		vm[vertexName]=newv;
		return newv;
	}
	return itr->second;
}

Vertex* Graph::findVertex(const string& vertexName) const {
	VMap::const_iterator itr(vm.find(vertexName));
	if (itr==vm.end())
		throw runtime_error(vertexName + " is not a vertex in this graph");
	return itr->second;
}

void Graph::addEdge(const string& sourceName, const string& destName, int cost) {
	Vertex* v(getVertex(sourceName));
	Vertex* w(getVertex(destName));
	v->addEdge(w, cost);
}

void Graph::printPath(const string& destName) const {
	Vertex* dest(findVertex(destName));
	if (dest->distance()==INFINITY)
		cout<<destName<<" is unreachable";
	else {
		cout<<"(Cost is: "<<dest->distance()<<") ";
		dest->printPath();
	}
	cout<<endl;
}

void Graph::unweighted(const string& startName)	{
	reset();
	Vertex* start(findVertex(startName));
	start->setDistance(0);
	queue<Vertex*> q;
	q.push(start);
	while (!q.empty()) {
		Vertex* v(q.front());
		q.pop();
		for (Vertex::const_iterator i(v->begin()); i!=v->end(); ++i) {
			Vertex* w(i->first);
			if (w->distance()==INFINITY) {
				w->setDistance(v->distance()+1);
				w->setPrev(v);
				q.push(w);
			}
		}
	}
}

class GreaterDistance {
public:
	bool operator()(const Vertex* l, const Vertex* r) {
		return l->distance()>r->distance();
	}
};

void Graph::dijkstra(const string& startName) {
	reset();
	Vertex* start(findVertex(startName));
	start->setDistance(0);
	priority_queue<Vertex*, vector<Vertex*>, GreaterDistance> pq;
	pq.push(start);
	while (!pq.empty()) {
		Vertex* v(pq.top());
		pq.pop();
		for (Vertex::const_iterator i(v->begin()); i!=v->end(); ++i) {
			Vertex* w(i->first);
			int cvw(i->second);
			if (cvw<0)
				throw runtime_error("Graph has negative edges");
			if (w->distance()>v->distance()+cvw) {
				w->setDistance(v->distance()+cvw);
				w->setPrev(v);
				if (w->getScratch()==0) {
					w->scratchInc();
					pq.push(w);
				}
			}
		}
	}
}

void Graph::negative(const string& startName) {
	reset();
	Vertex* start(findVertex(startName));
	start->setDistance(0);
	queue<Vertex*> q;
	start->scratchInc();
	q.push(start);
	while (!q.empty()) {
		Vertex* v(q.front());
		q.pop();
		v->scratchInc();
		if (v->getScratch()/2>vm.size())
			throw runtime_error("Negative cycle detected");
		for (Vertex::const_iterator i(v->begin()); i!=v->end(); ++i) {
			Vertex* w(i->first);
			int cvw(i->second);
			if (w->distance()>v->distance()+cvw) {
				w->setDistance(v->distance()+cvw);
				w->setPrev(v);
				if (w->getScratch()%2==0) {
					w->scratchInc();
					q.push(w);
				}
				w->scratchInc();
				w->scratchInc();
			}
		}
	}
}

void Graph::acyclic(const string& startName) {
	reset();
	Vertex* start(findVertex(startName));
	start->setDistance(0);
	queue<Vertex*> q;
	for (VMap::const_iterator itr(vm.begin()); itr!=vm.end(); ++itr) {
		Vertex* v(itr->second);
		for (Vertex::const_iterator i(v->begin()); i!=v->end(); ++i)
			i->first->scratchInc();
	}
	for (VMap::const_iterator itr(vm.begin()); itr!=vm.end(); ++itr) {
		Vertex* v(itr->second);
		if (v->getScratch()==0)
			q.push(v);
	}
	VMap::size_type iterations;
	for (iterations=0; !q.empty(); ++iterations) {
		Vertex* v(q.front());
		q.pop();
		for (Vertex::const_iterator i(v->begin()); i!=v->end(); ++i) {
			Vertex* w(i->first);
			int cvw(i->second);
			w->scratchDec();
			if (w->getScratch()==0) {
				q.push(w);
			}
			if (v->distance()==INFINITY)
				continue;
			if (w->distance()>v->distance()+cvw) {
				w->setDistance(v->distance()+cvw);
				w->setPrev(v);
			}
		}
	}
	if (iterations!=vm.size())
		throw runtime_error("Graph has a cycle!");
}

bool processRequest(istream& in, Graph& g) {
	cout<<"Enter start node: ";
	string startName;
	if (!(in>>startName))
		return false;
	cout<<"Enter destination node: ";
	string destName;
	if (!(in>>destName))
		return false;
	cout<<"Enter algorithm u=nweighted, d=dijkstra, n=negative or a=acyclic: ";
	char alg;
	in>>alg;
	try {
		switch (alg) {
			case 'u':
			case 'U': g.unweighted(startName); break;
			case 'd':
			case 'D': g.dijkstra(startName); break;
			case 'n':
			case 'N': g.negative(startName); break;
			case 'a':
			case 'A': g.acyclic(startName); break;
			case 'q':
			case 'Q': return false;
			default: throw runtime_error("Wrong input, try again.");
		}
		g.printPath(destName);
	}
	catch(const runtime_error& e) {
		cerr<<e.what()<<endl;
	}
	return true;
}

int main(int argc, char* argv[]) {
	string fileName;
	if (argc>2) {
		cerr<<"Usage: "<<argv[0]<<" {graphfile}"<<endl;
		cin.get();
		return 1;
	}
	else if (argc==2) {
		fileName=argv[1];
	}
	else if (argc==1) {
		const int pasen(0);
		const int pinksteren(1);
		while(pasen!=pinksteren) {
			do {
				cout<<"Choose graph p=positive(fig 15.1), n=negative(fig 15.29) or a=acyclic(fig 15.32): ";
				char c;
				cin>>c;
				switch (c) {
					case 'p':
					case 'P': fileName="graph_15_1.txt"; break;
					case 'n':
					case 'N': fileName="graph_15_29.txt"; break;
					case 'a':
					case 'A': fileName="graph_15_32.txt"; break;
					case 'q':
					case 'Q': cin.get(); exit(0);
					default: cout<<"Wrong input, try again."<<endl;
				}
			} while (fileName.length()==0);
			ifstream inFile(fileName.c_str());
			if (!inFile) {
				cerr<<"Cannot open "<<fileName<<endl;
				cin.get();
				return 1;
			}
			cout<<"Reading file... "<<endl;

			Graph g;

			string oneLine;
			while (!getline(inFile, oneLine).eof()) {
				string source, dest;
				int cost;
				istrstream st(oneLine.c_str(), oneLine.length());
				st>>source>>dest>>cost;
				if (st.fail())
					cerr<<"Bad line: "<<oneLine<<endl;
				else
					g.addEdge(source, dest, cost);
			}
			cout<<"File read"<<endl<<endl;
			processRequest(cin, g);
		}
	}
	return 0;
}