/[escript]/trunk/paso/src/SystemMatrixPattern_reduceBandwidth.c
ViewVC logotype

Contents of /trunk/paso/src/SystemMatrixPattern_reduceBandwidth.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1049 - (show annotations)
Tue Mar 20 03:00:18 2007 UTC (12 years, 2 months ago) by gross
File MIME type: text/plain
File size: 25598 byte(s)
bandwidth optimizer has been moved back (Lutz: switch on your brain.
)
1
2 /*
3 ********************************************************************************
4 * Copyright 2006 by ACcESS MNRF *
5 * *
6 * http://www.access.edu.au *
7 * Primary Business: Queensland, Australia *
8 * Licensed under the Open Software License version 3.0 *
9 * http://www.opensource.org/licenses/osl-3.0.php *
10 ********************************************************************************
11 */
12
13 /* Finley_Reduce determines a row and column permutation which, when applied to a given sparse matrix, produces a permuted */
14 /* matrix with a smaller bandwidth and profile. the input array is a connection table which represents the */
15 /* indices of the nonzero elements of the matrix, a. the algorithm is described in terms of the adjacency graph which */
16 /* has the characteristic that there is an edge (connection) between nodes i and j if a(i,j) .ne. 0 and i .ne. j. */
17
18
19 /* NDSTK(NR,D1) D1 IS >= MAXIMUM DEGREE OF ALL NODES.
20 /* Label(D2) D2 AND NR ARE >= THE TOTAL NUMBER OF
21 /* NewLabel(D2+1) NODES IN THE GRAPH.
22 /* Degree(D2) STORAGE REQUIREMENTS CAN BE SIGNifICANTLY
23
24 /* AssignedLevel(D2) DECREASED FOR IBM 360 AND 370 COMPUTERS
25 /* LevelToNode(D2) BY REPLACING INTEGER NDSTK BY
26 /* NodeToLevel(D2) INTEGER*2 NDSTK IN SUBROUTINES Finley_Reduce,
27 /* ConnectedComponents(D2) Finley_Reduce_setDegree, Finley_Reduce_findDiameter, Finley_Reduce_dropTree AND NUMBER.
28 /* COMMON INFORMATION--THE FOLLOWING COMMON BLOCK MUST BE IN THE
29 /* CALLING ROUTINE.
30 /* COMMON/GRA/N,IDPTH,ndeg_max
31 /* EXPLANATION OF INPUT VARIABLES--
32 /* NDSTK- CONNECTION TABLE REPRESENTING GRAPH.
33 /* pattern->index[iptr]=NODE NUMBER OF JTH CONNECTION TO NODE
34 /* NUMBER I. A CONNECTION OF A NODE TO ITSELF IS NOT
35 /* LISTED. EXTRA POSITIONS MUST HAVE ZERO FILL.
36 /* NR- ROW DIMENSION ASSIGNED NDSTK IN CALLING PROGRAM.
37 /* Label[i]- NUMBERING OF ITH NODE UPON INPUT. if NO NUMBERING EXISTS THEN Label[i]=I.
38 /* N- NUMBER OF NODES IN GRAPH (EQUAL TO ORDER OF MATRIX).
39 /* ndeg_max- MAXIMUM DEGREE OF ANY NODE IN THE GRAPH.
40 /* Degree[i]- THE DEGREE OF THE ITH NODE.
41 /* EXPLANATION OF OUTPUT VARIABLES--
42 /* NewLabel[i]- THE NEW NUMBER FOR THE ITH NODE.
43 /* newBandwidth- THE BANDWIDTH AFTER numbering .
44 /* newProfile- THE PROFILE AFTER numbering .
45 /* IDPTH- NUMBER OF LEVELS IN Finley_Reduce LEVEL STRUCTURE.
46 /* */
47 /* The following only have meaning if the graph was connected:
48
49 /* AssignedLevel[i]- INDEX INTO LevelToNode TO THE FIRST NODE IN LEVEL I. AssignedLevel(I+1)-AssignedLevel[i]= number of nodes in ith leveL
50 /* LevelToNode- node numbers listed by level
51 /* NodeToLevel[i]- the level assigned to node i by Finley_Reduce.
52
53 /* WORKING STORAGE VARIABLE--
54 /* ConnectedComponents
55 /* LOCAL STORAGE--
56 /* COMMON/CC/-SUBROUTINES Finley_Reduce, SORT2 AND PIKAssignedLevel ASSUME THAT
57 /* THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
58 /* SUBROUTINE Finley_Reduce_findDiameter ASSUMES THAT THERE ARE AT MOST
59 /* 100 NODES IN THE LAST LEVEL.
60 /* COMMON/AssignedLevelW/-SUBROUTINES Finley_Reduce_setup AND PIKAssignedLevel ASSUME THAT THERE
61 /* ARE AT MOST 100 LEVELS.
62 SUBROUTINE Finley_Reduce(NDSTK, NR, Label, NewLabel, Degree, AssignedLevel, LevelToNode,NodeToLevel, ConnectedComponents, newBandwidth, newProfile, NIN, ndeg_maxIN)
63 /* USE INTEGER*2 NDSTK WITH AN IBM 360 OR 370.
64 integer NIN, ndeg_maxIN
65 INTEGER NDSTK
66 INTEGER StartNode, ReverseNode, NewLabel, ConnectedComponentCounter, SORT2, LastAvailableNodeNumber, ConnectedComponents,
67 * SIZE, STPT, FirstAvailableNodeNumber
68 COMMON /GRA/ N, IDPTH, ndeg_max
69 /* IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
70 COMMON /CC/ ConnectedComponentCounter, SIZE(50), STPT(50)
71 COMMON /AssignedLevelW/ NHIGH(100), NLOW(100), NACUM(100)
72 DIMENSION ConnectedComponents(1), Label(1)
73 DIMENSION NDSTK(NR,1), AssignedLevel(1), LevelToNode(1), NodeToLevel(1), NewLabel(1),
74 * Degree(1)
75 newBandwidth = 0
76 newProfile = 0
77 /* SET NewLabel[i]=0 FOR ALL I TO INDICATE NODE I IS UNNUMBERED
78 c
79 c N = NR
80 c do i=0,i<N,++i)
81 c if(ndeg_max<Degree[i]) then
82 c ndeg_max = Degree[i]
83 c end if
84 c end do
85 c
86
87 set Degree
88 N=NIN
89 ndeg_max = ndeg_maxIN
90 for (i=0,i<N,++i) {
91 Degree[i]=ptr[i+1]-ptr[i];
92 NewLabel[i] = 0;
93 }
94
95 /* COMPUTE DEGREE OF EACH NODE AND ORIGINAL BANDWIDTH AND PROFILE*/
96
97 CALL Finley_Reduce_setDegree(NDSTK, NR, Degree, Label, initialBandwidth, initialProfile)
98
99 /* FirstAvailableNodeNumber = low end of available numbers for numbering */
100 /* LastAvailableNodeNumber = high end of available numbers for numbering */
101 FirstAvailableNodeNumber = 1;
102 LastAvailableNodeNumber = N;
103
104 /* number the nodes of degree zero */
105
106 for (i=0,i<N,++i) {
107 if (Degree[i]==0) {
108 NewLabel[i] = LastAvailableNodeNumber;
109 LastAvailableNodeNumber--;
110 }
111 }
112 /* find an unnumbered node of min degree to start on */
113 while (FirstAvailableNodeNumber<=LastAvailableNodeNumber) {
114
115 LowestDegree = ndeg_max + 1;
116 Flag = 1;
117 SDIR = 1;
118 for (i=0,i<N,++i) {
119 if (Degree[i]<LowestDegree && NewLabel[i]<=0) {
120 LowestDegree = Degree[i];
121 StartNode = i;
122 }
123 }
124
125 /* find pseudo-diameter and associated level structures: */
126
127 /* StartNode and ReverseNode are the ends of the diameter and LevelToNode and NodeToLevel are the respective level structures. */
128
129 CALL Finley_Reduce_findDiameter(StartNode, ReverseNode, NDSTK, NR, Degree, AssignedLevel, LevelToNode,NodeToLevel, ConnectedComponents, IDFLT)
130 /* Flag INDICATES THE END TO BEGIN NUMBERING ON */
131 if (Degree(StartNode)>Degree(ReverseNode)) {
132 Flag = -1;
133 StartNode = ReverseNode;
134 }
135 CALL Finley_Reduce_setup(AssignedLevel, LevelToNode, NodeToLevel)
136 /* find all the connected components (ConnectedComponentCounter counts them) */
137 ConnectedComponentCounter = 0;
138 LROOT = 1
139 available_NodesInTree = 1
140 for (i=0,i<N,++i) {
141 if (AssignedLevel[i]==0) {
142 ConnectedComponentCounter++;
143 STPT(ConnectedComponentCounter) = LROOT
144 CALL Finley_Reduce_dropTree(I, NDSTK, NR, AssignedLevel, ConnectedComponents, Degree, LastLevelWidth, BottomLevel,available_NodesInTree, max_LevelWidth, N)
145 SIZE(ConnectedComponentCounter) = BottomLevel + LastLevelWidth - LROOT
146 LROOT = BottomLevel + LastLevelWidth
147 available_NodesInTree = LROOT
148 }
149 }
150 /* on return from PIKAssignedLevel, DirectionLargestComponent indicates the direction the largest component fell. */
151 /* DirectionLargestComponent is modIFied now to indicate the numbering direction. num is set to the proper value for this direction. */
152 if (SORT2(DMY)!=0) PIKAssignedLevel(LevelToNode, NodeToLevel, ConnectedComponents, IDFLT, DirectionLargestComponent)
153 DirectionLargestComponent = DirectionLargestComponent*Flag;
154 NUM= (DirectionLargestComponent<0) ? LastAvailableNodeNumber :FirstAvailableNodeNumber;
155
156 CALL NUMBER(StartNode, NUM, NDSTK, NodeToLevel, Degree, NewLabel, LevelToNode,
157 * AssignedLevel, NR, Flag, newBandwidth, newProfile, ConnectedComponents, DirectionLargestComponent)
158
159 /* update LastAvailableNodeNumber or FirstAvailableNodeNumber after numbering */
160
161 if (DirectionLargestComponent<0) LastAvailableNodeNumber = NUM;
162 if (DirectionLargestComponent>0) FirstAvailableNodeNumber = NUM;
163
164 }
165
166 /* if original numbering is better than new one, set up to return it */
167
168 if (newBandwidth > initialBandwidth) {
169 for (i=0,i<N,++i)
170 NewLabel[i] = Label[i];
171 *newBandwidth = initialBandwidth;
172 *newProfile = initialProfile;
173 }
174 }
175
176 /* Finley_Reduce_setDegree computes the degree of each node and stores it in the array Degree. */
177 /* the bandwidth and profile for the original or input numbering of the graph is computed also. */
178
179 void Finley_Reduce_setDegree( pattern, dim_t *Degree,dim_t* Label,dim_t *bandwidth,dim_t *initialProfile) {
180
181 *bandwidth = 0;
182 *profile = 0;
183 for (i=0,i<pattern->N,++i) {
184 Degree[i] = 0;
185 max_diff = 0;
186 for (iptr=pattern->ptr[i],iptr<pattern->ptr[i+1],++i) {
187 Degree[i] = Degree[i] + 1;
188 diff = Label[i] - Label(pattern->index[iptr]);
189 max_diff = MAX(max_diff,diff);
190 }
191 *profile + = max_diff;
192 *bandwidth=MAX(*bandwidth,max_diff);
193 }
194 }
195 /* Finley_Reduce_findDiameter is the control procedure for finding the pseudo-diameter of pattern */
196 /* as well as the level structure from each end */
197
198 /* StartNode- on input this is the node number of the first attempt at finding a diaMeter. */
199 /* on output it contains the actual number used.
200 /* EndNode- on output contains other end of diameter
201 /* LevelToNode- ARRAY CONTAINING LEVEL STRUCTURE WITH StartNode AS ROOT
202 /* NodeToLevel- ARRAY CONTAINING LEVEL STRUCTURE WITH EndNode AS ROOT
203 /* IDFLT- FLAG USED IN PICKING FINAL LEVEL STRUCTURE, SET
204 /* =1 if WIDTH OF LevelToNode <= WIDTH OF NodeToLevel, OTHERWISE =2
205 /* AssignedLevel,NodesInTree- WORKING STORAGE
206 void Finley_Reduce_findDiameter(index_t *StartNode,index_t *EndNode,PPP pattern, NR, Degree, AssignedLevel, LevelToNode,NodeToLevel, NodesInTree, IDFLT)
207 INTEGER NDSTK
208 INTEGER FLAG, StartNode2, StartNode, EndNode
209 COMMON /GRA/ N, IDPTH, ndeg_max
210 /* IT IS ASSUMED THAT THE LAST LEVEL HAS AT MOST 100 NODES.
211 COMMON /CC/ NDLST(100)
212 DIMENSION NDSTK(NR,1), Degree(1), AssignedLevel(1), LevelToNode(1), NodeToLevel(1),NodesInTree(1)
213 FLAG = 0;
214 MTW2 = N;
215 StartNode2 = StartNode;
216 10
217 /* zero AssignedLevel to indicate all nodes are available to Finley_Reduce_dropTree */
218 for (i=0,i<N,++i)
219 AssignedLevel[i] = 0;
220
221 available_NodesInTree = 1
222 /* drop a tree from StartNode2 */
223 CALL Finley_Reduce_dropTree(StartNode2, NDSTK, NR, AssignedLevel, NodesInTree, Degree, LastLevelWidth, BottomLevel,available_NodesInTree, max_LevelWidth, MTW2)
224 if (FLAG<1) {
225 FLAG = 1
226 30 IDPTH = available_NodesInTree - 1
227 MTW1 = max_LevelWidth
228 /* copy level structure into LevelToNode */
229 for (i=0,i<N,++i)
230 LevelToNode[i] = AssignedLevel[i];
231 NDXN = 1;
232 NDXL = 0;
233 MTW2 = N;
234 /* sort last level by degree and store in ndlst
235 CALL SORTDG(NDLST, NodesInTree(BottomLevel), NDXL, LastLevelWidth, Degree)
236 StartNode2 = NDLST(1)
237 GO TO 10
238 }
239 50 if (IDPTH>=available_NodesInTree-1) GO TO 60
240 /* START AGAIN WITH NEW STARTING NODE
241 StartNode = StartNode2
242 GO TO 30
243 60 if (max_LevelWidth>=MTW2) GO TO 80
244 MTW2 = max_LevelWidth
245 EndNode = StartNode2
246 /* STORE NARROWEST REVERSE LEVEL STRUCTURE IN NodeToLevel
247 for (70 i=0,i<N,++i)
248 NodeToLevel[i] = AssignedLevel[i]
249 70 CONTINUE
250 80 if (NDXN.EQ.NDXL) GO TO 90
251 /* TRY NEXT NODE IN NDLST
252 NDXN = NDXN + 1
253 StartNode2 = NDLST(NDXN)
254 GO TO 10
255 90 IDFLT = 1
256 if (MTW2<=MTW1) IDFLT = 2
257 RETURN
258 END
259 */
260 void Finley_Reduce_dropTree(index_t root, PPP pattern, NR, index_t *AssignedLevel,index_t *NodesInTree,
261 index_t *LastLevelWidth, index_t *BottomLevel,index_t *available_NodesInTree, index_t *max_LevelWidth, index_t max_LevelWidth_abort)
262
263 /* Finley_Reduce_dropTree drops a tree in pattern from root */
264
265 /* AssignedLevel- array of length length pattern->N indicating available nodes with zero entries. */
266 /* Finley_Reduce_dropTree enters level numbers assigned during execution of this procedure */
267
268 /* NodesInTree - on output contains node numbers used in tree (array of length pattern->N) */
269 /* arranged by levels (NodesInTree[available_NodesInTree] contains root and NodesInTree(BottomLevel+LastLevelWidth-1) */
270 /* contains last node entered) */
271
272 /* LastLevelWidth - on output contains width of last level */
273 /* BottomLevel - on output contains index into iwk of first node in last level
274 /* max_LevelWidth - on output contains the maximum level width
275 /* available_NodesInTree- on input the first available location in NodesInTree
276 /* usually one but if NodesInTree is used to store previous connected components, */
277 /* available_NodesInTree is next available location. on output the total number of levels + 1 */
278 /* max_LevelWidth_abort- input param which triggers early return if max_LevelWidth becomes >= max_LevelWidth_abort */
279
280 index_t ITOP = available_NodesInTree;
281 index_t INOW = available_NodesInTree;
282
283 *max_LevelWidth = 0;
284 *BottomLevel = available_NodesInTree;
285 *TopLevel = available_NodesInTree + 1;
286 *available_NodesInTree = 1
287 AssignedLevel(root) = 1
288 NodesInTree(ITOP) = root
289 while(max_LevelWidth<max_LevelWidth_abort && ITOP>=TopLevel) {
290 available_NodesInTree++;
291 while (INOW>=TopLevel) {
292 NodesInTreeNOW = NodesInTree(INOW)
293 for (j=pattern->iptr[NodesInTreeNOW],j<pattern->iptr[NodesInTreeNOW+1],++J) {
294 ITEST = pattern->index[J];
295 if (AssignedLevel(ITEST)==0) {
296 AssignedLevel(ITEST) = available_NodesInTree;
297 ITOP++;
298 NodesInTree(ITOP) = ITEST
299 }
300 }
301 INOW = INOW + 1
302 }
303 *LastLevelWidth = TopLevel - BottomLevel
304 *max_LevelWidth = MAX(max_LevelWidth,LastLevelWidth);
305 *BottomLevel = INOW
306 *TopLevel = ITOP + 1
307 }
308 }
309
310 SUBROUTINE SORTDG(STK1, STK2, X1, X2, Degree) SOR 10
311 /* SORTDG SORTS STK2 BY DEGREE OF THE NODE AND ADDS IT TO THE END
312 /* OF STK1 IN ORDER OF LOWEST TO HIGHEST DEGREE. X1 AND X2 ARE THE
313 /* NUMBER OF NODES IN STK1 AND STK2 RESPECTIVELY.
314 INTEGER X1, X2, STK1, STK2, TEMP
315 COMMON /GRA/ N, IDPTH, ndeg_max
316 DIMENSION Degree(1), STK1(1), STK2(1)
317 IND = X2
318 10 ITEST = 0
319 IND = IND - 1
320 if (IND<1) GO TO 30
321 for (20 I=1,IND
322 J = I + 1
323 ISTK2 = STK2[i]
324 JSTK2 = STK2(J)
325 if (Degree(ISTK2)<=Degree(JSTK2)) GO TO 20
326 ITEST = 1
327 TEMP = STK2[i]
328 STK2[i] = STK2(J)
329 STK2(J) = TEMP
330 20 CONTINUE
331 if (ITEST.EQ.1) GO TO 10
332 30 for (40 I=1,X2
333 X1 = X1 + 1
334 STK1(X1) = STK2[i]
335 40 CONTINUE
336 RETURN
337 END
338 SUBROUTINE Finley_Reduce_setup(AssignedLevel, LevelToNode, NodeToLevel) SET 10
339 /* Finley_Reduce_setup COMPUTES THE REVERSE LEVELING INFO FROM NodeToLevel AND STORES
340 /* IT INTO NodeToLevel. NACUM[i] IS INITIALIZED TO NODES/ITH LEVEL FOR NODES
341 /* ON THE PSEUDO-diameter OF THE GRAPH. AssignedLevel IS INITIALIZED TO NON-
342 /* ZERO FOR NODES ON THE PSEUDO-diameter AND NODES IN A DifFERENT
343 /* COMPONENT OF THE GRAPH.
344 COMMON /GRA/ N, IDPTH, ndeg_max
345 /* IT IS ASSUMED THAT THERE ARE AT MOST 100 LEVELS.
346 COMMON /AssignedLevelW/ NHIGH(100), NLOW(100), NACUM(100)
347 DIMENSION AssignedLevel(1), LevelToNode(1), NodeToLevel(1)
348 for (10 I=1,IDPTH
349 NACUM[i] = 0
350 10 CONTINUE
351 for (30 i=0,i<N,++i)
352 AssignedLevel[i] = 1
353 NodeToLevel[i] = IDPTH + 1 - NodeToLevel[i]
354 ITEMP = NodeToLevel[i]
355 if (ITEMP>IDPTH) GO TO 30
356 if (ITEMP!=LevelToNode[i]) GO TO 20
357 NACUM(ITEMP) = NACUM(ITEMP) + 1
358 GO TO 30
359 20 AssignedLevel[i] = 0
360 30 CONTINUE
361 RETURN
362 END
363 INTEGER FUNCTION SORT2(DMY) SOR 10
364 /* SORT2 SORTS SIZE AND STPT INTO DESCENDING ORDER ACCORDING TO
365 /* VALUES OF SIZE. ConnectedComponentCounter=NUMBER OF ENTRIES IN EACH ARRAY
366 INTEGER TEMP, ConnectedComponents, SIZE, STPT, ConnectedComponentCounter
367 /* IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
368 COMMON /CC/ ConnectedComponentCounter, SIZE(50), STPT(50)
369 SORT2 = 0
370 if (ConnectedComponentCounter.EQ.0) RETURN
371 SORT2 = 1
372 IND = ConnectedComponentCounter
373 10 ITEST = 0
374 IND = IND - 1
375 if (IND<1) RETURN
376 for (20 I=1,IND
377 J = I + 1
378 if (SIZE[i]>=SIZE(J)) GO TO 20
379 ITEST = 1
380 TEMP = SIZE[i]
381 SIZE[i] = SIZE(J)
382 SIZE(J) = TEMP
383 TEMP = STPT[i]
384 STPT[i] = STPT(J)
385 STPT(J) = TEMP
386 20 CONTINUE
387 if (ITEST.EQ.1) GO TO 10
388 RETURN
389 END
390 SUBROUTINE PIKAssignedLevel(LevelToNode, NodeToLevel, ConnectedComponents, IDFLT, DirectionLargestComponent) PIK 10
391 /* PIKAssignedLevel CHOOSES THE LEVEL STRUCTURE USED IN NUMBERING GRAPH
392 /* LevelToNode- ON INPUT CONTAINS FORWARD LEVELING INFO
393 /* NodeToLevel- ON INPUT CONTAINS REVERSE LEVELING INFO
394 /* ON OUTPUT THE FINAL LEVEL STRUCTURE CHOSEN
395 /* ConnectedComponents- ON INPUT CONTAINS CONNECTED COMPONENT INFO
396 /* IDFLT- ON INPUT =1 if WDTH LevelToNode<=WDTH NodeToLevel, =2 OTHERWISE
397 /* NHIGH KEEPS TRACK OF LEVEL WIDTHS FOR HIGH NUMBERING
398 /* NLOW- KEEPS TRACK OF LEVEL WIDTHS FOR LOW NUMBERING
399 /* NACUM- KEEPS TRACK OF LEVEL WIDTHS FOR CHOSEN LEVEL STRUCTURE
400 /* ConnectedComponentCounter- NUMBER OF CONNECTED COMPONENTS
401 /* SIZE[i]- SIZE OF ITH CONNECTED COMPONENT
402 /* STPT[i]- INDEX INTO ConnectedComponentsE OF 1ST NODE IN ITH CON COMPT
403 /* DirectionLargestComponent- FLAG WHICH INDICATES WHICH WAY THE LARGEST CONNECTED
404 /* COMPONENT FELL. =+1 if LOW AND -1 if HIGH
405 INTEGER ConnectedComponents, SIZE, STPT, ConnectedComponentCounter, END
406 COMMON /GRA/ N, IDPTH, ndeg_max
407 /* IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 COMPONENTS AND
408 /* THAT THERE ARE AT MOST 100 LEVELS.
409 COMMON /AssignedLevelW/ NHIGH(100), NLOW(100), NACUM(100)
410 COMMON /CC/ ConnectedComponentCounter, SIZE(50), STPT(50)
411 DIMENSION LevelToNode(1), NodeToLevel(1), ConnectedComponents(1)
412 /* FOR EACH CONNECTED COMPONENT DO
413 for (80 I=1,ConnectedComponentCounter
414 J = STPT[i]
415 END = SIZE[i] + J - 1
416 /* SET NHIGH AND NLOW EQUAL TO NACUM
417 for (10 K=1,IDPTH
418 NHIGH(K) = NACUM(K)
419 NLOW(K) = NACUM(K)
420 10 CONTINUE
421 /* UPDATE NHIGH AND NLOW FOR EACH NODE IN CONNECTED COMPONENT
422 for (20 K=J,END
423 INODE = ConnectedComponents(K)
424 available_NodesInTreeH = LevelToNode(INODE)
425 NHIGH(available_NodesInTreeH) = NHIGH(available_NodesInTreeH) + 1
426 available_NodesInTreeL = NodeToLevel(INODE)
427 NLOW(available_NodesInTreeL) = NLOW(available_NodesInTreeL) + 1
428 20 CONTINUE
429 MAX1 = 0
430 MAX2 = 0
431 /* SET MAX1=LARGEST NEW NUMBER IN NHIGH
432 /* SET MAX2=LARGEST NEW NUMBER IN NLOW
433 for (30 K=1,IDPTH
434 if (2*NACUM(K).EQ.NLOW(K)+NHIGH(K)) GO TO 30
435 if (NHIGH(K)>MAX1) MAX1 = NHIGH(K)
436 if (NLOW(K)>MAX2) MAX2 = NLOW(K)
437 30 CONTINUE
438 /* SET IT= NUMBER OF LEVEL STRUCTURE TO BE USED
439 IT = 1
440 if (MAX1>MAX2) IT = 2
441 if (MAX1.EQ.MAX2) IT = IDFLT
442 if (IT.EQ.2) GO TO 60
443 if (I.EQ.1) DirectionLargestComponent = -1
444 /* COPY LevelToNode INTO NodeToLevel FOR EACH NODE IN CONNECTED COMPONENT
445 for (40 K=J,END
446 INODE = ConnectedComponents(K)
447 NodeToLevel(INODE) = LevelToNode(INODE)
448 40 CONTINUE
449 /* UPDATE NACUM TO BE THE SAME AS NHIGH
450 for (50 K=1,IDPTH
451 NACUM(K) = NHIGH(K)
452 50 CONTINUE
453 GO TO 80
454 /* UPDATE NACUM TO BE THE SAME AS NLOW
455 60 for (70 K=1,IDPTH
456 NACUM(K) = NLOW(K)
457 70 CONTINUE
458 80 CONTINUE
459 RETURN
460 END
461 SUBROUTINE NUMBER(StartNode2, NUM, NDSTK, NodeToLevel, Degree, NewLabel, AssignedLevelST, NUM 10
462 * LSTPT, NR, Flag, newBandwidth, newProfile, IPFA, DirectionLargestComponent)
463 /* NUMBER PRODUCES THE NUMBERING OF THE GRAPH FOR MIN BANDWIDTH
464 /* StartNode2- ON INPUT THE NODE TO BEGIN NUMBERING ON
465 /* NUM- ON INPUT AND OUTPUT, THE NEXT AVAILABLE NUMBER
466 /* NodeToLevel- THE LEVEL STRUCTURE TO BE USED IN NUMBERING
467 /* NewLabel- THE ARRAY USED TO STORE THE NEW NUMBERING
468 /* AssignedLevelST- ON OUTPUT CONTAINS LEVEL STRUCTURE
469 /* LSTPT[i]- ON OUTPUT, INDEX INTO AssignedLevelST TO FIRST NODE IN ITH AssignedLevel
470 /* LSTPT(I+1) - LSTPT[i] = NUMBER OF NODES IN ITH AssignedLevel
471 /* Flag- =+1 if StartNode2 IS FORWARD END OF PSEUDO-diameter
472 /* =-1 if StartNode2 IS REVERSE END OF PSEUDO-diameter
473 /* newBandwidth- BANDWIDTH OF NEW NUMBERING COMPUTED BY NUMBER
474 /* newProfile- PROFILE OF NEW NUMBERING COMPUTED BY NUMBER
475 /* IPFA- WORKING STORAGE USED TO COMPUTE PROFILE AND BANDWIDTH
476 /* DirectionLargestComponent- INDICATES STEP DIRECTION USED IN NUMBERING(+1 OR -1)
477 /* USE INTEGER*2 NDSTK WITH AN IBM 360 OR 370.
478 INTEGER NDSTK
479 INTEGER StartNode2, STKA, STKB, STKC, STKD, XA, XB, ConnectedComponentCounter, XD, CX, END,
480 * NewLabel, TEST
481 COMMON /GRA/ N, IDPTH, ndeg_max
482 /* THE STORAGE IN COMMON BLOCKS CC AND AssignedLevelW IS NOW FREE AND CAN
483 /* BE USED FOR STACKS.
484 COMMON /AssignedLevelW/ STKA(100), STKB(100), STKC(100)
485 COMMON /CC/ STKD(100)
486 DIMENSION IPFA(1)
487 DIMENSION NDSTK(NR,1), NodeToLevel(1), Degree(1), NewLabel(1), AssignedLevelST(1),
488 * LSTPT(1)
489 /* SET UP AssignedLevelST AND LSTPT FROM NodeToLevel
490 for (10 i=0,i<N,++i)
491 IPFA[i] = 0
492 10 CONTINUE
493 NSTPT = 1
494 for (30 I=1,IDPTH
495 LSTPT[i] = NSTPT
496 for (20 J=1,N
497 if (NodeToLevel(J)!=I) GO TO 20
498 AssignedLevelST(NSTPT) = J
499 NSTPT = NSTPT + 1
500 20 CONTINUE
501 30 CONTINUE
502 LSTPT(IDPTH+1) = NSTPT
503 /* STKA, STKB, STKC AND STKD ARE STACKS WITH POINTERS
504 /* XA,XB,ConnectedComponentCounter, AND XD. CX IS A SPECIAL POINTER INTO STKC WHICH
505 /* INDICATES THE PARTICULAR NODE BEING PROCESSED.
506 /* available_NodesInTree KEEPS TRACK OF THE LEVEL WE ARE WORKING AT.
507 /* INITIALLY STKC CONTAINS ONLY THE INITIAL NODE, StartNode2.
508 available_NodesInTree = 0
509 if (Flag<0) available_NodesInTree = IDPTH + 1
510 ConnectedComponentCounter = 1
511 STKC(ConnectedComponentCounter) = StartNode2
512 40 CX = 1
513 XD = 0
514 available_NodesInTree = available_NodesInTree + Flag
515 LST = LSTPT(available_NodesInTree)
516 LND = LSTPT(available_NodesInTree+1) - 1
517 /* BEGIN PROCESSING NODE STKC(CX)
518 50 IPRO = STKC(CX)
519 NewLabel(IPRO) = NUM
520 NUM = NUM + DirectionLargestComponent
521 END = Degree(IPRO)
522 XA = 0
523 XB = 0
524 /* CHECK ALL ADJACENT NODES
525 for (80 I=1,END
526 TEST = NDSTK(IPRO,I)
527 INX = NewLabel(TEST)
528 /* ONLY NODES NOT NUMBERED OR ALREADY ON A STACK ARE ADDED
529 if (INX.EQ.0) GO TO 60
530 if (INX<0) GO TO 80
531 /* for (PRELIMINARY BANDWIDTH AND PROFILE CALCULATIONS
532 NBW = (NewLabel(IPRO)-INX)*DirectionLargestComponent
533 if (DirectionLargestComponent>0) INX = NewLabel(IPRO)
534 if (IPFA(INX)<NBW) IPFA(INX) = NBW
535 GO TO 80
536 60 NewLabel(TEST) = -1
537 /* PUT NODES ON SAME LEVEL ON STKA, ALL OTHERS ON STKB
538 if (NodeToLevel(TEST).EQ.NodeToLevel(IPRO)) GO TO 70
539 XB = XB + 1
540 STKB(XB) = TEST
541 GO TO 80
542 70 XA = XA + 1
543 STKA(XA) = TEST
544 80 CONTINUE
545 /* SORT STKA AND STKB INTO INCREASING DEGREE AND ADD STKA TO STKC
546 /* AND STKB TO STKD
547 if (XA.EQ.0) GO TO 100
548 if (XA.EQ.1) GO TO 90
549 CALL SORTDG(STKC, STKA, ConnectedComponentCounter, XA, Degree)
550 GO TO 100
551 90 ConnectedComponentCounter = ConnectedComponentCounter + 1
552 STKC(ConnectedComponentCounter) = STKA(XA)
553 100 if (XB.EQ.0) GO TO 120
554 if (XB.EQ.1) GO TO 110
555 CALL SORTDG(STKD, STKB, XD, XB, Degree)
556 GO TO 120
557 110 XD = XD + 1
558 STKD(XD) = STKB(XB)
559 /* BE SURE TO PROCESS ALL NODES IN STKC
560 120 CX = CX + 1
561 if (ConnectedComponentCounter>=CX) GO TO 50
562 /* WHEN STKC IS EXHAUSTED LOOK FOR MIN DEGREE NODE IN SAME LEVEL
563 /* WHICH HAS NOT BEEN PROCESSED
564 MAX = ndeg_max + 1
565 StartNode2 = N + 1
566 for (130 I=LST,LND
567 TEST = AssignedLevelST[i]
568 if (NewLabel(TEST)!=0) GO TO 130
569 if (Degree(TEST)>=MAX) GO TO 130
570 NewLabel(StartNode2) = 0
571 NewLabel(TEST) = -1
572 MAX = Degree(TEST)
573 StartNode2 = TEST
574 130 CONTINUE
575 if (StartNode2.EQ.N+1) GO TO 140
576 ConnectedComponentCounter = ConnectedComponentCounter + 1
577 STKC(ConnectedComponentCounter) = StartNode2
578 GO TO 50
579 /* if STKD IS EMPTY WE ARE DONE, OTHERWISE COPY STKD ONTO STKC
580 /* AND BEGIN PROCESSING NEW STKC
581 140 if (XD.EQ.0) GO TO 160
582 for (150 I=1,XD
583 STKC[i] = STKD[i]
584 150 CONTINUE
585 ConnectedComponentCounter = XD
586 GO TO 40
587 /* for (FINAL BANDWIDTH AND PROFILE CALCULATIONS
588 160 for (170 i=0,i<N,++i)
589 if (IPFA[i]>newBandwidth) newBandwidth = IPFA[i]
590 newProfile = newProfile + IPFA[i]
591 170 CONTINUE
592 RETURN
593 END

  ViewVC Help
Powered by ViewVC 1.1.26