//	ENGR 131, Monday 3:30 Recitation (Amanda Rohn)
//	Homework #7 - The Pruefer Correspondence
//	Solution

/****** ALGORITHM ******\

  To find the sequence, S, given a tree, T:

  1. Choose the vertex of degree one of T with the smallest label
  2. Take the (unique) vertex of T adjacent to the vertex in (1) and 
	 make its label the first term in the sequence S.
  3. Remove the vertex in (1) and its adjacent edge from T
  4. Repeat these steps until there are only two vertices left in T.
	 The resulting ordered set is called the Pruefer Code of T.

***********************


	A tree with n vertices can be represented by a two-dimensional boolean array, T, with n
	rows and n columns.  T[i][j] will be true if vertex i is connected to vertex j.  There
	are different types of trees, but in our case, edges will be bidirectional (that means
	that if T[i][j] is true, T[j][i] must necessarily be true), and T[i][i] will always
	be false (a vertex can't be connected to itself).

	You may assume that the input trees are valid trees. (Checking the validity of trees 
	is beyond the scope of this assignment.)

	In this assignment, since the trees' vertices are numbered from 1 to n, we'll have 
	one extra row and column  Here's a representation for the following tree with 5 
	vertices (all the trees in this assignment will have no more than 5 vertices).

	Tree:  1-2-3-4-5

    0  1  2  3  4  5 

  0 -  -  -  -  -  -      

  1 -  F  T  F  F  F       

  2 -  T  F  T  F  F			(Note: the dashes in the 0 row and column would actually
									   be set to false.)
  3 -  F  T  F  T  F     

  4 -  F  F  T  F  T     

  5 -  F  F  F  T  F
  

	The Pruefer Code of a tree, S, can easily be represented as an integer array containing
	n-2 elements.

***********************/


#include <iostream>

using std::cin;
using std::cout;
using std::endl;

const int vertices = 5;

int GetInteger(const char* prompt, int min, int max);
void GetTree(int T[vertices+1][vertices+1]);
void MakeS(int T[vertices+1][vertices+1], int S[vertices]);
void MakeT(int T[vertices+1][vertices+1], int S[vertices]);
void ShowTree(int T[vertices+1][vertices+1]);
void ShowS(int S[vertices]);
int Find(int n, int a[], int size);

int main()
{
	cout << "This program will prompt you for a description of a 5-vertex tree,\n"
		 << "display the tree, and calculate its Pruefer Code.\n\n";
	
	// Create two-dimensional array representation of a 5-vertex tree
	// (This tree is specified by the user)

	int T1[vertices+1][vertices+1] = {false};

	// Array to hold the Pruefer Code, S

	int S[vertices] = {0};

	// Get the tree from the user and display it

	GetTree(T1);
	ShowTree(T1);

	// Create and display S

	MakeS(T1, S);
	ShowS(S);

	return 0;
}


int GetInteger(const char* prompt, int min, int max)
{
	int num;

	for(;;)
	{
		cout << prompt << ": ";
		cin >> num;
		if(cin.fail() || cin.peek() != '\n' || num < min || num > max)
		{
			cin.clear();
			cin.ignore(1024,'\n');
			cout << "Please enter only an integer between " << min << " and " << max << endl;
		}
		else break;
	}
	return num;
}


void GetTree(int T[vertices+1][vertices+1])
{
	cout << "Please enter the " << vertices-1 << " edges of your tree, one at a time.\n";

	int i, j;	//the vertices on each edge

	for(int x = 1; x < vertices; x++)	//ask for n-1 edges
	{
		cout << "\nEdge #" << x << '\n';
		i = GetInteger("First Vertex", 1, vertices);
		j = GetInteger("Second Vertex", 1, vertices);

		T[i][j] = true;			//edges are bidirectional
		T[j][i] = true;
	}
}


void MakeS(int T[vertices+1][vertices+1], int S[vertices])
{
	int smallest, adj;

	for(int x = 1; x <= vertices-2; x++)
	{
		// 1. find vertex of degree one with smallest label
		int degree;

		for(smallest = 1; smallest <= vertices; smallest++)	//start checking row (vertex) 1
		{
			degree = 0;

			for(int j = 1; j <= vertices; j++)
			{
				if(T[smallest][j])
				{
					adj = j;	//most recently seen adjacent vertex
					degree++;
				}
			}

			if(degree == 1)		//if this vertex has degree one, move to next step
				break;
		}

		// 2. make the vertex adjacent to the vertex in (1) the next term in S

		S[x] = adj;

		// 3. Remove the vertex in (1) and its adjacent edge from T
		
		for(int j = 1; j <= vertices; j++)
		{
			T[smallest][j] = false;
			T[j][smallest] = false;
		}

		// 4. Repeat until there are two vertices left (taken care of by main for-loop)
	}
}


void ShowTree(int T[vertices+1][vertices+1])
{
	cout << "\nThe tree is given by the following matrix:\n\n    ";

	int i,j;	//counters

	for(i = 0; i <= vertices; i++)
		cout << i << "  ";

	cout << "\n\n";

	for(i = 0; i <= vertices; i++)
	{
		cout << i << "   ";
		for(j = 0; j <= vertices; j++)
			cout << T[i][j] << "  ";
		cout << endl;
	}
}
	

void ShowS(int S[vertices])
{
	cout << "\nThe Pruefer Code is: ";

	for(int i = 0; i < vertices; i++)
		cout << S[i] << " ";
}

int Find(int n, int a[], int size)
// if n is in the array a, returns the index at which it first appears
// if n is not in the array, returns -1
{
	for(int i = 0; i < size; i++)
	{
		//cout << a[i] << " =? " << n << endl;
		if(a[i] == n)
		{
			return i;
		}
	}

	return -1;
}