/* Minimum Spanning Tree / m8724607 / 林淑媛 */

/* My program limit CPU_Size at 1,2,4,8,...(2^i) */

/* Its for compair and broadcast with tree algorithm */

/*-------------------------------------------------*/

#include <mpi.h>

#include <stdio.h>

#include <stdlib.h>

#define maxV 1000 /* set max number of vertices */

#define MAX 100

#define True 1

#define False 0

int cost[maxV][maxV]; /* cost matrix of graph */

int nearest[maxV]; /* closest node matrix */

int spantree[maxV]; /* node of spanning tree */

int at_tree[maxV]; /* states of each point which on tree or no */

int rec[3], N;

int temp[3];

FILE *data;

void main(int argc, char *argv[])

{

int K, my_pe;

int i, j, k, p, par, t, c;

MPI_Status status;

MPI_Init(&argc, &argv);

MPI_Comm_size(MPI_COMM_WORLD, &K);

MPI_Comm_rank(MPI_COMM_WORLD, &my_pe);

/*-------------------------------data input and inilization-----------*/

data = fopen(argv[1],"r");

fscanf(data, "%d", &N);

for(i=0; i<N; i++)

{

for(j=0; j<N; j++)

fscanf(data, "%4d", &cost[i][j]);

}

par = N/K;

temp[2] = 0;

nearest[0] = 0;

t=my_pe*par;

for(j=0; j<N; j++)

{

spantree[j] = 0;

at_tree[j] = False;

nearest[j] = 0;

}

spantree[0]=0;

at_tree[0]=True;

/*------------------------start for find local min----------------*/

for(k=1; k<N; k++)

{

t = my_pe*par;

temp[0] = MAX;

for(j=0; j<par; j++)

{

c=t+j;

if(at_tree[c] == False)

{

if(cost[c][nearest[c]] <= temp[0])

{

temp[0] = cost[c][nearest[c]];

temp[1] = c;

temp[2] = nearest[c];

}

}

}

/*-----------------------------start find global min ------------*/

t=1;

while(t<K)

{

if((my_pe%t)==0)

{

if((my_pe%(t*2))==0)

{

MPI_Recv(&rec, 3, MPI_INT, my_pe+t, 4, MPI_COMM_WORLD, &status);

if(temp[0] > rec[0])

{

temp[0] = rec[0];

temp[1] = rec[1];

temp[2] = rec[2];

}

}

if((my_pe%(t*2))!=0)

MPI_Send(&temp, 3, MPI_INT, my_pe-t, 4, MPI_COMM_WORLD);

}

t=t*2;

}

/*------------------boardcast abs min to each processor -----------*/

t=K;

while(t>1)

{

if((my_pe%t)==0)

MPI_Send(&temp,3,MPI_INT,my_pe+(t/2),0,MPI_COMM_WORLD);

if((my_pe%t)==(t/2))

MPI_Recv(&temp,3, MPI_INT,my_pe-(t/2) ,0, MPI_COMM_WORLD, &status);

t=t/2;

}

spantree[k] = temp[1];

at_tree[temp[1]] = True;

/*-----------------------------change some data--------------*/

i=my_pe;

for(j=0; j<par; j++)

{

t=i*par+j;

if(at_tree[t]==False)

{

if(cost[t][spantree[k]] < cost[t][nearest[t]])

nearest[t] = spantree[k];

}

}

}

MPI_Finalize();

}