#! /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