-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path422listingrun.txt
405 lines (362 loc) · 14.9 KB
/
422listingrun.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ gfortran driver.f -c
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ gfortran -o 422run driver.o src.o
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ ./422run
^C
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ ls
422run brew data driver.f driver.o res src.f src.o
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ ./422run < 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
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
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ cat 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 ..
PARAMETER (NMAX=50)
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 ..
OPEN (10,FILE='data',STATUS='old',ERR=30)
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 ..
C INTEGER NMAX
C PARAMETER (NMAX=50)
C ..
C .. External Functions ..
C INTEGER I1MACH
C EXTERNAL I1MACH
C real r1mach
C ..
NIN = 5
C NOUT = 6
READ (5,FMT='(a)') BUF1
WRITE (6,FMT='(//,1x,a)') BUF1
READ (5,FMT='(a)') BUF1
WRITE (6,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 (6)
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
30 WRITE(NOUT,FMT='(//,'' Error opening spantr.in !! '',/)')
STOP
40 WRITE(NOUT,FMT='(//,'' Error opening spantr.out !! '',/)')
STOP
9000 FORMAT (A14,6F7.1)
9010 FORMAT (1X,A14,6F7.1)
END
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ cat 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 .
INTEGER NMAX
PARAMETER (NMAX=50)
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 ..
C 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
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ sloccount 422.sh
WARNING!!! Not a file nor a directory (so ignored): 422.sh
Categorizing files.
Skipping non-directory *
Computing results.
SLOC Directory SLOC-by-Language (Sorted)
SLOC total is zero, no further analysis performed.
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ sloccount driver.f || src.f
Have a non-directory at the top, so creating directory top_dir
Adding /home/ian/Downloads/422dir/Fortran77/Drivers/Dp/driver.f to top_dir
Categorizing files.
Finding a working MD5 command....
Found a working MD5 command.
Computing results.
SLOC Directory SLOC-by-Language (Sorted)
38 top_dir fortran=38
Totals grouped by language (dominant language first):
fortran: 38 (100.00%)
Total Physical Source Lines of Code (SLOC) = 38
Development Effort Estimate, Person-Years (Person-Months) = 0.01 (0.08)
(Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
Schedule Estimate, Years (Months) = 0.08 (0.95)
(Basic COCOMO model, Months = 2.5 * (person-months**0.38))
Estimated Average Number of Developers (Effort/Schedule) = 0.08
Total Estimated Cost to Develop = $ 872
(average salary = $56,286/year, overhead = 2.40).
SLOCCount, Copyright (C) 2001-2004 David A. Wheeler
SLOCCount is Open Source Software/Free Software, licensed under the GNU GPL.
SLOCCount comes with ABSOLUTELY NO WARRANTY, and you are welcome to
redistribute it under certain conditions as specified by the GNU GPL license;
see the documentation for details.
Please credit this data as "generated using David A. Wheeler's 'SLOCCount'."
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ sloccount driver.f
Have a non-directory at the top, so creating directory top_dir
Adding /home/ian/Downloads/422dir/Fortran77/Drivers/Dp/driver.f to top_dir
Categorizing files.
Finding a working MD5 command....
Found a working MD5 command.
Computing results.
SLOC Directory SLOC-by-Language (Sorted)
38 top_dir fortran=38
Totals grouped by language (dominant language first):
fortran: 38 (100.00%)
Total Physical Source Lines of Code (SLOC) = 38
Development Effort Estimate, Person-Years (Person-Months) = 0.01 (0.08)
(Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
Schedule Estimate, Years (Months) = 0.08 (0.95)
(Basic COCOMO model, Months = 2.5 * (person-months**0.38))
Estimated Average Number of Developers (Effort/Schedule) = 0.08
Total Estimated Cost to Develop = $ 872
(average salary = $56,286/year, overhead = 2.40).
SLOCCount, Copyright (C) 2001-2004 David A. Wheeler
SLOCCount is Open Source Software/Free Software, licensed under the GNU GPL.
SLOCCount comes with ABSOLUTELY NO WARRANTY, and you are welcome to
redistribute it under certain conditions as specified by the GNU GPL license;
see the documentation for details.
Please credit this data as "generated using David A. Wheeler's 'SLOCCount'."
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ sloccount src.f
Have a non-directory at the top, so creating directory top_dir
Adding /home/ian/Downloads/422dir/Fortran77/Drivers/Dp/src.f to top_dir
Categorizing files.
Finding a working MD5 command....
Found a working MD5 command.
Computing results.
SLOC Directory SLOC-by-Language (Sorted)
45 top_dir fortran=45
Totals grouped by language (dominant language first):
fortran: 45 (100.00%)
Total Physical Source Lines of Code (SLOC) = 45
Development Effort Estimate, Person-Years (Person-Months) = 0.01 (0.09)
(Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
Schedule Estimate, Years (Months) = 0.08 (1.01)
(Basic COCOMO model, Months = 2.5 * (person-months**0.38))
Estimated Average Number of Developers (Effort/Schedule) = 0.09
Total Estimated Cost to Develop = $ 1,041
(average salary = $56,286/year, overhead = 2.40).
SLOCCount, Copyright (C) 2001-2004 David A. Wheeler
SLOCCount is Open Source Software/Free Software, licensed under the GNU GPL.
SLOCCount comes with ABSOLUTELY NO WARRANTY, and you are welcome to
redistribute it under certain conditions as specified by the GNU GPL license;
see the documentation for details.
Please credit this data as "generated using David A. Wheeler's 'SLOCCount'."
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ cat 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
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$ cat 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
ian@ian-HP-Stream-Notebook-PC-11:~/Downloads/422dir/Fortran77/Drivers/Dp$