/************************************************************************************************/
/*			        LEDA Lab: 5th Lab Assignment					*/
/*			         Graphs and Topological Sort 					*/
/************************************************************************************************/

#define WhoAmI "<Give your name(s)>"		// for identification purposes		

#include <LEDA/graph/graph.h> 
#include <LEDA/core/array.h> 
#include <LEDA/core/string.h>
#include <LEDA/core/d_array.h> // for the dynamic insertion of a graph...
#include <iostream> 
 
using namespace leda; 

using std::cout;
using std::cin;
using std::endl;
  
bool TOPORDER(const graph& G, node_array<int>& ord) 
{ 
 
 
} 
 
void construct_graph(graph &G, node_array<string> &name)
{

	string s; 
	node v, startnode, endnode;
	edge e;
	bool getout = false;

	d_array<string,node> nametonode;
	d_array<node,string> nodetoname;

// INSERTION OF NODES...
		while(!getout)
		{ 
			cout.flush();	
			cout << "Will you give a new node[y/n]? ";
			cin >> s;
			if ( "y" != s ) 
			{ 
				getout=true; 
			} 
			else 
			{ 
				cout << "Onoma Kombou: "; 
				cin >> s; 
				cout << "YOU GAVE: " << s << endl;
				nametonode[s] = G.new_node();
				nodetoname[nametonode[s]] = s;
			}
		}

		getout = false;
// INSERTION OF EDGES...
		while(!getout)
		{ 
			cout.flush();	
			cout << "Will you give a new edge[y/n]? ";
			cin >> s;
			if ( "y" != s ) 
			{ 
				getout=true; 
			} 
			else 
			{ 
				cout << "Onoma 1oy Kombou: "; 
				cin >> s; 
				cout << "YOU GAVE: " << s << endl;
				startnode = nametonode[s];
				if (startnode != nil ) 
				{
					cout << "Onoma 2oy Kombou: "; 
					cin >> s; 
					cout << "YOU GAVE: " << s << endl;
					endnode = nametonode[s];
					if ( endnode != nil ) 
					{ 
						G.new_edge(startnode, endnode); 
					}
					else 
					{ 
						cout << "You gave a name of a node that does not exist..." << endl; 
					}
				}
				else 
				{
					cout << "You gave a name of a node that does not exist..." << endl;
				}
			}
		}

// INSERTION OF LOGICAL NAMES...
		name.init(G);
		forall_nodes(v,G)
		{ 
			name[v] = "[" + nodetoname[v] + "]"; 
		}	

}

void myprint(graph &G, node_array<string> &name)
{
	node v;
	edge e;
	
	forall_nodes(v,G){
		cout << name[v] << ": ";
		forall_out_edges(e,v) cout << name[source(e)] << "---->" << name[target(e)] << "\t";
		cout << endl;
	}
}

int main() 
{ 
	int i, N; //number of nodes...
	string s;

	graph G; 

	node_array<string> name(G);
	node_array<int> ord(G);

	node v;
	edge e;

cout << " /////////////////////////////////////////////////////////// " << endl;
cout << " LEDA LAB 2012: Lab5 \t " << WhoAmI << endl;
cout << " /////////////////////////////////////////////////////////// " << endl;


	cout << "...GIVING A GRAPH AS INPUT..." << endl; 
	if(Yes("8a dwseis diko soy grafhma [Yes/No]? ")){ construct_graph(G,name); }
	else {
		N=9;
		array<node> A(1,N);

		for(i=1; i<=N; i++)
		{
			A[i] = G.new_node();
		}
		
		name.init(G);
		i = 1;
		forall_nodes(v, G) { 
			name[v] = "[NODE"; 
			name[v]+= i+'0'; 
			name[v]+= ']';
			cout << name[v] << " - "; 
			i++; 
		}

		G.new_edge(A[1], A[3]);
		G.new_edge(A[3], A[7]);
		G.new_edge(A[9], A[2]);
		G.new_edge(A[9], A[5]);
		G.new_edge(A[2], A[8]);
		G.new_edge(A[7], A[4]);
		G.new_edge(A[7], A[5]);
		G.new_edge(A[4], A[6]);
		G.new_edge(A[5], A[8]);
		G.new_edge(A[8], A[6]);

// 		the bad edge destroying the topological order...
		G.new_edge(A[4], A[1]);
	}

	G.print(cout);
	myprint(G, name);
	
	ord.init(G);
	bool topolorder = TOPORDER(G, ord);

	if(topolorder) {
		cout << "THERE EXISTS A TOPOLOGICAL ORDER: " << endl; 
		forall_nodes(v,G){
			cout << "\t Order of Node " << name[v] << " is " << ord[v] << endl;
		}
		cout << endl;
		G.sort_nodes(ord);
		forall_nodes(v,G) cout << name[v] << " - ";
		cout << endl;
	}
	else cout <<"THERE IS NO TOPOLOGICAL ORDER FOR THIS GRAPH" << endl;
}