/*Tyler A. Simon
prims_undirected.c
Create a minimum spanning tree from a file "weights.inp"
Format output to be used with GraphViz dot
Some of the code was used from 
"Mastering Algorithms with C" by Kyle Louden


To compile:cc -o prims_undirected prims_undirected.c
To Run:
./prims_undirected | dot -Tgif -o graph_un.gif; display graph_un.gif &
circo -Tgif problem.dat > problem_un.gif; display problem_un.gif &

Change MAX to get a larger graph, note the "problem.dat" wil mostly be unreadable.
*/ 

#include <stdio.h>
#include <stdlib.h>

#define MAX 20

struct nlist {
	int head;
	int nid;
	int tail;
	};
struct nlist list[MAX];


int inp_gen(){
FILE *fp;
FILE *gfp;
int i,j;
int weights[MAX+1][MAX+1]; //adj matrix n^2 storage needed


srand( (unsigned int)time( NULL ) );


gfp=fopen("problem.dat", "w+");

	fprintf(gfp,"graph G{\n");
	fprintf(gfp,"rankdir=LR;");
	fprintf(gfp,"size=\"7,7\"\n");
	fprintf(gfp,"node [shape = circle];\n");


//fprintf(fp, "%d\n", MAX);
int count=MAX-1;
for(i=0; i<MAX; i++)
        {
		
	for(j=i+1; j<MAX; j++)
			{
				weights[i][j]=1+(rand()%(2*MAX));	
				fprintf(gfp,"%d--%d [ label = \"%d\"];\n", i, j, weights[i][j]);
				count=j;
			//	printf("weights[%d][%d] = %d, count = %d\n", i,j,weights[i][j],count);
			}
       
        }
fprintf(gfp,"}\n");
fclose(gfp);

	/*Now create weights.inp*/
fp=fopen("weights.inp", "w+");
	fprintf(fp, "%d\n", MAX);	
	for(i=0; i<MAX; i++)
	{		
		for(j=0; j<MAX; j++)
        {
			if (i==j)
			{weights[i][j]=0;
			fprintf(fp, "%d ",weights[i][j] );
			
			}
			else {
				weights[j][i]=weights[i][j];
				fprintf(fp, "%d ", weights[i][j]);
			}
			}
		fprintf(fp, "\n");
	}
fclose(fp);
	
return(1);
}//end inp_gen 

/*
	The input file (weights.inp) look something like this
		4
		0 0 0 21
		0 0 8 17
		0 8 0 16
		21 17 16 0

	The first line contains n, the number of nodes.
	Next is an nxn matrix containg the distances between the nodes
	NOTE: The distance between a node and itself should be 0

output looks like this
digraph finite_state_machine {
	rankdir=LR;
	size="10,10"
	node [shape = doublecircle]; LR_0 LR_3 LR_4 LR_8;
	node [shape = circle];
	LR_0 -> LR_2 [ label = "SS(B)" ];
	LR_8 -> LR_5 [ label = "S(a)" ];
}

*/

int n; /* The number of nodes in the graph */

int weight[MAX][MAX]; /* weight[i][j] is the distance between node i and node j;
			if there is no path between i and j, weight[i][j] should
			be 0 */

char inTree[MAX]; /* inTree[i] is 1 if the node i is already in the minimum
			spanning tree; 0 otherwise*/

int d[MAX]; /* d[i] is the distance between node i and the minimum spanning
		tree; this is initially infinity (100000); if i is already in
		the tree, then d[i] is undefined;
		this is just a temporary variable. It's not necessary but speeds
		up execution considerably (by a factor of n) */

int whoTo[MAX]; /* whoTo[i] holds the index of the node i would have to be
			linked to in order to get a distance of d[i] */

/* updateDistances(int target)
	should be called immediately after target is added to the tree;
	updates d so that the values are correct (goes through target's
	neighbours making sure that the distances between them and the tree
	are indeed minimum)
*/
void updateDistances(int target) {
	int i;
	for (i = 0; i < n; ++i)
		if ((weight[target][i] != 0) && (d[i] > weight[target][i])) {
			d[i] = weight[target][i];
			whoTo[i] = target;
		}
}

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

	if(!inp_gen())perror("Cannot open input File!");


	FILE *f = fopen("weights.inp", "r");
	fscanf(f, "%d", &n);

	if (n > MAX)
		{
		printf("%d is too large, %d is max!\n", n,MAX);
		exit(0);
		}
	
	printf("graph G{\n");
	printf("rankdir=LR;");
	printf("size=\"10,10\"\n");
	printf("node [shape = circle];\n");

	
	int i, j;
	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
	        fscanf(f, "%d", &weight[i][j]);
	fclose(f);

	/* Initialise d with infinity */
	for (i = 0; i < n; ++i)
		d[i] = 100000;

	/* Mark all nodes as NOT being in the minimum spanning tree */
	for (i = 0; i < n; ++i)
		inTree[i] = 0;

	/* Add the first node to the tree */
	//printf("Adding node %c\n", 0 + 'A');
	inTree[0] = 1;
	updateDistances(0);

	int total = 0;
	int treeSize;
	for (treeSize = 1; treeSize < n; ++treeSize) {
		/* Find the node with the smallest distance to the tree */
		int min = -1;
		for (i = 0; i < n; ++i)
			if (!inTree[i])
				if ((min == -1) || (d[min] > d[i]))
					min = i;

		/* And add it */
	//	printf("%d--%d [ color = \"blue\" label = \"%d\"];\n", whoTo[min], min, d[min]);
		list[whoTo[min]].head=whoTo[min];
		list[whoTo[min]].tail=min;
		list[whoTo[min]].nid=d[min];
		printf("%d--%d [ label = \"%d\"];\n", list[whoTo[min]].head, list[whoTo[min]].tail, list[whoTo[min]].nid);
		//printf("%d--%d [ label = \"%d\"];\n", whoTo[min], min, d[min]);
		inTree[min] = 1;
		total += d[min];

		updateDistances(min);
	}

	printf("label =\"Minimum Distance = %d\";\n", total);
	printf("}\n");

	return 0;
}