/*
 ============================================================================
 Name        : dstw2.c
 Author      :
 Version     :
 Copyright   : Your copyright notice
 Description : Hello MPI World in C
 ============================================================================
 */
#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"

#define M_TAG 1
#define PARENT_TAG 2
#define ALREADY_TAG 3

void print_spanning_tree(int* spanningTree, int nnodes, int root, int depth) {
	int i;

	for (i = 0; i < depth; ++i) {
		printf("\t");
	}

	printf("%d\n", root);

	for (i = 0; i < nnodes; ++i) {
		if (spanningTree[i] == root) {
			print_spanning_tree(spanningTree, nnodes, i, depth + 1);
		}
	}
}

int main(int argc, char* argv[]){
	int nnodes = 7;
	/*
	int index[] = {2, 3, 4, 6};
	int edges[] = {1, 3, 0, 3, 0, 2};
	*/
	int index[] = {3,7,11,14,15,17,18};
	int edges[] = {1,2,6,0,2,3,4,0,1,3,5,1,2,5,1,2,3,0};

	int pr = 0;/* the root processing unit */
	int pi; /* rank of process */
	int np;       /* number of processes */
	MPI_Comm G;

	int parent = -1;

	int i = 0;
	int terminate = 0;

	int pj;   /* rank of sender */

	int tag = 0;    /* tag for messages */
	MPI_Status status ;   /* return status for receive */

	/* start up MPI */

	MPI_Init(&argc, &argv);

	/* find out process rank */
	MPI_Comm_rank(MPI_COMM_WORLD, &pi);

	/* find out number of processes */
	MPI_Comm_size(MPI_COMM_WORLD, &np);
	if (np != nnodes) {
		if (pi == 0) {
			printf("Use -np %d!\n", nnodes);
		}
	} else {
		MPI_Graph_create(MPI_COMM_WORLD, nnodes, index, edges, 0, &G);

		int neighborsCount = 0;
		MPI_Graph_neighbors_count(G, pi, &neighborsCount);

		int *neighbors = 0;
		int *children = 0;
		int *other = 0;
		if (neighborsCount != 0) {
			neighbors = (int *)malloc(neighborsCount * sizeof(int));
			MPI_Graph_neighbors(G, pi, neighborsCount, neighbors);

			children = (int *)malloc(nnodes * sizeof(int));
			other = (int *)malloc(nnodes * sizeof(int));

			for (i = 0; i < nnodes; ++i) {
				children[i] = -1;
				other[i] = -1;
			}

			for (i = 0; i < neighborsCount; ++i) {
				children[neighbors[i]] = 0;
				other[neighbors[i]] = 0;
			}
		}

		int true = 1;
		while (true) {
			switch (tag) {
			case 0:
				if (pi == pr && parent == -1) {
					parent = pi;
					if (neighborsCount > 0) {
						for (i = 0; i < neighborsCount; ++i) {
							MPI_Send(&pi, 1, MPI_INT, neighbors[i], M_TAG, G);
						}
					} else {
						true = 0;
					}
				}
				break;
			case M_TAG:
				if (parent == -1) {
					parent = pj;
					MPI_Send(&pi, 1, MPI_INT, parent, PARENT_TAG, G);
					if (neighborsCount > 1) {
						for (i = 0; i < neighborsCount; ++i) {
							if (neighbors[i] != parent)
								MPI_Send(&pi, 1, MPI_INT, neighbors[i], M_TAG, G);
						}
					} else {
						true = 0;
					}
				} else {
					MPI_Send(&pi, 1, MPI_INT, pj, ALREADY_TAG, G);
				}
				break;
			case PARENT_TAG:
				children[pj] = 1;

				terminate = 1;
				for (i = 0; i < nnodes; ++i) {
					if (i != parent && children[i] == 0 && other[i] == 0) {
						terminate = 0;
						break;
					}
				}

				if (terminate) {
					true = 0;
				}

				break;
			case ALREADY_TAG:
				other[pj] = 1;

				terminate = 1;
				for (i = 0; i < nnodes; ++i) {
					if (i != parent && children[i] == 0 && other[i] == 0) {
						terminate = 0;
						break;
					}
				}

				if (terminate) {
					true = 0;
				}

				break;
			}

			if (true) {
				MPI_Recv(&pj, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, G, &status);
				tag = status.MPI_TAG;
			}
		}
	}

	if (parent != -1) {
		if (pi ==  parent) {

			int *spanningTree = (int *)malloc(nnodes * sizeof(int));
			for (i = 0; i < nnodes; ++i)
			{
				if (i != pi) {
					MPI_Recv(spanningTree + i, 1, MPI_INT, i, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
				}
			}

			print_spanning_tree(spanningTree, nnodes, pr, 0);
		}
		else
			MPI_Send(&parent, 1, MPI_INT, pr, 0, MPI_COMM_WORLD);
	}

	/* shut down MPI */
	MPI_Finalize();
	return 0;
}