/*
 * graphtest.cpp
 *
 *  Created on: 09.01.2014
 *      Author: trifon
 */

#include <iostream>
using namespace std;

#include "graph.cpp"
#include "double_linked_list.cpp"

typedef Graph<int> TestGraph;

template <typename V>
void visit(V const& v) {
	cout << "Посещаваме " << v << endl;
}

template <typename T, typename I>
bool member(T const& x, List<T, I> const& l) {
	I it = l.begin();
	while (it && *it != x)
		++it;
	return it;
}

// O(n+m*n)
// всъщност може да стане O(n+m), ако пренебрегнем member
template <typename V>
void DFSrec(Graph<V> const& g, V const& v, LinkedList<V>& visited) {
	visit(v);
	visited.toEnd(v);
	for(typename Graph<V>::VI it = g.successors(v); it; ++it)
		if (!member(*it, visited))
			DFSrec(g, *it, visited);
}

template <typename V>
void DFS(Graph<V> const& g, V const& v) {
	LinkedList<V> visited;
	DFSrec(g, v, visited);
}

/*
 * не внимава за цикли!
template <typename V>
void BFS(Graph<V> const& g, V const& v) {
	LinkedList<V> toVisit;
	toVisit.toEnd(v);
	while (!toVisit.empty()) {
		LinkedListIterator<V> it = toVisit.begin();
		V u;
		toVisit.deleteAt(u, it);
		visit(u);
		for(it = g.successors(u); it; ++it)
			toVisit.toEnd(*it);
	}
}
*/

template <typename V>
void BFS(Graph<V> const& g, V const& v) {
	LinkedList<V> toVisit;
	toVisit.toEnd(v);
	LinkedListIterator<V> nextToVisit = toVisit.begin();
	while (nextToVisit) {
		V u = *nextToVisit;
		visit(u);
		for(LinkedListIterator<V> it = g.successors(u); it; ++it)
			if (!member(*it, toVisit))
				toVisit.toEnd(*it);
		nextToVisit++;
	}
}

// O(n + m), ако пренебрегнем member
template <typename V>
bool findPathRec(Graph<V> const& g, V const& a, V const& b,
		LinkedList<V>& visited, LinkedList<V>& path) {
	// visit(a);
	path.toEnd(a);
	visited.toEnd(a);
	if (a == b) {
		cout << "Намерихме път: " << path;
		return true;
	}
	for(typename Graph<V>::VI it = g.successors(a); it; ++it)
		if (!member(*it, visited) &&
			findPathRec(g, *it, b, visited, path))
			return true;
	// неуспех, изтриваме a от пътя
	V tmp;
	LinkedListIterator<V> it = path.end();
	path.deleteAt(tmp, it);
	return false;
}

template <typename V>
bool findPath(Graph<V> const& g, V const& a, V const& b) {
	LinkedList<V> visited;
	LinkedList<V> path;
	return findPathRec(g, a, b, visited, path);
}

// O(n*n!)
template <typename V>
void findAllPathsRec(Graph<V> const& g, V const& a, V const& b,
		LinkedList<V>& path) {
	// visit(a);
	path.toEnd(a);
	cout << "Маркираме " << a << endl;
	if (a == b) {
		cout << "Намерихме път: " << path;
		// !!! НЕ!!!! return;
	} else {
		for(typename Graph<V>::VI it = g.successors(a); it; ++it)
			if (!member(*it, path))
				findAllPathsRec(g, *it, b, path);
	}
	// неуспех, изтриваме a от пътя
	V tmp;
	LinkedListIterator<V> it = path.end();
	path.deleteAt(tmp, it);
	cout << "Отмаркираме " << a << endl;
	return;
}

template <typename V>
void findAllPaths(Graph<V> const& g, V const& a, V const& b) {
	LinkedList<V> path;
	findAllPathsRec(g, a, b, path);
}

// O(n*n!)
template <typename V>
bool findPath2Rec(Graph<V> const& g, V const& a, V const& b,
		LinkedList<V>& path) {
	// visit(a);
	path.toEnd(a);
	//cout << "Маркираме " << a << endl;
	if (a == b) {
		cout << "Намерихме път: " << path;
		return true;
	} else {
		for(typename Graph<V>::VI it = g.successors(a); it; ++it)
			if (!member(*it, path) &&
				findPath2Rec(g, *it, b, path))
				return true;
	}
	// неуспех, изтриваме a от пътя
	V tmp;
	LinkedListIterator<V> it = path.end();
	path.deleteAt(tmp, it);
	//cout << "Отмаркираме " << a << endl;
	return false;
}

template <typename V>
bool findPath2(Graph<V> const& g, V const& a, V const& b) {
	LinkedList<V> path;
	return findPath2Rec(g, a, b, path);
}

Graph<int> fullGraph(int n) {
	Graph<int> g;
	for(int i = 1; i <= n; i++) {
		g.addVertex(i);
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if (i != j)
				g.addEdge(i, j);
	return g;
}

template <typename V>
void findAllPathsShorterThanRec(Graph<V> const& g, V const& a, V const& b,
		LinkedList<V>& path, int k) {
	// visit(a);
	path.toEnd(a);
	if (k > 0) {
		if (a == b) {
			cout << "Намерихме път: " << path;
			// !!! НЕ!!!! return;
		} else {
			for(typename Graph<V>::VI it = g.successors(a); it; ++it)
				findAllPathsShorterThanRec(g, *it, b, path, k - 1);
		}
	}
	// неуспех, изтриваме a от пътя
	V tmp;
	LinkedListIterator<V> it = path.end();
	path.deleteAt(tmp, it);
	return;
}

template <typename V>
void findAllPathsShorterThan(Graph<V> const& g, V const& a, V const& b, int k) {
	LinkedList<V> path;
	findAllPathsShorterThanRec(g, a, b, path, k);
}

template <typename V>
bool hasCycleFrom(Graph<V> const& g, V const& v) {
	LinkedList<LinkedList<V> > toVisit;
	LinkedList<V> path;
	path.toEnd(v);
	toVisit.toEnd(path);
	cout << "Тръгваме от " << v << endl;
	LinkedListIterator<LinkedList<V> > nextToVisit = toVisit.begin();
	while (nextToVisit) {
		LinkedList<V> upath = *nextToVisit;
		V u = *upath.end();
		// if ( member(u, toVisit)) // винаги ще връща true -- не става
			// visit(u);
		for(LinkedListIterator<V> it = g.successors(u); it; ++it)
			if (!member(*it, upath)) {
				LinkedList<V> newPath = upath;
				newPath.toEnd(*it);
				toVisit.toEnd(newPath);
			}
			else {
				cout << "Стигнахме до " << *it << endl;
				return true;
			}
		LinkedListIterator<LinkedList<V> > it = nextToVisit++;
		toVisit.deleteAt(upath, it);
	}
	return false;
}

template <typename V>
bool hasCycle(Graph<V> const& g) {
	LinkedList<V> vert = g.vertices();
	for(LinkedListIterator<V> it = vert.begin(); it; ++it)
		if (hasCycleFrom(g, *it))
			return true;
	return false;
}

template <typename V>
struct Edge {
	Edge() {}
	Edge(V _from, V _to) : from(_from), to(_to) {}
	V from, to;
	// наричаме ребрата различни, ако
	// завършват в различни върхове
	// т.е. сравняваме ребрата по to върховете им
	bool operator!=(Edge const& e) {
		return e.to != to;
	}
	friend ostream& operator<<(ostream& os, Edge<V> const& e) {
		return os << '(' << e.from << ',' << e.to << ')';
	}
};

template <typename V>
bool shortestPath(Graph<V> const& g, V const& a, V const& b) {

	DoubleLinkedList<Edge<V> > toVisit;
	toVisit.toEnd(Edge<V>(a,a));
	DoubleLinkedListIterator<Edge<V> > nextToVisit = toVisit.begin();
	while (nextToVisit) {
		Edge<V> e = *nextToVisit;
		V u = e.to;
		for(LinkedListIterator<V> it = g.successors(u); it; ++it)
			if (!member(Edge<V>(u,*it), toVisit)) {
				toVisit.toEnd(Edge<V>(u,*it));
				if (*it == b) {
					cout << "Намерихме най-кратък път: ";
					// cout << toVisit << endl;
					LinkedList<V> path;
					V current = b;
					for(DoubleLinkedListIterator<Edge<V> > it = toVisit.end(); it; --it) {
						if (current == (*it).to) {
							path.insertBefore(current, path.begin());
							current = (*it).from;
						}
					}
					cout << path << endl;
					return true;
				}
			}
		nextToVisit++;
	}
	return false;
}

template <typename V>
void spanningTreeRec(Graph<V> const& g, V const& v, Graph<V> & st) {
	// вече е посетен, добавен в дървото
	for(typename Graph<V>::VI it = g.successors(v); it; ++it)
		if (!member(*it, st.vertices())) {
			st.addVertex(*it);
			st.addEdge(v, *it);
			spanningTreeRec(g, *it, st);
		}
}

template <typename V>
Graph<V> spanningTree(Graph<V> const& g, V const& v) {
	Graph<V> st;
	st.addVertex(v);
	spanningTreeRec(g, v, st);
	return st;
}

/**
 * Проверяваме дали върхът v няма предшественици
 */
template <typename V>
bool isBoss(Graph<V> const& g, V const& v) {
	LinkedList<V> vert = g.vertices();
	for(LinkedListIterator<V> it = vert.begin(); it; ++it)
		for(LinkedListIterator<V> sit = g.successors(*it); sit; ++sit)
			if (*sit == v)
				return false;
	return true;
}

/**
 * Намираме всички върхове в candidates, които нямат предшественици и ги записваме в result
 */
template <typename V>
void findBosses(Graph<V> const& g, LinkedList<V> const& candidates, LinkedList<V>& result) {
	for(LinkedListIterator<V> it = candidates.begin(); it; ++it)
		if (isBoss(g, *it))
			result.toEnd(*it);
}

/**
 * Топологично сортиране
 */
template <typename V>
LinkedList<V> topoSort(Graph<V> g) {
	LinkedList<V> result;
	LinkedList<V> currentBosses;
	// намираме първоначалния списък на върхове без предшественици
	findBosses(g, g.vertices(), currentBosses);
	if (currentBosses.empty())
		// цикъл!
		return result;
	for(LinkedListIterator<V> it = currentBosses.begin(); it; ++it) {
		// извеждаме поредния връх
		result.toEnd(*it);
		LinkedList<V> candidates;
		// събираме като кандидати всички наследници, които още не са обходени
		for(LinkedListIterator<V> sit = g.successors(*it); sit; ++sit)
			if (!member(*sit, currentBosses))
				candidates.toEnd(*sit);
		// премахваме текущия връх
		g.removeVertex(*it);
		// и събираме евентуално новите върхове, които са останали без предшественици
		findBosses(g, candidates, currentBosses);
	}
	// това е!
	return result;
}

void testGraph() {
	TestGraph g;
	for(int i = 1; i <= 6; i++)
		g.addVertex(i);
	g.addEdge(1,2);
	g.addEdge(1,3);
	g.addEdge(2,3);
	g.addEdge(2,6);
	g.addEdge(3,4);
	g.addEdge(3,6);
	g.addEdge(4,5);
	g.addEdge(4,1);
	g.addEdge(5,3);
	g.addEdge(6,5);
	cout << g.vertices() << endl;
	cout << g << endl;
	//g.removeVertex(3);
	//cout << g << endl;
	cout << "DFS" << endl;
	DFS(g, 1);
	cout << "BFS" << endl;
	BFS(g, 1);
	cout << "findPath(g,1,6)\n";
	cout << findPath(g, 1, 6) << endl;
	cout << "findAllPaths(g,1,6)\n";
	findAllPaths(g, 1, 6);
	cout << "findPath2(g,1,6)\n";
	cout << findPath2(g, 1, 6) << endl;

	const int n = 5;
	Graph<int> fg = fullGraph(n);
	fg.addVertex(n+1);
	fg.addEdge(1, n+1);
	cout << findPath(fg, 1, n+1) << endl;
	cout << findPath2(fg, 1, n+1) << endl;

	findAllPathsShorterThan(g, 1, 6, 7);

	cout << shortestPath(g, 1, 5) << endl;

	cout << spanningTree(g, 1) << endl;

	cout << hasCycle(g) << endl;
	g.removeEdge(5, 3);
	cout << hasCycle(g) << endl;
	g.removeEdge(4, 1);
	cout << hasCycle(g) << endl;

	cout << topoSort(g) << endl;
}

int main() {
	testGraph();
	return 0;
}