/*	Description: main function and other high-level code 

	implementing Prim's MST algorithm

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

						  9/1/99/LY

						  11/1/99/LY

						  19/1/99/LY - added exception handling

						  13/3/99/LY - finishing touches, debugging

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

*/



#include <iostream>	//allow cout

#include <vector>	

#include <algorithm> 

#include <limits.h> //allow UINT_MAX

#include <iterator>

#include "graph.h"



void test_assertions(void);

void generate_graph(void);

void prim(void);



//global constants - no namespace wrapper necessary 

const unsigned int	NUM_VERTICES = 15;	//must be greater than 1

const unsigned int	MAX_DEGREE = 40;		//must be greater than 1

const unsigned int	MAX_WEIGHT = 50;

const unsigned int	START_VERTEX = 1;	//must be between 0 and NUM_VERTICES-1



namespace Graph	//use namespaces to avoid introducing global variables

{

	graph_container	graph(NUM_VERTICES);

}

namespace MST_NS

{

	MST_container	MST(NUM_VERTICES);		

}



using namespace std;	/*global using directives are discouraged by Stroustrup, but widely used in this way to avoid

						constant namespace resolution (as in std::cout), cf. for example Microsoft sample code.*/



void main()

{

	using namespace MST_NS;

	test_assertions();	

	generate_graph();

	prim();

	cout << MST;

}



void generate_graph(void)

{

	using namespace Graph;

	for_each(graph.begin(),graph.end(),GraphGenerator<adj_list,graph_container>

			(NUM_VERTICES,MAX_DEGREE,MAX_WEIGHT,graph)); //generate a graph

	cout << graph;

}



void prim(void)

{

	using namespace MSTElem; 

	using namespace EdgeType; 	

	using namespace Graph;	

	using namespace MST_NS; 



	queue_container				heap(NUM_VERTICES);

	queue_container::iterator	qr_iter;

	MST_container::iterator		MST_iter;

		//initialise MST

	MSTElement	MST_elem = {START_VERTEX,UINT_MAX,1,0};	//declare appropriate initialization element for MST container



	fill(MST.begin(),MST.end(),MST_elem);	

	for (qr_iter = heap.begin(),MST_iter = MST.begin(); MST_iter != MST.end(); MST_iter++,qr_iter++)

	{	

		*qr_iter = &*MST_iter;	//fill the queue with references to the elements in the MST

		MST_iter->heap_ptr = &*qr_iter; //put pointer to heap in MST element

	}

	MST[START_VERTEX].key = 0;	//make sure start vertex is extracted first		

	make_heap(heap.begin(),heap.end(),heap_cmp);	//heap_cmp is a custom predicate (see definition elsewhere)

		

	adj_list::iterator					g_iter;

	queue_container::difference_type	q_diff;	

	MSTElement*							ptr_MST_elem;

		//the for-loop below corresponds closely to the pseudo-code for Prim's algorithm

	for (unsigned int count = 0;count<heap.size();count++) 

	{		

		ptr_MST_elem = *heap.begin();	//get minimal element from the priority queue 

		(*ptr_MST_elem).member = 0;	//indicate in the MST that the element selected is off the heap		

		q_diff = ptr_MST_elem - &*MST.begin();		//compute MST index of minimal element 

		for(g_iter = graph[q_diff].begin(); g_iter < graph[q_diff].end(); g_iter++)

		{	//compare the edge currently recorded to the one now considered and update if appropriate

			ptr_MST_elem = &MST[(*g_iter)[v]];

			if (((*ptr_MST_elem).member) && ((*ptr_MST_elem).key > (*g_iter)[weight])) 					

			{

		

				(*ptr_MST_elem).parent = (*g_iter)[u];	

				(*ptr_MST_elem).key = (*g_iter)[weight]; 

				heapify(heap.begin(),heap.end()-count,(*ptr_MST_elem).heap_ptr);

			}

		}

		pop_heap(heap.begin(),heap.end()-count,heap_cmp);	//remove minimal element

	} 

}



//rudimentary exception handling but better than the ANSI C assert(bool) function

void test_assertions(void)

{

	try {		//see graph.h for definition of assert<T>

	assert<exception>(NUM_VERTICES > 1);	

	assert<exception>(MAX_DEGREE > 1); 

	assert<exception>((START_VERTEX >= 0) && (START_VERTEX < NUM_VERTICES));

	}

	catch (...)

	{

		cerr << "Initialisation error. Check global constants." << endl;

		throw;	//surrender control to terminate()

	}

}