/* 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 ======================================