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

  ViewVC Help
Powered by ViewVC 1.1.26