#! /bin/sh # This is a shell archive, meaning: # 1. Remove everything above the #! /bin/sh line. # 2. Save the resulting text in a file. # 3. Execute the file with /bin/sh (not csh) to create the files: # Doc/ # Doc/email # Fortran77/ # Fortran77/Drivers/ # Fortran77/Drivers/Dp/ # Fortran77/Drivers/Dp/data # Fortran77/Drivers/Dp/driver.f # Fortran77/Drivers/Dp/res # Fortran77/Src/ # Fortran77/Src/Dp/ # Fortran77/Src/Dp/src.f # This archive created: Mon Oct 4 14:09:39 1999 export PATH; PATH=/bin:$PATH if test ! -d 'Doc' then mkdir 'Doc' fi cd 'Doc' if test -f 'email' then echo shar: will not over-write existing file "'email'" else cat << SHAR_EOF > 'email' (Message /home/cur/trh/.Mail/inbox:4071) Return-Path: Received: from mercury.ukc.ac.uk by ash.ukc.ac.uk (SMI-8.6/UKC-2.14) id QAA25223; Thu, 16 Sep 1999 16:00:03 +0100 Received: from hercules.ngs.noaa.gov ([140.90.111.153] helo=gpserver.ngs.noaa.gov ident=steveh) by mercury.ukc.ac.uk with esmtp (Exim 2.12 #1) id 11Rd0R-0000tb-00 for T.R.Hopkins@ukc.ac.uk; Thu, 16 Sep 1999 15:59:27 +0100 Received: (from steveh@localhost) by gpserver.ngs.noaa.gov (8.8.6 (PHNE_17135)/8.8.6) id KAA05534; Thu, 16 Sep 1999 10:55:47 -0400 (EDT) From: Steve Hilla Message-Id: <199909161455.KAA05534@gpserver.ngs.noaa.gov> Subject: Algorithm 422 by V.Kevin M. Whitney To: T.R.Hopkins@ukc.ac.uk Date: Thu, 16 Sep 1999 10:55:46 EDT Cc: steveh@ngs.noaa.gov X-Mailer: Elm [revision: 212.4] Dear Tim, I went ahead a made a driver program for Algorithm 422 as you requested. I have added a few additional notes to Whitney's subroutine so that folks can understand exactly how it works. I have tested this driver program on a Pentium PC using WATCOM Fortran 77 under Windows NT 4.0 and also on a Hewlett Packard UNIX workstation running HP-UX 10.x. The keywords in Whitney's paper were: spanning tree, minimal spanning tree, maximal spanning tree In the file below, spantr.for, I have added the example input file and output file at the end of the file. These lines will need to be copied and then removed before compiling the Fortran code. Thanks again for adding this to your web site. I hope other folks find it as useful as I have. Regards, Steve Hilla National Geodetic Survey, NOAA Silver Spring, Maryland 20910 steveh@ngs.noaa.gov ----------------------------------------------------------------------------- SHAR_EOF fi # end of overwriting check cd .. if test ! -d 'Fortran77' then mkdir 'Fortran77' fi cd 'Fortran77' if test ! -d 'Drivers' then mkdir 'Drivers' fi cd 'Drivers' if test ! -d 'Dp' then mkdir 'Dp' fi cd 'Dp' if test -f 'data' then echo shar: will not over-write existing file "'data'" else cat << SHAR_EOF > 'data' City Name Distances between cities in miles ----------- ---------------------------------------- Ann Arbor 0.0 38.0 55.0 131.0 97.0 62.0 Detroit 38.0 0.0 57.0 156.0 142.0 84.0 Flint 55.0 57.0 0.0 107.0 126.0 51.0 Grand Rapids 131.0 156.0 107.0 0.0 52.0 66.0 Kalamazoo 97.0 142.0 126.0 52.0 0.0 75.0 Lansing 62.0 84.0 51.0 66.0 75.0 0.0 SHAR_EOF fi # end of overwriting check if test -f 'driver.f' then echo shar: will not over-write existing file "'driver.f'" else cat << SHAR_EOF > 'driver.f' PROGRAM SPANTR c c A driver program to demonstrate Algorithm 422. c This example shows how to find the minimum spanning c tree which connects 6 large cities in Michigan. c A graph which stores the distances in miles between c each city is read in as file spantr.in and is then c used to load array bgraph(6,6). The output file c lists the edges which make up the minimal spanning c tree, these edges are stored in array mstree(2,6). c This driver program was compiled and tested using c Fortran 77. c c Note: The input file spantr.in should contain only c eight lines; two header lines and then six lines c containing the six city names and the 6-by-6 matrix c of distances between these cities (in miles). c c buf1 is an 80-char scratch buffer c sname(6) holds the 14-char city names c bgraph(50,50) holds the graph and the edges between the 6 nodes c mstree(2,50) holds the nodes for the minimal spanning tree c numbls is the number of edges in the minimal spanning tree c sumlen is the sum of the edge lengths in the minimal c spanning tree c c C .. Local Scalars .. DOUBLE PRECISION SUMLEN INTEGER I,J,NIN,NOUT,NUMBLS CHARACTER*80 BUF1 C .. C .. Local Arrays .. DOUBLE PRECISION BGRAPH(NMAX,NMAX) INTEGER MSTREE(2,NMAX) CHARACTER*14 SNAME(NMAX) C .. C .. External Subroutines .. EXTERNAL DMTOMS C .. C OPEN (10,FILE='data',STATUS='old',ERR=30) C OPEN (20,FILE='res',STATUS='unknown',ERR=40) c C Use port library routine to set default input and C output channels C C .. Parameters .. INTEGER NMAX PARAMETER (NMAX=50) C .. C .. External Functions .. INTEGER I1MACH EXTERNAL I1MACH C .. NIN = I1MACH(1) NOUT = I1MACH(2) READ (NIN,FMT='(a)') BUF1 WRITE (NOUT,FMT='(//,1x,a)') BUF1 READ (NIN,FMT='(a)') BUF1 WRITE (NOUT,FMT='(1x,a)') BUF1 DO 10 I = 1,6 READ (NIN,FMT=9000) SNAME(I), (BGRAPH(I,J),J=1,6) WRITE (NOUT,FMT=9010) SNAME(I), (BGRAPH(I,J),J=1,6) 10 CONTINUE C CLOSE (10) c CALL DMTOMS(BGRAPH,6,MSTREE,NUMBLS,SUMLEN) c WRITE (NOUT,FMT= + '(//,'' number of edges in minimal spanning tree = '', i8)') + NUMBLS WRITE (NOUT,FMT='(/,'' sum of the edges (miles) = '',f8.4,//)') + SUMLEN DO 20 I = 1,NUMBLS WRITE (NOUT,FMT='('' from,to: '',2i4,2x,2a18)') MSTREE(1,I), + MSTREE(2,I),SNAME(MSTREE(1,I)),SNAME(MSTREE(2,I)) 20 CONTINUE C CLOSE (20) STOP c C 30 WRITE(NOUT,FMT='(//,'' Error opening spantr.in !! '',/)') C STOP C 40 WRITE(NOUT,FMT='(//,'' Error opening spantr.out !! '',/)') C STOP 9000 FORMAT (A14,6F7.1) 9010 FORMAT (1X,A14,6F7.1) END SHAR_EOF fi # end of overwriting check if test -f 'res' then echo shar: will not over-write existing file "'res'" else cat << SHAR_EOF > 'res' number of edges in minimal spanning tree = 5 sum of the edges (miles) = 262.0000 from,to: 3 6 Flint Lansing from,to: 1 3 Ann Arbor Flint from,to: 2 1 Detroit Ann Arbor from,to: 4 6 Grand Rapids Lansing from,to: 5 4 Kalamazoo Grand Rapids SHAR_EOF fi # end of overwriting check cd .. cd .. if test ! -d 'Src' then mkdir 'Src' fi cd 'Src' if test ! -d 'Dp' then mkdir 'Dp' fi cd 'Dp' if test -f 'src.f' then echo shar: will not over-write existing file "'src.f'" else cat << SHAR_EOF > 'src.f' C---------------------------------------------------------------- SUBROUTINE DMTOMS(DM,N,MST,IMST,CST) C C THIS SUBROUTINE FINDS A SET OF EDGES OF A LINEAR GRAPH C COMPRISING A TREE WITH MINIMAL TOTAL EDGE LENGTH. THE C GRAPH IS SPECIFIED AS AN ARRAY OF INTER-NODE EDGE LENGTHS. C THE EDGES OF THE MINIMAL SPANNING TREE OF THE GRAPH ARE C PLACED IN ARRAY MST. EXECUTION TIME IS PROPORTIONAL TO C THE SQUARE OF THE NUMBER OF NODES. C C C ADDITIONAL NOTES: C ----------------- C C This code is taken from "Algorithm 422 Minimal Spanning Tree [H]" C by V. Kevin M. Whitney, Communications of the ACM, April 1972, C Volume 15, Number 4, pages 273-274. It has been digitized on C September 16, 1999 so it can be added to the CALGO collection of C algorithms made available by the ACM. The code has been modified C slightly so it could be compiled and tested using Fortran 77. C C The algorithm uses a technique suggested by E.W. Dijkstra in C "A note on two problems in connection with graphs", C Numer. Math. 1, 5 (Oct. 1959), 269-271. C C from Whitney: C "The Dijkstra algorithm grows a minimal spanning tree by successively C adjoining the nearest remaining node to a partially formed tree until C all nodes of the graph are included in the tree. At each iterative C step the nodes not yet included in the tree are stored in array NIT. C The node of the partially completed tree nearest to node NIT(I) is C stored in JI(I), and the length of edge from NIT(I) to JI(I) is stored C in UI(I). Hence the node not yet in the tree which is nearest to a C node of the tree may be found by searching for the minimal element of C array UI. That node, KP, is added to the tree and removed from array C NIT. For each node remaining in array NIT, the distance from the C nearest node of the tree (stored in array UI) is compared to the C distance from KP, the new node of the tree, and arrays UI and JI are C updated if the new distance is shorter. The nearest node selection C and list updating are performed N - 1 times until all nodes are in C the tree." C C Diagonal elements of array DM are not used. The edges of the output C minimal spanning tree are specified by pairs of nodes in array MST. C If the graph represented by the inter-node edge length array DM is C not connected, the procedure will generate a minimal spanning forest C containing the minimal spanning trees of the disjoint components C joined together by edges of length 10.**10. A disconnected graph C is indicated by a value 10.**10 for variable UK at step 500 during C execution of the algorithm. This algorithm can also be used to find C a maximal spanning tree by changing the loop between statements 300 C and 400 to search for the most distant rather than for the nearest C remaining node to be adjoined to the partially completed tree. C C C CALLING SEQUENCE VARIABLES ARE: C C DM ARRAY OF INTER-NODE EDGE LENGTHS. C DM(I,J) (1 .LE. I,J .LE. IN) IS THE LENGTH OF C AN EDGE FROM NODE I TO NODE J. IF THERE IS NO C EDGE FROM NODE I TO NODE J, SET DM(I,J)=10.**10 C N NODES ARE NUMBERED 1, 2, ..., N. C C MST ARRAY IN WHICH EDGE LIST OF MST IS PLACED. MST(1,I) C IS THE ORIGINAL NODE AND MST(2,I) IS THE TERMINAL C NODE OF EDGE I FOR 1 .LE. I .LE. IMST. C IMST NUMBER OF EDGES IN ARRAY MST. C CST SUM OF EDGE LENGTHS OF EDGES OF TREE. C C PROGRAM VARIABLES : C C NIT ARRAY OF NODES NOT YET IN TREE. C NITP NUMBER OF NODES IN ARRAY NIT. C JI(I) NODE OF PARTIAL MST CLOSEST TO NODE NIT(I). C UI(I) LENGTH OF EDGE FROM NIT(I) TO JI(I). C KP NEXT NODE TO BE ADDED TO ARRAY MST. C C C INITIALIZE NODE LABEL ARRAYS C C .. Scalar Arguments .. DOUBLE PRECISION CST INTEGER IMST,N C .. C .. Array Arguments .. DOUBLE PRECISION DM(NMAX,NMAX) INTEGER MST(2,NMAX) C .. C .. Local Scalars .. DOUBLE PRECISION D,UK INTEGER I,K,KP,NI,NITP C .. C .. Local Arrays .. DOUBLE PRECISION UI(NMAX) INTEGER JI(NMAX),NIT(NMAX) C .. C .. Parameters .. INTEGER NMAX PARAMETER (NMAX=50) C .. CST = 0.0D0 NITP = N - 1 KP = N IMST = 0 DO 10 I = 1,NITP NIT(I) = I UI(I) = DM(I,KP) JI(I) = KP 10 CONTINUE C C UPDATE LABELS OF NODES NOT YET IN TREE. C 20 DO 30 I = 1,NITP NI = NIT(I) D = DM(NI,KP) IF (UI(I).LE.D) GO TO 30 UI(I) = D JI(I) = KP 30 CONTINUE C C FIND NODE OUTSIDE TREE NEAREST TO TREE. C UK = UI(1) DO 40 I = 1,NITP IF (UI(I).GT.UK) GO TO 40 UK = UI(I) K = I 40 CONTINUE C C PUT NODES OF APPROPRIATE EDGE INTO ARRAY MST. C IMST = IMST + 1 MST(1,IMST) = NIT(K) MST(2,IMST) = JI(K) CST = CST + UK KP = NIT(K) C C DELETE NEW TREE NODE FROM ARRAY NIT. C UI(K) = UI(NITP) NIT(K) = NIT(NITP) JI(K) = JI(NITP) NITP = NITP - 1 50 IF (NITP.NE.0) GO TO 20 C C WHEN ALL NODES ARE IN TREE, QUIT. C RETURN END SHAR_EOF fi # end of overwriting check cd .. cd .. cd .. # End of shell archive exit 0