/*	Description: source file for classes used in implementation of Prim's MST algorithm

	Revision history: 8/1/99/LY - initial version, specialised

					  9/1/99/LY - template version begun

					  11/1/99/LY - experimented with some variations of data structure

					  12/1/99/LY - finalized program. Started trial runs and algorithmic debugging						

					  19/1/99/LY - added exception handling

					  22/1/99/LY - finished heap functions

					  28/3/99/LY - improved complexity of heap operations  

*/



#ifndef GRAPH

#define GRAPH



#include <stdlib.h>

#include <time.h>



using namespace std;



template <class X, class A>		

inline void assert(A assertion)	// see Stroustrup, p.750-751

{

	if (!assertion) throw X();

}



// GraphGenerator member functions

template <class T,class G>

GraphGenerator<T,G>::GraphGenerator(unsigned int v_arg,unsigned int degree_arg,

									unsigned int max_weight_arg, G& graph_arg)

: v(0),max_degree(degree_arg)	

{

	AdjacencyListGenerator<T::value_type,G>::Initialise(v_arg,max_weight_arg,&graph_arg); //initialise class

}



template <class T,class G>

void GraphGenerator<T,G>::operator()(T& adj_list)

{

	//unsigned int rand_degree = unsigned((rand()%(max_degree-1))+2);

	unsigned int rand_degree = max_degree;

	adj_list.resize(adj_list.size()+rand_degree);

	for_each(adj_list.end()-rand_degree,adj_list.end(),AdjacencyListGenerator<T::value_type,G>(v,v++));

}



// AdjacencyListGenerator static data members (definition)

template <class T,class G>

unsigned int AdjacencyListGenerator<T,G>::max_weight;

template <class T,class G>

unsigned int AdjacencyListGenerator<T,G>::total_v;

template <class T,class G>

G* AdjacencyListGenerator<T,G>::graph_ptr;

template <class T,class G>

vector<unsigned int>	AdjacencyListGenerator<T,G>::rnd_pool;



// AdjacencyListGenerator member functions

template <class T,class G>

AdjacencyListGenerator<T,G>::AdjacencyListGenerator(unsigned int v_arg,unsigned int v_index_arg)

:v(v_arg), v_index(v_index_arg)

{

}



template <class T,class G>

void AdjacencyListGenerator<T,G>::operator()(T& edge)

{

	Generator(edge);

}



//static member function

template <class T,class G>

void AdjacencyListGenerator<T,G>::Initialise(unsigned int v_arg,unsigned int max_weight_arg,G* graph_arg)

{

	srand(unsigned(time(NULL)));	//seed the pseudo-random number generation

	insert_iterator<vector<unsigned int> >	r_iter(rnd_pool,rnd_pool.begin()); 

	for (int c = v_arg-1; c>=0; c--) 

	{

		*r_iter++ = c;	

	}

	random_shuffle(rnd_pool.begin(),rnd_pool.end()); //make random permutation

	max_weight = max_weight_arg;

	total_v = v_arg;

	graph_ptr = graph_arg;

}



//edge generator function

template <class T,class G>

void AdjacencyListGenerator<T,G>::Generator(T& x) 

{				

	x.push_back(v);	//insert first vertex of edge

	unsigned int end_point = rnd_pool[(v_index++)%total_v];

	end_point = (v==end_point) ? rnd_pool[(v_index++)%total_v] : end_point; //avoid loops in the graph

	x.push_back(end_point);	 //pick random valid end-vertex for edge

	x.push_back(unsigned((rand()%max_weight)+1));	//generate random weight within acceptable range for new edge



	T	y;		//new edge to be inserted into adj[end_point]

	y.push_back(x[EdgeType::v]);	//insert vertices in reverse order of original

	y.push_back(x[EdgeType::u]);	//to create an appropriate counterpart

	y.push_back(x[EdgeType::weight]);	//weight is the same as that of the original, of course

	(*graph_ptr)[x[EdgeType::v]].push_back(y); 

}



/*	Precondition:  all elements of the range [first,last), with the possible exception of *element,

				   obey the heap condition (node x >= parent[x]).

	Postcondition: all elements of [first,last), with the possible exception of *element's parent,

				   obey the heap condition. 

*/

template <class RandomAccessIterator>

void heapify(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator element)

{

	queue_container::difference_type	offset = (element-first-1)/2;



	if ((offset > 0) && ((**element).key < (**(first+offset)).key))

	{

		swap(*(first+offset),*element);		//swap node *first with parent

		heapify(first,last,first+offset);	//"bubble up" *first further in the heap, if necessary

	}

}



/* Function used as equivalent of > operator on elements in priority queue (implemented as a heap)

   Notice that this produces a heap which is ordered oppositely of the norm, i.e. smallest element at the root.

   This is done to make the STL algorithm pop_heap return the smallest rather than largest element, as

   is its default behaviour.

 */

bool heap_cmp(MSTElement* ptr_M1,MSTElement* ptr_M2)

{

	return ((*ptr_M1).key > (*ptr_M2).key);

}



//overloaded I/O operators



// custom indentation I/O manipulator 

ostream& tab(ostream& os)

{

	return os << "\t";

}

namespace Graph

{	

	// overloaded << operator for edges

	ostream& operator<<(ostream& os, edge_type& edge)

	{

		using namespace EdgeType;

		os << "(" << edge[u] << "," << edge[v] << "," 

			   << edge[weight] << ")" << " "; 

		return os;

	}

	

	// overloaded << operator for adjacency lists

	ostream& operator<<(ostream& os, adj_list& a_list)

	{	

		for (adj_list::iterator a_iter = a_list.begin(); a_iter != a_list.end(); a_iter++)

		{

			os << *a_iter;

		}

		return os;

	}

	// overloaded << operator for graphs

	ostream& operator<<(ostream& os, graph_container& graph)

	{

		os << "Now printing a graph containing " << graph.size() << " vertices" << endl;

		for (graph_container::iterator g_iter = graph.begin(); g_iter != graph.end(); g_iter++)

		{

			os << tab << "Adjacency list #" << (g_iter - graph.begin()) << ":" << *g_iter << endl;

		}

		return os;

	}

}

namespace MST_NS

{

	// overloaded operator for queue

	ostream& operator<< (ostream& os,MST_container& MST)

	{

		using namespace MSTElem;

		os << endl << "Now printing a minimum spanning tree with " << MST.size() << " vertices" << endl;

		for (MST_container::iterator MST_iter = MST.begin(); MST_iter != MST.end(); MST_iter++)

		{

			os << "(" << (*MST_iter).parent << "," << (MST_iter - MST.begin()) 

			   << "," << (*MST_iter).key << ")" << " ";

		}

		os << endl;

		return os;

	}

}



#endif