/**
 * A template graph and bfs algorithm
 *
 * Author: Erel Segal
 * Date: 2010-10-17
 */

#include <iostream>
#include <map>
#include <set>
#include <string>
#include <queue>
using namespace std;

typedef unsigned int uint;

/**
 * A graph that stores edges in adjacency list.
 */
template <class VertexKey, class Vertex> class Graph {
	typedef set<VertexKey> AdjacencyList;
	typedef map<VertexKey,Vertex> VertexMap;
	typedef map<VertexKey,AdjacencyList> EdgeMap;

	VertexMap myVertices;
	EdgeMap myOutgoingEdges;

public:
	Graph<VertexKey,Vertex> () {}

	Graph<VertexKey,Vertex>& addVertex(VertexKey key, const Vertex& newVertex) {
		myVertices[key]=newVertex;
		return *this;
	}

	Graph<VertexKey,Vertex>& addEdge  (VertexKey keyFrom, VertexKey keyTo) {
		// add the two vertices if they doesn't exist:
		myVertices[keyFrom];
		myVertices[keyTo];
		myOutgoingEdges[keyFrom].insert(keyTo);
		return *this;
	}

	void printOutgoingEdges(VertexKey key, ostream& out) {
		out << key << " -> ";
		myVertices[key];  // may add a new vertex if not exists
		const AdjacencyList& targets = myOutgoingEdges[key];
		typename AdjacencyList::const_iterator f;
		for (f=targets.begin(); f!=targets.end(); ++f) {
			out << " " << (*f);
		}
		out << endl;
	}

	void printIncomingEdges(VertexKey key, ostream& out) {
		out << key << " <- ";
		myVertices[key];  // may add a new vertex if not exists

		typename EdgeMap::const_iterator e;
		for (e=myOutgoingEdges.begin(); e!=myOutgoingEdges.end(); ++e) {
			VertexKey currentSource = e->first;
			const AdjacencyList& currentTargets = e->second;
			if (currentTargets.count(key)) {
				out << currentSource << " ";
			}
		}
		out << endl;
	}

	void print(ostream& out) const {
		out << "VERTICES:" << endl;
		out << myVertices;
		out << "EDGES:" << endl;
		typename EdgeMap::const_iterator e;
		for (e=myOutgoingEdges.begin(); e!=myOutgoingEdges.end(); ++e) {
			VertexKey currentSource = e->first;
			const AdjacencyList& currentTargets = e->second;
			typename AdjacencyList::const_iterator f;
			for (f=currentTargets.begin(); f!=currentTargets.end(); ++f) {
				out << "  "  << currentSource << "-" << (*f) << endl;
			}
		}
	}

	friend ostream& operator<< (ostream& out, Graph<VertexKey,Vertex> g) {
		g.print(out);
		return out;
	}
	

	/// @see http://w...content-available-to-author-only...t.org/doc/libs/1_43_0/libs/graph/doc/breadth_first_search.html
	void breadth_first_search(VertexKey source, map<VertexKey,uint>& distances) const {
		enum {white, gray, black};
		map<VertexKey,int> vertexColor;
		queue<VertexKey> vertexQueue;

		// Initialize vertices:
		typename VertexMap::const_iterator v;
		for (v=myVertices.begin();  v!=myVertices.end();  ++v) {
			vertexColor[v->first] = white;
			distances[v->first] = 0-1; // max uint
		}

		// Initlaize source:
		vertexColor[source] = gray;
		distances[source] = 0;
		vertexQueue.push(source);

		// Loop over all vertices:
		while (!vertexQueue.empty()) {
			VertexKey current = vertexQueue.front();     // finish a vertex
			vertexQueue.pop();
			uint current_distance = distances[current];

			// Loop over all outgoing edges of the current vertex:
			const AdjacencyList& nextTargets = (myOutgoingEdges.find(current))->second;
			typename AdjacencyList::const_iterator neighbour;
			for (neighbour=nextTargets.begin(); neighbour!=nextTargets.end(); ++neighbour) {
				if (vertexColor[*neighbour]==white) {   // a tree edge
					vertexColor[*neighbour] = gray;
					distances[*neighbour] = current_distance+1;
					vertexQueue.push(*neighbour);
				} else {                        // a non-tree edge
					// don't do anything
				}
			}

			vertexColor[current] = black;   // finish a vertex
		}

		// cleanup:
		for (v=myVertices.begin();  v!=myVertices.end();  ++v) {
			if (distances[v->first] == 0-1) // max uint
				distances.erase(v->first);
		}
	}
};


template <class K, class T> ostream& operator<< (ostream& out, const map<K,T>& theMap) {
	typename map<K,T>::const_iterator v;
	for (v=theMap.begin();  v!=theMap.end();  ++v) {
		out << "  "  << v->first << ": " << v->second << endl;
	}
	return out;
}


int main() {
	Graph <char,bool> g;
	g.addEdge('a','b').addEdge('b','c').addEdge('c','d').addEdge('d','a').addEdge('a','c');
	cout << g << endl;
	g.printOutgoingEdges('a',cout);
	g.printOutgoingEdges('b',cout);
	g.printOutgoingEdges('c',cout);
	g.printOutgoingEdges('d',cout);
	g.printOutgoingEdges('e',cout);
	cout << endl;
	g.printIncomingEdges('a',cout);
	g.printIncomingEdges('b',cout);
	g.printIncomingEdges('c',cout);
	g.printIncomingEdges('d',cout);
	g.printIncomingEdges('e',cout);
	cout << endl;

	map<char,uint> distances;
	g.breadth_first_search('a', distances);
	cout << "BFS from a: " << endl << distances << endl;
	g.breadth_first_search('b', distances);
	cout << "BFS from b: " << endl << distances << endl;
	g.breadth_first_search('c', distances);
	cout << "BFS from c: " << endl << distances << endl;
	g.breadth_first_search('d', distances);
	cout << "BFS from d: " << endl << distances << endl;
	g.breadth_first_search('e', distances);
	cout << "BFS from e: " << endl << distances << endl;
}