tree.cpp

算法中图算法的详细实现

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