/*Tyler A. Simon
prims_directed.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_directed prims_directed.c
To Run:
./prims_directed | dot -Tgif -o graph_di.gif; display graph_di.gif &
circo -Tgif problem.dat > problem_di.gif; display problem_di.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 

int inp_gen(){
FILE *fp;
FILE *gfp;
int i,j;
int weights[MAX][MAX];
srand( (unsigned int)time( NULL ) );

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

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


fprintf(fp, "%d\n", MAX);
for(i=0; i<MAX; i++)
        {
        for(j=0; j<MAX; j++)
                {
                if (j == i)
                        {
                        fprintf(fp, "%d ", 0);
                        weights[i][j]=0;
                        }
                else
                        {
                        weights[i][j]=rand()%(2*MAX+1);
                        fprintf(fp, "%d ", weights[i][j]);
		fprintf(gfp,"%d->%d [ label = \"%d\"];\n", i, j, weights[i][j]);
                        }

                }
		
        fprintf(fp, "\n");
        }
		fprintf(gfp,"}\n");
fclose(fp);
fclose(gfp);

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("digraph G{\n");
	printf("rankdir=LR;");
	printf("size=\"50,50\"\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("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');
		printf("%d->%d [ color = \"blue\" label = \"%d\"];\n", whoTo[min], min, d[min]);
		//LR_0 -> LR_2 [ label = "SS(B)" ];
		inTree[min] = 1;
		total += d[min];

		updateDistances(min);
	}

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

	return 0;
}