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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 505 - (hide annotations)
Wed Feb 8 23:27:16 2006 UTC (16 years, 6 months ago) by gross
File MIME type: text/plain
File size: 24952 byte(s)
bandwidth optimizer but it does not really work.
1 gross 505 /* 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