/*
 *  prim.c
 *  
 *
 *  Created by eric on Mon Oct 15 2001.
 *
 *  WE ARE ASSUMING THAT ALL EDGES HAVE POSITIVE WEIGHTS.
 *
 */

#include <stdio.h>

//number of vertices
#define sizeG 9

void Prim(int, int[][sizeG], int[][sizeG]);

void main()
{
// user edge lists to generate adjacency matrix.

//{vertex #1, vertex #2, weight}

int E[][3] =
{
{0,1,2},
{0,2,4},
{0,3,5},
{0,4,7},
{0,5,9},
{0,6,3},
{0,7,5},
{0,8,12},
{1,4,34},
{2,5,56},
{3,6,5},
{3,5,45},
{4,7,8},
{4,6,4},
{5,8,10},
{5,7,12},
{6,8,20}
};

//I have chosen to represent the graph by it's adjacency matrix.
//large, but easy.

int G[sizeG][sizeG];  //allocate for adjacency matrix.
int T[sizeG][sizeG];  //allocate for tree adjacency matrix.

//zero the adjacency matrix for G

for(int y=0; y < sizeG; y++) for(int x=0; x < sizeG; x++) {G[x][y]=0;T[x][y]=0;}

//printf("%i\n\n", sizeof(E)/sizeof(int[3]) );

//fill adjacency matrix
for(int x=0; x < sizeof(E)/sizeof(int[3]); x++)
{
//printf("adding #%i:{%i,%i,%i}\n",x,E[x][0],E[x][1],E[x][2]);
G[ E[x][0] ][ E[x][1] ] = E[x][2];
G[ E[x][1] ][ E[x][0] ] = E[x][2];
}

//do the algorithm
//I will generate the adjacency matrix for T from G.

//pick some arbitrary vertex.
int first_vertex = 0;

//call prim's algorithm.
Prim(first_vertex, G, T);

printf("\n");

for(int x = 0; x < sizeG; x++)
{for(int y = 0; y < sizeG; y++) printf("%i ",G[x][y]);printf("\n");}

printf("\n");

for(int x = 0; x < sizeG; x++)
{for(int y = 0; y < sizeG; y++) printf("%i ",T[x][y]);printf("\n");}


// represent it on a circle?  draw diameters?

}//close main







void Prim(int vertex, int Graph[][sizeG], int Tree[][sizeG])
{//open prim
bool unused_vertices[sizeG];
int unused_count = sizeG;
//setting it

for(int x=0; x < sizeG; x++) for(int y=0; y < sizeG; y++) Tree[x][y]=0;

//set all vertices unused.
for(int y = 0; y < sizeG; y++) unused_vertices[y] = true;

//set the first vertex used.
unused_vertices[vertex] = false;
unused_count--;

while (unused_count > 0) //until we've used them all
{
//set the lightest edge to nothing value
int lightest_edge[] = {-1,-1,-1};

for(int x = 0; x < sizeG; x++) //go through all the used vertices
{//open for x

if (!unused_vertices[x])
{//open if

for(int y = 0; y < sizeG; y++) //then go through all vertices adjacent
{//open for y

if (unused_vertices[y] && ((lightest_edge[2] ==-1) || (Graph[x][y] < lightest_edge[2])) && (Graph[x][y] > 0) )
{
lightest_edge[0]=x;
lightest_edge[1]=y;
lightest_edge[2]=Graph[y][x];
printf("new lightest edge, from %i to %i weight: %i\n", x, y, Graph[y][x]);
}

}//close for y

}//close if

}//close for x

printf("setting vertex #%i used\n\n",lightest_edge[1]);
//add the edge to the tree.
Tree[lightest_edge[0]][lightest_edge[1]]=Tree[lightest_edge[1]][lightest_edge[0]]=lightest_edge[2];
unused_vertices[lightest_edge[1]] = false;
unused_count--;

}//close while

}//close prim