#include "Tree.h"#include <limits.h>#include <iostream>#include <map>#include <queue>#include <set>using namespace std;Tree::Tree( int nnodes ){	nnode = nnodes;	list< treenode* > ll;	myTree.push_back(ll);	for( int i = 1 ; i <= nnodes; i ++ )	{		treenode *node = new treenode(i);		list< treenode* > l;		l.push_back( node );		myTree.push_back( l );			}	for( int i = 0; i <= nnode; i ++ )	{		vector< int > now;		matrix.push_back( now );		parent.push_back( now );		for( int j = 0; j <= nnode; j ++ )		{			matrix[i].push_back( 0 );			parent[i].push_back( 0 );		}	}}void Tree::addOneEdge(int from , int to , int value){	treenode *node = myTree[to].front();	edge.insert( make_pair( make_pair( from , to ) , value ));	addOneEdge( from , node );}void Tree::addOneEdge( int from , treenode* node ){	myTree[from].push_back( node );	}int Tree::getEdgeValue( int from , int to ){	if( from == to )		return 0;	pair< int , int > p = make_pair( from , to );	map< pair< int , int > , int >::iterator it = edge.find( p );	if( it != edge.end() )		return it->second;	else		return INT_MAX;}void Tree::removeOneEdge( int from , int to ){	list< treenode* > l = myTree[from];	list< treenode* >::iterator it = l.begin();	while( it != l.end() )	{		if( (*it)->id == to )		{			l.erase( it );			break;		}	}}void Tree::BFS( int s ){	for( int i = 1;i <= nnode ; i ++ )	{		if( i != s )		{			myTree[i].front()->color = WHITE;			myTree[i].front()->distence = INT_MAX;			myTree[i].front()->parent = NULL;		}	}	treenode* node = myTree[s].front();	node->color = GRAY;	node->distence = 0;	node->parent = NULL;	myQueue.push( node );	while( !myQueue.empty() )	{		treenode* u = myQueue.front();		myQueue.pop();		int id = u->id;		cout << u->id << "(depth:" << u->distence << ")   ";		list< treenode* > l = myTree[id];		list< treenode* >::iterator it = l.begin();		it ++;		while( it != l.end() )		{			if( (*it)->color == WHITE )			{				(*it)->color = GRAY;				(*it)->distence = u->distence + 1;				(*it)->parent = u;				myQueue.push( *it );			}			it ++;		}		u->color = BLACK;	}}void Tree::DFS(){	topologicalList.clear();	for( int i = 1; i <= nnode; i ++ )	{		treenode* node = myTree[i].front();		node->color = WHITE;		node->parent = NULL;	}	myTime = 0;	for( int i = 1; i <= nnode; i ++ )	{		treenode* node = myTree[i].front();		if( node->color == WHITE )		{			dfs_visit( i , myTree );		}	}}void Tree::dfs_visit( int root , vector< list< treenode* > >& G ){	treenode* node = G[root].front();	node->color = GRAY;	myTime ++;	node->firsttime = myTime;	list< treenode* > l = G[root];	list< treenode* >::iterator it = l.begin();	it ++;	while( it != l.end() )	{		if( (*it)->color == WHITE )		{			(*it)->parent = node;			dfs_visit( (*it)->id , G);		}		it ++;	}	node->color = BLACK;	myTime ++;	node->endtime = myTime;	topologicalList.push_front( node->id );}void Tree::print_path( int root , int end ){	BFS( root );	print( root , end );}void Tree::printTopologic(){	list< int >::iterator it = topologicalList.begin();	while( it != topologicalList.end() )	{		cout << *it << "   ";		it ++;	}}void Tree::print(int root ,  int end ){	if( end == root )		cout << "v" << root << "--->";	else	{		treenode* now = myTree[end].front();		if( now->parent == NULL )		{			cout << "There is no path from " << root << " to " << end << endl;			return;		}		else		{			print( root , now->parent->id );			cout << "v" << end  << "--->";		}	}}void Tree::getGT(){	list< treenode* > ll;	myGT.push_back( ll );	for( int i = 1; i <= nnode; i ++ )	{		list< treenode* > l;		treenode* node = new treenode( i );		l.push_back( node );		myGT.push_back( l );	}	for( int i = 1; i <= nnode; i ++ )	{		list< treenode* > l = myTree[i];		list< treenode* >::iterator it = l.begin();		it ++;		while( it != l.end() )		{			int pid = (*it)->id;			myGT[pid].push_back( myGT[i].front() );			it ++;		}	}}void Tree::strongly_connected(){	DFS();	map< int , int > index;	for( int i = 1; i <= nnode; i ++ )	{		treenode* node = myTree[i].front();		index.insert( make_pair( node->endtime , node->id ) );	}	getGT();	for( int i = 1; i <= nnode; i ++ )	{		myGT[i].front()->color = WHITE;		myGT[i].front()->parent = NULL;	}	map< int , int >::reverse_iterator rit = index.rbegin();	while( rit != index.rend() )	{		int pid = rit->second;		if( myGT[pid].front()->color == WHITE )		{			cout << "Strongly Connected Tree root: " << pid << endl;			dfs_visit( pid , myGT );			cout << endl;		}		rit ++;	}}void Tree::MST_PRIM(int root ){	caseno = 1;	int total = 0;	set< qnode > myQueue;	set< int > outQueue;	treenode* node = myTree[root].front();	node->key = 0;	qnode qq( root , node->key );	myQueue.insert( qq );	for( int i = 1; i <= nnode; i ++ )	{		if( i == root )			continue;		treenode* node = myTree[i].front();		node->key = INT_MAX;		node->parent = NULL;		qnode qn( i , node->key );		myQueue.insert( qn );	}	set< qnode >::iterator pq;	while( !myQueue.empty() )	{		pq = myQueue.begin();		qnode q = *pq;		myQueue.erase( pq );		total += q.key;		cout << "The " << caseno << " node: { " << q.id << " , " << q.key << " }" << endl;		int id = q.id;		outQueue.insert( id );		list< treenode* >l = myTree[id];		list< treenode* >::iterator it = l.begin();		it ++;		while( it != l.end() )		{			int myid = (*it)->id;							if( outQueue.find( myid ) == outQueue.end() )			{				(*it)->parent = node;				int w = getEdgeValue( id , myid ); 				treenode* now = myTree[myid].front();					if( now->key > w )				{					qnode tt( myid , now->key );					myQueue.erase( tt );					now->key = w;					tt.key = w;					myQueue.insert( tt );				}			}			it ++;		}	}	cout << "The total value of the MST produced by PRIM is: " << total << endl;}void Tree::initialize_single_source( ){	for( int i = 1; i <= nnode; i ++ )	{		treenode* node = myTree[i].front();		node->value = INT_MAX;		node->parent = NULL;	}}void Tree::relax( int u , int v , set< treenode* , value_cmp >& myQueue ){	treenode* node1 = myTree[u].front();	treenode* node2 = myTree[v].front();	int xv = node1->value + getEdgeValue( u , v );	if( node2->value > xv )	{		myQueue.erase( node2 );		node2->value = xv;		node2->parent = node1;		myQueue.insert( node2 );	}}void Tree::dijkstra( int s ){	initialize_single_source();	myTree[s].front()->value = 0;	set< int > S;	set< treenode* , value_cmp > myQueue;	myQueue.insert( myTree[s].front() );		while( !myQueue.empty() )	{		treenode* now = *myQueue.begin();		myQueue.erase( myQueue.begin() );		int nowid = now->id;		S.insert( nowid );		list< treenode* > l = myTree[nowid];		list< treenode* >::iterator it = l.begin();		it ++;		while( it != l.end() )		{			treenode* adjnode = *it;			int adjid = adjnode->id;			if( S.find( adjid ) == S.end() )				relax( nowid , adjid , myQueue );			it ++;		}	}}void Tree::print_all_single_source_path( int s ){	cout << "All the paths is: " << endl;	for( int i = 1; i <= nnode; i ++ )	{		if( i != s )		{			cout << "The path from " << s << " to " << i << " is: " << endl;			int total = print_single_source_path(i);			cout << "(TotalValue: " << total << " )" << endl;		}		cout << endl;	}}int Tree::print_single_source_path( int e ){	int result = 0;	treenode* end = myTree[e].front();	if( end->parent == NULL )	{		cout << end->id << "(" << end->value << ") " << "--->";	}	else	{		result = print_single_source_path(end->parent->id);		cout << end->id << "(" << end->value << ") " << "--->" ;	}	return end->value;}bool Tree::bellman_ford (int s){	set< treenode* , value_cmp> qq ;	initialize_single_source();	myTree[	s ].front()->value = 0;	for( int i = 1; i < nnode; i ++ )	{		map< pair< int , int > , int >::iterator it = edge.begin();		while( it != edge.end() )		{			pair< int , int > p = it->first;			relax( p.first , p.second  , qq);			it ++;		}	}	map< pair< int , int > , int >::iterator it = edge.begin();	while( it != edge.end() )	{		pair< int , int > p = it->first;		treenode* node1 = myTree[p.first].front();		treenode* node2 = myTree[p.second].front();		if( node2->value > node1->value + getEdgeValue( p.first , p.second ) )			return false;		it ++;	}	return true;}void Tree::slow_all_pairs_shortest_paths(){	//initialize	for( int i = 1; i <= nnode; i ++ )	{		for( int j = 1; j <= nnode; j ++ )		{			int ev = getEdgeValue( i , j );			matrix[i][j] =  ev;			if( ev != INT_MAX )				parent[i][j] = i;		}	}	for( int i = 2; i <= nnode - 1; i ++ )		extend_shortest_paths();}void Tree::extend_shortest_paths(){	for( int i = 1; i <= nnode; i ++ )	{		for( int j = 1; j <= nnode ; j ++ )		{			for( int k = 1; k <= nnode; k ++ )			{				//relax				int ev = getEdgeValue( k , j );				if( ev == INT_MAX || matrix[i][k] == INT_MAX )					continue;				int t = matrix[i][k] + ev;				if( matrix[i][j] >  t )				{					matrix[i][j] = t ;					parent[i][j] = k;				}			}		}	}}void Tree::print_all_pairs_shortest_paths(){	for( int i = 1; i <= nnode; i ++ )	{		for( int j = 1; j <= nnode; j ++ )		{			cout << i << " to " << j << ":" << endl;			print_one_pair_shortest_path( i , j );			cout << "ShortestPath( " << matrix[i][j] << " )" ;			cout << endl;		}		cout << endl;	}}bool Tree::print_one_pair_shortest_path( int from , int to ){	if( from == to )		cout << from << "--->";	else if( parent[from][to] == 0 )	{		cout << "No path from " << from << " to " << to << endl;		return false;	}	else	{		if( print_one_pair_shortest_path( from , parent[from][to] ) ) 			cout << to << "--->";		else			return false;	}	return true;}void Tree::Floyd_Warshall(){	for( int i = 1; i <= nnode; i ++ )	{		for( int j = 1; j <= nnode; j ++ )		{			int ev = getEdgeValue( i , j );			matrix[i][j] = ev;			if( ev != INT_MAX )				parent[i][j] = i;			else				parent[i][j] = 0;		}	}		for( int k = 1; k <= nnode; k ++ )	{		vector< vector< int > > old = matrix;		vector< vector< int > > oldParent = parent;		for( int i = 1; i <= nnode; i ++ )		{			for( int j = 1; j <= nnode; j ++ )			{				if( old[i][k] == INT_MAX || old[k][j] == INT_MAX )					continue;				int newvalue = old[i][k] + old[k][j];				if( matrix[i][j] > newvalue )				{					matrix[i][j] = newvalue;					parent[i][j] = oldParent[k][j];				}			}		}	}}Tree::~Tree(){	for( int i = 1; i <= nnode ; i ++ )	{		treenode* node = myTree[i].front();		delete node;		if( !myGT.empty() )		{			node = myGT[i].front();			delete node;		}	}}