/**************************
 *	Aufgabe 1
 *
 *      Azyklisch Test
 *
 * ************************/

#include <LEDA/graph/graph.h>
#include <LEDA/core/queue.h>
#include <LEDA/graphics/graphwin.h>

using namespace leda;

bool acyclic(const graph& G, GraphWin& gw){
	// Variables for initialization
	node_array<int> INDEG(G); 
	queue<node> ZEROINDEG; 
	node v, w; 

	// initilize queue with all nodes that have indegree 0 
	forall_nodes(v,G){
		if (( INDEG[v] = G.indeg(v)) == 0 ){
		       	ZEROINDEG.append(v); 
		}
	}

	// Variables for sorting 
	int counter = 0; 
	node_array<int> node_ord(G);
 	edge e; 

	// loop through queue, as long as its not empty
	while (!ZEROINDEG.empty()){
		v = ZEROINDEG.pop();
		node_ord[v] = ++counter; 

		// loop through all edges of the node
		// check if its deletion will cause a new node with indegree 0
		forall_out_edges(e,v){
			node w = G.target(e); 
			if ( --INDEG[w] == 0 ){
			       	ZEROINDEG.append(w);
			}
		}
	}
	// If Case --> if every Node has an order, the graph is acyclic and there is a topsort
	if ( counter == G.number_of_nodes() ){
		int y = 0;
		gw.set_flush(false);
		forall_nodes(v,G){
			point old_position = gw.get_position(v);
			point new_position = point(node_ord[v]*50,y);
			gw.set_position(v, new_position);
			// to see edges that skip nodes
			if (y == 0){
				y = 10;
			}else{
				y = 0;
			}
		}
		gw.place_into_win();
		gw.redraw();
		return true;
	// Else Case --> Graph has a cycle
	}else{
		queue<node> ZEROOUTDEG; 
		node_array<int> OUTDEG(G); 
		counter = 0;
		node_array<int> node_ord_out(G);

		// initilize queue with all nodes that have outdegree 0 
		forall_nodes(v,G){
			if (( OUTDEG[v] = G.outdeg(v)) == 0 ){
					ZEROOUTDEG.append(v); 
			}
		}

		while (!ZEROOUTDEG.empty()){
			v = ZEROOUTDEG.pop();
			node_ord_out[v] = ++counter; 

			forall_in_edges(e,v){
				node w = G.source(e);
				if ( --OUTDEG[w] == 0){
					ZEROOUTDEG.append(w);
				}
			}
		}

		forall_nodes(v,G){
			if (node_ord[v] == 0 && node_ord_out[v] == 0){
				gw.set_color(v,red);
			}
		}

		return false; 
	}
	
}

int main(){
	// creating graph window and setting title
	GraphWin gw("Acyclic Test");
	graph& G = gw.get_graph();
	gw.display(window::center, window::center); 

	// while graph is edited, do stuff
	while ( gw.edit() ){
		if ( acyclic(G, gw) ){	
			cout << "This graph is acyclic." << endl;
		}else {
			cout << "This graph is not acyclic." << endl;
		}
	}
	return 0; 
}