/[escript]/trunk/finley/src/Mesh_reduceBandwidth.c.later
ViewVC logotype

Annotation of /trunk/finley/src/Mesh_reduceBandwidth.c.later

Parent Directory Parent Directory | Revision Log Revision Log


Revision 633 - (hide annotations)
Thu Mar 23 05:37:00 2006 UTC (16 years, 10 months ago) by dhawcroft
Original Path: trunk/paso/src/SystemMatrixPattern_reduceBandwidth.c
File MIME type: text/plain
File size: 25598 byte(s)


1 dhawcroft 631
2     /*
3     ********************************************************************************
4 dhawcroft 633 * Copyright 2006 by ACcESS MNRF *
5 dhawcroft 631 * *
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 gross 505 /* 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