Minimal Spanning Tree algorithm by V. Kevin .M. Whitney

/*
This file contains a driver program, the function spantree,
an example input file, and an example output file. Do not
attempt to compile the C source code listed here until you
copy the input and output files to spantree.in and
spantree.output and then remove those lines from the bottom
of this file.
*/


#include
#include
#include
#include

int spantree( double **graph, int **min_span_tree, int n,
int *p_num_of_edges, double *p_sum_of_edges);

FILE *in, *out;


#define npts 9

/*-------------------------------------------------------------------------
This is a driver program for testing the Minimal Spanning Tree function.

in File handle for input file called spantree.in
out File handle for output file called spantree.out
graph 2D array used to store the edge weights of the graph.
npts number of points to be connected by the minimal spanning tree (MST)
buf1 temporary string buffer
*p character pointer used for the string tokenizer
n_mst number of edges in the MST
sum_mst sum of the edge weights in the MST

min_span_tree 2D array output by function spantree(). It holds the "to" and
"from" indices for each edge in the MST.
-------------------------------------------------------------------------*/

int main()
{
int i,j, n_mst;
double **graph, sum_mst;
int **min_span_tree;
char names[npts][3];
char buf1[82];
char *p;


if( ( in = fopen("spantree.in","r") ) == NULL )
{
printf(" ERROR opening file spantree.in ! \n");
return(1);
}


if( ( out = fopen("spantree.out","w") ) == NULL )
{
printf(" ERROR opening file spantree.out ! \n");
return(1);
}

graph = malloc( (npts)*sizeof(double *));
for( i=0; i < npts; i++)
{
graph[i] = malloc( (npts)*sizeof(double) );
if (!graph[i]) {
printf("memory request failed for graph matrix ! \n");
exit(1);
}
}

min_span_tree = malloc( (npts - 1)*sizeof(int *));
for( i=0; i < npts - 1; i++)
{
min_span_tree[i] = malloc( (2)*sizeof(int) );
if (!min_span_tree[i]) {
printf("memory request failed for min_span_tree matrix ! \n");
exit(1);
}
}

/* Read in the two header lines at the top of the input file */
fgets(buf1,80,in);
printf("%s",buf1);
fgets(buf1,80,in);
printf("%s",buf1);


/* read in the 2D graph array */
for( i=0; i < npts; i++ )
{
fgets(buf1,80,in);
p = strtok(buf1," ");
strcpy(names[i],p);
j = 0;
do {
p = strtok('\0'," ");
if( p && j < npts )
{
graph[i][j] = atof(p);
j++;
}
} while(p);
}

for( i=0; i < npts; i++ )
{
printf("%-2s ",names[i]);
for( j=0; j < npts; j++ )
{
printf("%6.1lf ",graph[i][j]);
}
printf("\n");
} /* end of loop to read in "npts" lines of data from graph array */


/* write out column headings for the output file */
fprintf(out," ",names[i]);
for( i=0; i < npts; i++ )
fprintf(out," %-2s",names[i]);
fprintf(out,"\n");

/* output the 2D graph array */
for( i=0; i < npts; i++ )
{
fprintf(out,"%-2s ",names[i]);
for( j=0; j < npts; j++ )
{
fprintf(out,"%6.1lf ",graph[i][j]);
}
fprintf(out,"\n");
} /* end of loop to read in "npts" lines of data from graph array */


/* call the spantree function to find the minimal spanning tree */
i = spantree( graph, min_span_tree, npts, &n_mst, &sum_mst );
if( i != 0 ) printf(" Error returned from spantree: %d\n",i);


/* output the minimal spanning tree to the output file called spantree.out */
fprintf(out,"\n\n Minimal Spanning Tree: \n\n");
printf("\n\n Minimal Spanning Tree: \n\n");
for( i = 0; i < npts - 1; i++ )
{
fprintf(out," %2d %2d %-2s %-2s \n",min_span_tree[i][0],min_span_tree[i][1],
names[ min_span_tree[i][0] ], names[ min_span_tree[i][1] ] );
printf(" %2d %2d %-2s %-2s \n",min_span_tree[i][0],min_span_tree[i][1],
names[ min_span_tree[i][0] ], names[ min_span_tree[i][1] ] );
}
fprintf(out,"\n\n Number of edges in Minimal Spanning Tree: %d\n\n",n_mst);
printf("\n\n Number of edges in Minimal Spanning Tree: %d\n\n",n_mst);
fprintf(out,"\n\n Sum of edges in Minimal Spanning Tree: %lf\n\n",sum_mst);
printf("\n\n Sum of edges in Minimal Spanning Tree: %lf\n\n",sum_mst);

fclose(in);
fclose(out);

for( i=0; i < npts; i++)
free(graph[i]);
for( i=0; i < npts - 1; i++)
free(min_span_tree[i]);

return(0);
}

/*-------------------------------------------------------------------------
This is the spantree function.

int spantree( double **graph, int **min_span_tree, int n,
int *p_num_of_edges, double *p_sum_of_edges)

This C function is a modified version of a Fortran subroutine originally
published by V.K.M. Whitney in Communications of the Association for
Computing Machinery (ACM) in 1972, Algorithm 422 minimal spanning tree [H],
15(4), 273-274. The Fortran code has been recently digitized and is
available as file 422 from the ACM at http://www.acm.org/calgo/contents/.
Because the algorithm in this C code has been modified, the ACM is not
responsible for its accuracy. This C code may contain material copyrighted
by ACM. Please view the ACM copyright agreement at:
http://www.acm.org/pubs/copyright_policy/softwareCRnotice.html

Input variables
---------------
**graph 2D matrix holding representing the graph
n the number of nodes in the graph

Output variables
----------------
**min_span_tree 2D matrix holding the station indices for each edge
in the minimal spanning tree (MST).
*p_num_of_edges number of edges in the MST.
*p_sum_of_edges sum of all edge weights in the MST.

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

int spantree( double **graph, int **min_span_tree, int n,
int *p_num_of_edges, double *p_sum_of_edges)
{
int i,best_node,new_node,num_nodes_outside, num_of_edges;
int *closest_existing_node,*not_in_tree,outside_node;
int all_nodes_in_tree = 0;
double *smallest_edges, edge_weight, best_edge, sum_of_edges;

/* allocate memory for arrays */
closest_existing_node = malloc( (n)*sizeof(int) );
if (!closest_existing_node) {
printf(" In spantree, memory request failed for closest_existing_node matrix ! \n");
return(1);
}

not_in_tree = malloc( (n)*sizeof(int) );
if (!not_in_tree) {
printf(" In spantree, memory request failed for not_in_tree matrix ! \n");
return(2);
}

smallest_edges = malloc( (n)*sizeof(double) );
if (!smallest_edges) {
printf(" In spantree, memory request failed for smallest_edges matrix ! \n");
return(3);
}

/* initialize the node label arrays */
sum_of_edges = 0.0;
num_nodes_outside = n - 1;
new_node = n - 1; /* the last node is the first node in the MST */
num_of_edges = 0;

for( i = 0; i < num_nodes_outside; i++ )
{
not_in_tree[i] = i;
smallest_edges[i] = graph[i][new_node];
closest_existing_node[i] = new_node;
}

/* update labels of nodes not yet in tree */
while( !all_nodes_in_tree )
{
for( i = 0; i < num_nodes_outside; i++ )
{
outside_node = not_in_tree[i];
edge_weight = graph[outside_node][new_node];
if( smallest_edges[i] <= edge_weight ) continue;
smallest_edges[i] = edge_weight;
closest_existing_node[i] = new_node;
}

/* find node outside tree nearest to tree */
best_edge = smallest_edges[0]; /* to start, assume 1st edge is closest */
for( i = 0; i < num_nodes_outside; i++ )
{
if( smallest_edges[i] > best_edge ) continue;
best_edge = smallest_edges[i];
best_node = i;
}

/* put nodes of appropriate edge into array mst */
min_span_tree[num_of_edges][0] = not_in_tree[best_node];
min_span_tree[num_of_edges][1] = closest_existing_node[best_node];
sum_of_edges = sum_of_edges + best_edge;
new_node = not_in_tree[best_node];
num_of_edges++;

/* delete new tree node from array not_in_tree by replacing it with
the last node in not_in_tree[], then decrement the number of
nodes not yet in the tree */
smallest_edges[best_node] = smallest_edges[num_nodes_outside - 1];
not_in_tree[best_node] = not_in_tree[num_nodes_outside - 1];
closest_existing_node[best_node] = closest_existing_node[num_nodes_outside - 1];
num_nodes_outside--;
if( num_nodes_outside == 0 ) all_nodes_in_tree = num_of_edges;

} /* finish while loop when all nodes are in tree */

*p_num_of_edges = num_of_edges;
*p_sum_of_edges = sum_of_edges;

/* free memory */
free( closest_existing_node );
free( not_in_tree );
free( smallest_edges );

return(0);
}
============== spantree.in =================================================
Name Distances between cities in miles
---- ---------------------------------------------------------------------
A 0.0 60.2 62.6 68.9 114.4 68.9 124.8 136.5 83.6
B 60.2 0.0 122.6 31.3 70.8 67.8 180.4 120.7 32.9
C 62.6 122.6 0.0 126.2 168.4 108.8 79.6 170.4 145.2
D 68.9 31.3 126.2 0.0 46.2 42.4 193.6 89.4 60.9
E 114.4 70.8 168.4 46.2 0.0 65.7 239.0 68.8 89.3
F 68.9 67.8 108.8 42.4 65.7 0.0 185.1 67.6 100.4
G 124.8 180.4 79.6 193.6 239.0 185.1 0.0 249.2 192.5
H 136.5 120.7 170.4 89.4 68.8 67.6 249.2 0.0 148.5
I 83.6 32.9 145.2 60.9 89.3 100.4 192.5 148.5 0.0
============== spantree.output =============================================

A B C D E F G H I
A 0.0 60.2 62.6 68.9 114.4 68.9 124.8 136.5 83.6
B 60.2 0.0 122.6 31.3 70.8 67.8 180.4 120.7 32.9
C 62.6 122.6 0.0 126.2 168.4 108.8 79.6 170.4 145.2
D 68.9 31.3 126.2 0.0 46.2 42.4 193.6 89.4 60.9
E 114.4 70.8 168.4 46.2 0.0 65.7 239.0 68.8 89.3
F 68.9 67.8 108.8 42.4 65.7 0.0 185.1 67.6 100.4
G 124.8 180.4 79.6 193.6 239.0 185.1 0.0 249.2 192.5
H 136.5 120.7 170.4 89.4 68.8 67.6 249.2 0.0 148.5
I 83.6 32.9 145.2 60.9 89.3 100.4 192.5 148.5 0.0


Minimal Spanning Tree:

1 8 B I
3 1 D B
5 3 F D
4 3 E D
0 1 A B
2 0 C A
7 5 H F
6 2 G C


Number of edges in Minimal Spanning Tree: 8



Sum of edges in Minimal Spanning Tree: 422.800000

============== end of file span-c.txt ======================================