/**
 * A graph where the nodes are integers, and an implementation of the 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;
typedef set<uint> AdjacencyList;
const uint MAXINT = 999999999u;

template <class Iterator> ostream& print (Iterator iFrom, Iterator iTo) {
	for (; iFrom!=iTo; ++iFrom) cout << *iFrom << " ";
	return (cout << endl);
}

template <class T> ostream& operator<< (ostream& out, const vector<T>& theVector) {
	return print (theVector.begin(), theVector.end());
}

template <class T> ostream& operator<< (ostream& out, const set<T>& theVector) {
	return print (theVector.begin(), theVector.end());
}



/**
 * A graph where the vertices are integers; stores edges in adjacency list.
 */
class IntegerGraph {
	vector<AdjacencyList> myVertices;

public:
	IntegerGraph (uint nVertices): myVertices(nVertices) {}
	uint size() const { return myVertices.size(); }

	IntegerGraph& addEdge (uint iFrom, uint iTo) {
		if (iFrom >= size()) {
			throw string("trying to add an edge from a nonexisting vertex index");
		}
		if (iTo >= size()) {
			throw string("trying to add an edge to a nonexisting vertex index");
		}
		myVertices[iFrom].insert(iTo);
		return *this;
	}

	void createClique() {     // for testing
		for (uint iFrom=0; iFrom<size(); ++iFrom) {
			for (uint iTo=0; iTo<size(); ++iTo) {
				if (iFrom!=iTo)
					addEdge(iFrom,iTo);
			}
		}
	}

	void printOutgoingEdges(uint iFrom, ostream& out) const {
		out << iFrom << " -> ";
		const AdjacencyList& targets = myVertices[iFrom];
		AdjacencyList::const_iterator f;
		for (f=targets.begin(); f!=targets.end(); ++f) {
			out << " " << (*f);
		}
		out << endl;
	}

	void printIncomingEdges(uint iTo, ostream& out) {
		out << iTo << " <- ";
		for (uint iFrom=0; iFrom<myVertices.size(); ++iFrom) {
			const AdjacencyList& currentTargets = myVertices[iFrom];
			if (currentTargets.count(iTo)) {
				out << iFrom << " ";
			}
		}
		out << endl;
	}

	// Print the graph, using the vertex indices
	void printIndices(ostream& out) const {
		for (uint i=0; i<myVertices.size(); ++i)
			out << i << " -> " << myVertices[i];
	}

	friend ostream& operator<< (ostream& out, const IntegerGraph& g) {
		g.printIndices(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(uint source, vector<uint>& distances, vector<uint>& previous) const {
		typedef unsigned char color;
		const color white=0, gray=1, black=2;

		vector<color> vertexColor(size());
		distances.resize(size());
		previous.resize(size());
		queue<uint> vertexQueue;

		fill(vertexColor.begin(), vertexColor.end(), white);
		fill(distances.begin(), distances.end(), MAXINT);
		fill(previous.begin(), previous.end(), MAXINT);

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

		// Loop over all vertices:
		while (!vertexQueue.empty()) {
			uint 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 = myVertices[current];
			AdjacencyList::const_iterator iNeighbour;
			for (iNeighbour=nextTargets.begin(); iNeighbour!=nextTargets.end(); ++iNeighbour) {
				uint neighbour = *iNeighbour;
				if (vertexColor[neighbour]==white) {   // a tree edge
					vertexColor[neighbour] = gray;
					distances[neighbour] = current_distance+1;
					previous[neighbour] = current;
					vertexQueue.push(neighbour);
				}
			}
			vertexColor[current] = black;   // finish a vertex
		}
	}
	
	
	void print_bfs_from(uint iFrom) {
		vector<uint> distances, previous;
		breadth_first_search(iFrom, distances, previous);
		cout << "BFS from " << iFrom << ": " << endl << "distances: " << distances << "previouses: " << previous << endl;
	}
}; // end of class IntegerGraph


int main() {
	IntegerGraph g(5);
	g.addEdge(0,1).addEdge(1,2).addEdge(2,3).addEdge(3,0).addEdge(0,2);
	cout << g << endl;
	g.printOutgoingEdges(0,cout);
	g.printOutgoingEdges(1,cout);
	g.printOutgoingEdges(2,cout);
	g.printOutgoingEdges(3,cout);
	g.printOutgoingEdges(4,cout);
	cout << endl;
	g.printIncomingEdges(0,cout);
	g.printIncomingEdges(1,cout);
	g.printIncomingEdges(2,cout);
	g.printIncomingEdges(3,cout);
	g.printIncomingEdges(4,cout);
	cout << endl;

	g.print_bfs_from(0);
	g.print_bfs_from(1);
	g.print_bfs_from(2);
	g.print_bfs_from(3);
	g.print_bfs_from(4);
}