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

#include <iostream>
using namespace std;

#include "graph.cpp"

typedef Graph<int> TestGraph;

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

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

// O(n+m*n)
// всъщност може да стане O(n+m)
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++;
	}
}

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);
}

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, 1);
}

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