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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1050 - (hide annotations)
Tue Mar 20 09:39:11 2007 UTC (15 years, 4 months ago) by gross
File size: 31446 byte(s)
rename so compilation does not fail
1 gross 1050
2     /*
3     ********************************************************************************
4     * Copyright 2006 by ACcESS MNF *
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     /* pattern_p(N,D1) D1 IS >= MAXIMUM degree_p OF ALL NODES.
20     /* label_p(D2) D2 AND N ARE >= THE TOTAL NUMBER OF
21     /* new_label_p(D2+1) NODES IN THE GRAPH.
22     /* degree_p(D2) STORAGE REQUIREMENTS CAN BE SIGNifICANTLY
23    
24     /* assigned_level_p(D2) DECREASED FOR IBM 360 AND 370 COMPUTERS
25     /* forward_levels_p(D2) BY REPLACING INTEGER pattern_p BY
26     /* backward_levels_p(D2) INTEGER*2 pattern_p IN SUBROUTINES Finley_Reduce,
27     /* ConnectedComponents(D2) Finley_Reduce_setCharacteristics, Finley_Reduce_findDiameter, Paso_SystemMatrixPattern_dropTree AND NUMBER.
28     /* COMMON INFORMATION--THE FOLLOWING COMMON BLOCK MUST BE IN THE
29     /* CALLING ROUTINE.
30     /* COMMON/GRA/N,num_levels,ndeg_max
31     /* EXPLANATION OF INPUT VARIABLES--
32     /* pattern_p- CONNECTION TABLE REPRESENTING GRAPH.
33     /* pattern_p->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     /* N- ROW DIMENSION ASSIGNED pattern_p IN CALLING PROGRAM.
37     /* label_p[i]- NUMBERING OF ITH NODE UPON INPUT. if NO NUMBERING EXISTS THEN label_p[i]=I.
38     /* N- NUMBER OF NODES IN GRAPH (EQUAL TO ORDER OF MATRIX).
39     /* ndeg_max- MAXIMUM degree_p OF ANY NODE IN THE GRAPH.
40     /* degree_p[i]- THE degree_p OF THE ITH NODE.
41     /* EXPLANATION OF OUTPUT VARIABLES--
42     /* new_label_p[i]- THE NEW NUMBER FOR THE ITH NODE.
43     /* newBandwidth- THE BANDWIDTH AFTER numbering .
44     /* newProfile- THE PROFILE AFTER numbering .
45     /* num_levels - NUMBER OF LEVELS IN Finley_Reduce LEVEL STRUCTURE.
46     /* */
47     /* The following only have meaning if the graph was connected:
48    
49     /* assigned_level_p[i]- INDEX INTO forward_levels_p TO THE FIRST NODE IN LEVEL I. assigned_level_p(I+1)-assigned_level_p[i]= number of nodes in ith leveL
50     /* forward_levels_p- node numbers listed by level
51     /* backward_levels_p[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 PIKassigned_level_p 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/assigned_level_pW/-SUBROUTINES Finley_Reduce_setup AND PIKassigned_level_p ASSUME THAT THERE
61     /* ARE AT MOST 100 LEVELS.
62     SUBROUTINE Finley_Reduce(pattern_p, N, label_p, new_label_p, degree_p, assigned_level_p, forward_levels_p,backward_levels_p, ConnectedComponents, newBandwidth, newProfile, NIN, ndeg_maxIN)
63     /* USE INTEGER*2 pattern_p WITH AN IBM 360 OR 370.
64     integer NIN, ndeg_maxIN
65     INTEGER pattern_p
66     INTEGER start_node, end_node, new_label_p, ConnectedComponentCounter, SORT2, last_available_node_number, ConnectedComponents,
67     * SIZE, STPT, first_available_node_number
68     COMMON /GRA/ N, num_levels, 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 /assigned_level_pW/ NHIGH(100), NLOW(100), NACUM(100)
72     DIMENSION ConnectedComponents(1), label_p(1)
73     DIMENSION pattern_p(N,1), assigned_level_p(1), forward_levels_p(1), backward_levels_p(1), new_label_p(1),
74     * degree_p(1)
75     newBandwidth = 0
76     newProfile = 0
77     /* SET new_label_p[i]=0 FOR ALL I TO INDICATE NODE I IS UNNUMBERED
78     c
79     c N = N
80     c do i=0,i<N,++i)
81     c if(ndeg_max<degree_p[i]) then
82     c ndeg_max = degree_p[i]
83     c end if
84     c end do
85     c
86    
87     set degree_p
88     N=NIN
89     ndeg_max = ndeg_maxIN
90     for (i=0,i<N,++i) {
91     degree_p[i]=ptr[i+1]-ptr[i];
92     new_label_p[i] = 0;
93     }
94    
95     /* COMPUTE degree_p OF EACH NODE AND ORIGINAL BANDWIDTH AND PROFILE*/
96    
97     ===============================
98     Paso_SystemMatrixpattern_p* pattern_p,
99    
100    
101     long initial_bandwidth, initial_profile
102     dim_t *degree_p=NULL;
103     dim_t N = pattern_p->n_ptr;
104     index_t *label_p_p=NULL;
105    
106     degree_p=MEMALLOC(N,dim_t);
107     label_p_p=MEMALLOC(N,index_t);
108     new_label_p=MEMALLOC(N,index_t);
109    
110     if (sdsadsad) {
111     /* get the initial bandwidth and profile */
112     for (i=0,i<N,++i) {
113     degree_p[i]=pattern_p->ptr[i+1]-pattern_p->ptr[i]-1;
114     label_p[i]=i;
115     new_label_p[i]=0;
116     }
117     Finley_Reduce_setCharacteristics(pattern_p, degree_p, label_p, *initial_bandwidth, *initial_profile)
118     printf("initial bandwidth and profile: %dl %dl\n",initial_bandwidth, initial_profile);
119    
120     /* first_available_node_number = low end of available numbers for numbering */
121     /* last_available_node_number = high end of available numbers for numbering */
122     first_available_node_number = 0;
123     last_available_node_number = N;
124     /* number the nodes of degree_p zero are last: */
125     for (i=0,i<N,++i) {
126     if (degree_p[i]==0) {
127     new_label_p[i] = last_available_node_number;
128     last_available_node_number--;
129     }
130     }
131    
132     }
133     }
134     /* find an unnumbered node of min degree to start on */
135     while (first_available_node_number<=last_available_node_number) {
136    
137     reverse_diameter_tree = FALSE;
138     SDIR = 1;
139    
140     /* find the node with smallest degree and use this one as start node */
141     smallest_degree = N + 1;
142     for (i=0,i<N,++i) {
143     if (degree_p[i]<smallest_degree && new_label_p[i]<=0) {
144     smallest_degree = degree_p[i];
145     start_node = i;
146     }
147     }
148     /* find pseudo-diameter and associated level structures marked assigned_level_p: */
149    
150     /* start_node and end_node are the ends of the diameter and
151     forward_levels_p and backward_levels_p are the respective level structures. */
152    
153     Finley_Reduce_findDiameter(*start_node, end_node, pattern_p, degree_p,
154     assigned_level_p, forward_levels_p,backward_levels_p, ConnectedComponents, IDFLT)
155     /* reverse_diameter_tree INDICATES THE END TO BEGIN NUMBERING ON */
156     if (degree_p(start_node)>degree_p(end_node)) {
157     reverse_diameter_tree = TRUE;
158     start_node = end_node;
159     } else {
160     reverse_diameter_tree = FALSE;
161     }
162     #########
163     CALL Finley_Reduce_setup(assigned_level_p, forward_levels_p, backward_levels_p)
164     /* find all the connected components (ConnectedComponentCounter counts them) */
165     ConnectedComponentCounter = 0;
166     LROOT = 1
167     first_available_in_list_of_tree_nodes = 1
168     for (i=0,i<N,++i) {
169     if (assigned_level_p[i]==0) {
170     ConnectedComponentCounter++;
171     STPT(ConnectedComponentCounter) = LROOT
172     CALL Paso_SystemMatrixPattern_dropTree(I, pattern_p, N, assigned_level_p, ConnectedComponents, degree_p, last_level_width, first_node_in_bottom_level,first_available_in_list_of_tree_nodes, max_level_width, N)
173     SIZE(ConnectedComponentCounter) = first_node_in_bottom_level + last_level_width - LROOT
174     LROOT = first_node_in_bottom_level + last_level_width
175     first_available_in_list_of_tree_nodes = LROOT
176     }
177     }
178     /* on return from PIKassigned_level_p, DirectionLargestComponent indicates the direction the largest component fell. */
179     /* DirectionLargestComponent is modIFied now to indicate the numbering direction. num is set to the proper value for this direction. */
180     if (SORT2(DMY)!=0) PIKassigned_level_p(forward_levels_p, backward_levels_p, ConnectedComponents, IDFLT, DirectionLargestComponent)
181     DirectionLargestComponent = DirectionLargestComponent*reverse_diameter_tree;
182     NUM= (DirectionLargestComponent<0) ? last_available_node_number :first_available_node_number;
183    
184     CALL NUMBER(start_node, NUM, pattern_p, backward_levels_p, degree_p, new_label_p, forward_levels_p,
185     * assigned_level_p, N, reverse_diameter_tree, newBandwidth, newProfile, ConnectedComponents, DirectionLargestComponent)
186    
187     /* update last_available_node_number or first_available_node_number after numbering */
188    
189     if (DirectionLargestComponent<0) last_available_node_number = NUM;
190     if (DirectionLargestComponent>0) first_available_node_number = NUM;
191    
192     }
193    
194     /* if original numbering is better than new one, set up to return it */
195    
196     if (newBandwidth > initial_bandwidth) {
197     for (i=0,i<N,++i)
198     new_label_p[i] = label_p[i];
199     *newBandwidth = initial_bandwidth;
200     *newProfile = initial_profile;
201     }
202     }
203     ===============================================
204     /* Finley_Reduce_setCharacteristics computes the degree_p of each node and stores it in the array degree_p. */
205     /* the bandwidth and profile for the original or input numbering of the graph is computed also. */
206    
207     void Finley_Reduce_setCharacteristics(Paso_SystemMatrixpattern_p *pattern_p,
208     dim_t *degree_p,
209     dim_t* label_p,
210     long *bandwidth,long *initial_profile) {
211    
212     long max_diff;
213     dim_t i;
214     *bandwidth = 0;
215     *profile = 0;
216     for (i=0,i<pattern_p->n_ptr,++i) {
217     max_diff = 0;
218     for (iptr=pattern_p->ptr[i],iptr<pattern_p->ptr[i+1],++i) {
219     diff = label_p[i] - label_p(pattern_p->index[iptr]);
220     max_diff = MAX(max_diff,diff);
221     }
222     *profile + = max_diff;
223     *bandwidth=MAX(*bandwidth,max_diff);
224     }
225     }
226     void Paso_SystemMatrixPattern_sortByDegree(index_t* node_index1, index_t* node_index2, dim_t* num_nodes1, dim_t num_nodes2, dim_t* degree_p)
227     {
228     /* Paso_SystemMatrixPattern_sortByDegree sorts node_index2 by degree_p of the NODE AND ADDS IT TO THE END
229     OF node_index1 IN ORDER OF LOWEST TO HIGHEST degree_p. num_nodes1 AND num_nodes2 ARE THE
230     NUMBER OF NODES IN node_index1 AND node_index2 RESPECTIVELY.
231     */
232     register bool_t swapped=TRUE;
233     register dim_t i, ipp;
234     register index_t node_index2_i, node_index2_ipp, temp;
235     register dim_t j=num_nodes2;
236     while (swapped && j>1) {
237     j--;
238     swapped = FALSE;
239     for (i=0; i<j; ++i) {
240     ipp=i+1
241     node_index2_i = node_index2[i]
242     node_index2_ipp = node_index2[ipp]
243     if (degree_p[node_index2_i]>degree_p[node_index2_ipp]) {
244     swapped= TRUE;
245     temp = node_index2[i];
246     node_index2[i] = node_index2[ipp];
247     node_index2[ipp] = temp;
248     }
249     }
250     }
251     for (i=0; i< num_nodes2; ++i) {
252     (*num_nodes1)++;
253     node_index1[num_nodes1] = node_index2[i]
254     }
255     return;
256     }
257    
258    
259     void Finley_Reduce_findDiameter(index_t *start_node,
260     index_t *end_node,
261     Paso_SystemMatrixPattern *pattern_p,
262     dim_t* degree_p,
263     index_t* forward_levels_p,
264     index_t* backward_levels_p,
265     *IDFLT,
266     index_t* work1_p,
267     index_t* work2_p,
268     index_t* node_list_p,
269     )
270     /*
271     Finley_Reduce_findDiameter is the control procedure for finding the pseudo-diameter of pattern
272     as well as the level structure from each end
273    
274     start_node- on input this is the node number of the first attempt at finding a diameter.
275     on output it contains the actual number used.
276     end_node - on output contains other end of diameter
277     forward_levels_p- ARRAY CONTAINING LEVEL STRUCTURE WITH start_node AS ROOT
278     backward_levels_p- ARRAY CONTAINING LEVEL STRUCTURE WITH end_node AS ROOT
279     IDFLT- reverse_diameter_tree USED IN PICKING FINAL LEVEL STRUCTURE, SET
280     =1 if WIDTH OF forward_levels_p <= WIDTH OF backward_levels_p, OTHERWISE =2
281     assigned_level_p, list_of_tree_nodes_p- WORKING STORAGE
282    
283     */
284    
285    
286     /* COMMON /GRA/ N, num_levels, ndeg_max
287     IT IS ASSUMED THAT THE LAST LEVEL HAS AT MOST 100 NODES.
288     COMMON /CC/ node_list(100)
289     DIMENSION pattern_p(N,1), degree_p(1), assigned_level_p(1), forward_levels_p(1), backward_levels_p(1),list_of_tree_nodes_p(1)
290     */
291     dim_t num_tree_nodes;
292     dim_t N= pattern->n_ptr;
293     bool_t find_new_starting_nodes=TRUE;
294    
295     /* find initial set of nodes as the end points of the tree created by root */
296     while (find_new_starting_nodes) {
297     num_tree_nodes = 0;
298     /* zero assigned_level_p to indicate all nodes are available to Paso_SystemMatrixPattern_dropTree */
299     for (i=0,i<N,++i) forward_levels_p[i] = -1;
300    
301     Paso_SystemMatrixPattern_dropTree(*(start_node),
302     pattern_p,
303     forward_levels_p,
304     work2_p,
305     degree_p,
306     num_tree_nodes, first_node_in_bottom_level,
307     first_available_in_list_of_tree_nodes,
308     num_levels, max_level_width_abort1, N)
309    
310     node_list_len = 0;
311     /* sort last level by degree_p and store in node_list_p */
312     Paso_SystemMatrixPattern_sortByDegree(node_list_p, &(work2_p[first_node_in_bottom_level]),
313     *node_list_len, last_level_width, degree_p)
314    
315     find_new_starting_nodes=FALSE;
316     /* now start searching from the ends points of the initial search */
317     NDXN=0;
318     while (NDXN < node_list_len) {
319     start_node2 = node_list[NDXN];
320    
321     /* drop a tree from start_node2 */
322     for (i=0;i<N;++i) assigned_level_p[i] = -1;
323     num_tree_nodes = 0;
324     Paso_SystemMatrixPattern_dropTree(start_node2,
325     pattern_p,
326     work1_p,
327     work2_p,
328     degree_p, last_level_width, first_node_in_bottom_level,
329     num_tree_nodes,
330     num_levels2,
331     max_level_width, max_level_width_abort);
332     if (num_levels2<num_levels) {
333     start_node = start_node2
334     find_new_starting_nodes=TRUE;
335     break;
336     }
337     /* STORE NARROWEST REVERSE LEVEL STRUCTURE IN backward_levels_p */
338     if (max_level_width<max_level_width_abort) {
339     max_level_width_abort = max_level_width;
340     end_node = start_node2;
341     for (i=0;i<N;++i) backward_levels_p[i] = work1_p[i];
342     }
343     NDXN++;
344     }
345     if (max_level_width_abort2<=max_level_width_abort1)
346     *IDFLT = 2
347     } else {
348     *IDFLT=1
349     }
350     return
351     }
352    
353     void Paso_SystemMatrixPattern_dropTree(index_t root,
354     Paso_SystemMatrixPattern *pattern_p,
355     index_t *assigned_level_p,
356     index_t *list_of_tree_nodes_p,
357     index_t *last_level_width,
358     index_t *first_node_in_bottom_level,
359     index_t *first_available_in_list_of_tree_nodes,
360     dim_t *num_levels,
361     dim_t *max_level_width, dim_t max_level_width_abort)
362    
363     /*
364     Paso_SystemMatrixPattern_dropTree drops a tree in pattern_p from root
365    
366     assigned_level_p- array of length length pattern_p->N indicating available nodes with -1 entries.
367     Paso_SystemMatrixPattern_dropTree enters level numbers .
368    
369     list_of_tree_nodes_p - on output contains node numbers used in tree (array of length pattern_p->N)
370     sorted by levels where list_of_tree_nodes_p[first_available_in_list_of_tree_nodes]
371     contains root and list_of_tree_nodes_p[first_node_in_bottom_level+last_level_width-1]
372     contains last node entered)
373    
374     last_level_width - on output contains width of last level
375     first_node_in_bottom_level - on output contains index into list_of_tree_nodes_p of first node in last level
376    
377     first_available_in_list_of_tree_nodes-
378     on input the first available location in list_of_tree_nodes_p
379     usually zero but if list_of_tree_nodes_p is used to store previous
380     connected components, first_available_in_list_of_tree_nodes is
381     next available location. on output the
382    
383     num_levels - number of levels
384    
385     max_level_width - on output contains the maximum level width
386     max_level_width_abort- input param which triggers early return if max_level_width becomes >= max_level_width_abort
387    
388     */
389    
390     dim_t j;
391     index_t node_now;
392     index_t i_top = first_available_in_list_of_tree_nodes;
393     index_t i_now = first_available_in_list_of_tree_nodes;
394     *max_level_width = 0;
395     *first_node_in_bottom_level = first_available_in_list_of_tree_nodes;
396     *top_level = first_available_in_list_of_tree_nodes + 1;
397     *num_levels = 0
398    
399     assigned_level_p[root] = *num_levels;
400     list_of_tree_nodes_p[i_top] = root;
401    
402     while ( ( max_level_width<max_level_width_abort ) && ( i_top >=top_level ) ) {
403    
404     num_levels++;
405    
406     while (i_now>=top_level) {
407     node_now = list_of_tree_nodes_p[i_now];
408     for (j=pattern_p->iptr[node_now],j<pattern_p->iptr[node_now+1],++j) {
409     index = pattern_p->index[j];
410     if (assigned_level_p[index]<0) {
411     assigned_level_p[index] = (*num_levels);
412     i_top++;
413     list_of_tree_nodes_p[i_top] = index
414     }
415     }
416     i_now++;
417     }
418     *last_level_width = top_level - first_node_in_bottom_level;
419     *max_level_width = MAX(*max_level_width, last_level_width);
420     *first_node_in_bottom_level = i_now;
421     *top_level = i_top + 1;
422     }
423     }
424    
425     SUBROUTINE Finley_Reduce_setup(assigned_level_p, forward_levels_p, backward_levels_p) SET 10
426     /* Finley_Reduce_setup COMPUTES THE REVERSE LEVELING INFO FROM backward_levels_p AND STORES
427     /* IT INTO backward_levels_p. NACUM[i] IS INITIALIZED TO NODES/ITH LEVEL FOR NODES
428     /* ON THE PSEUDO-diameter OF THE GRAPH. assigned_level_p IS INITIALIZED TO NON-
429     /* ZERO FOR NODES ON THE PSEUDO-diameter AND NODES IN A DifFERENT
430     /* COMPONENT OF THE GRAPH.
431     COMMON /GRA/ N, num_levels, ndeg_max
432     /* IT IS ASSUMED THAT THERE ARE AT MOST 100 LEVELS.
433     COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), NACUM(100)
434     DIMENSION assigned_level_p(1), forward_levels_p(1), backward_levels_p(1)
435     for (10 I=1,num_levels
436     NACUM[i] = 0
437     10 CONTINUE
438     for (30 i=0,i<N,++i)
439     assigned_level_p[i] = 1
440     backward_levels_p[i] = num_levels + 1 - backward_levels_p[i]
441     Itemp = backward_levels_p[i]
442     if (Itemp>num_levels) GO TO 30
443     if (Itemp!=forward_levels_p[i]) GO TO 20
444     NACUM(Itemp) = NACUM(Itemp) + 1
445     GO TO 30
446     20 assigned_level_p[i] = 0
447     30 CONTINUE
448     RETURN
449     END
450     INTEGER FUNCTION SORT2(DMY) SOR 10
451     /* SORT2 SORTS SIZE AND STPT INTO DESCENDING ORDER ACCORDING TO
452     /* VALUES OF SIZE. ConnectedComponentCounter=NUMBER OF ENTRIES IN EACH ARRAY
453     INTEGER temp, ConnectedComponents, SIZE, STPT, ConnectedComponentCounter
454     /* IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
455     COMMON /CC/ ConnectedComponentCounter, SIZE(50), STPT(50)
456     SORT2 = 0
457     if (ConnectedComponentCounter.EQ.0) RETURN
458     SORT2 = 1
459     IND = ConnectedComponentCounter
460     10 ITEST = 0
461     IND = IND - 1
462     if (IND<1) RETURN
463     for (20 I=1,IND
464     J = I + 1
465     if (SIZE[i]>=SIZE(J)) GO TO 20
466     ITEST = 1
467     temp = SIZE[i]
468     SIZE[i] = SIZE(J)
469     SIZE(J) = temp
470     temp = STPT[i]
471     STPT[i] = STPT(J)
472     STPT(J) = temp
473     20 CONTINUE
474     if (ITEST.EQ.1) GO TO 10
475     RETURN
476     END
477     SUBROUTINE PIKassigned_level_p(forward_levels_p, backward_levels_p, ConnectedComponents, IDFLT, DirectionLargestComponent) PIK 10
478     /* PIKassigned_level_p CHOOSES THE LEVEL STRUCTURE USED IN NUMBERING GRAPH
479     /* forward_levels_p- ON INPUT CONTAINS FORWARD LEVELING INFO
480     /* backward_levels_p- ON INPUT CONTAINS REVERSE LEVELING INFO
481     /* ON OUTPUT THE FINAL LEVEL STRUCTURE CHOSEN
482     /* ConnectedComponents- ON INPUT CONTAINS CONNECTED COMPONENT INFO
483     /* IDFLT- ON INPUT =1 if WDTH forward_levels_p<=WDTH backward_levels_p, =2 OTHERWISE
484     /* NHIGH KEEPS TRACK OF LEVEL WIDTHS FOR HIGH NUMBERING
485     /* NLOW- KEEPS TRACK OF LEVEL WIDTHS FOR LOW NUMBERING
486     /* NACUM- KEEPS TRACK OF LEVEL WIDTHS FOR CHOSEN LEVEL STRUCTURE
487     /* ConnectedComponentCounter- NUMBER OF CONNECTED COMPONENTS
488     /* SIZE[i]- SIZE OF ITH CONNECTED COMPONENT
489     /* STPT[i]- INDEX INTO ConnectedComponentsE OF 1ST NODE IN ITH CON COMPT
490     /* DirectionLargestComponent- reverse_diameter_tree WHICH INDICATES WHICH WAY THE LARGEST CONNECTED
491     /* COMPONENT FELL. =+1 if LOW AND -1 if HIGH
492     INTEGER ConnectedComponents, SIZE, STPT, ConnectedComponentCounter, END
493     COMMON /GRA/ N, num_levels, ndeg_max
494     /* IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 COMPONENTS AND
495     /* THAT THERE ARE AT MOST 100 LEVELS.
496     COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), NACUM(100)
497     COMMON /CC/ ConnectedComponentCounter, SIZE(50), STPT(50)
498     DIMENSION forward_levels_p(1), backward_levels_p(1), ConnectedComponents(1)
499     /* FOR EACH CONNECTED COMPONENT DO
500     for (80 I=1,ConnectedComponentCounter
501     J = STPT[i]
502     END = SIZE[i] + J - 1
503     /* SET NHIGH AND NLOW EQUAL TO NACUM
504     for (10 K=1,num_levels
505     NHIGH(K) = NACUM(K)
506     NLOW(K) = NACUM(K)
507     10 CONTINUE
508     /* UPDATE NHIGH AND NLOW FOR EACH NODE IN CONNECTED COMPONENT
509     for (20 K=J,END
510     INODE = ConnectedComponents(K)
511     first_available_in_list_of_tree_nodesH = forward_levels_p(INODE)
512     NHIGH(first_available_in_list_of_tree_nodesH) = NHIGH(first_available_in_list_of_tree_nodesH) + 1
513     first_available_in_list_of_tree_nodesL = backward_levels_p(INODE)
514     NLOW(first_available_in_list_of_tree_nodesL) = NLOW(first_available_in_list_of_tree_nodesL) + 1
515     20 CONTINUE
516     MAnum_nodes1 = 0
517     MAnum_nodes2 = 0
518     /* SET MAnum_nodes1=LARGEST NEW NUMBER IN NHIGH
519     /* SET MAnum_nodes2=LARGEST NEW NUMBER IN NLOW
520     for (30 K=1,num_levels
521     if (2*NACUM(K).EQ.NLOW(K)+NHIGH(K)) GO TO 30
522     if (NHIGH(K)>MAnum_nodes1) MAnum_nodes1 = NHIGH(K)
523     if (NLOW(K)>MAnum_nodes2) MAnum_nodes2 = NLOW(K)
524     30 CONTINUE
525     /* SET IT= NUMBER OF LEVEL STRUCTURE TO BE USED
526     IT = 1
527     if (MAnum_nodes1>MAnum_nodes2) IT = 2
528     if (MAnum_nodes1.EQ.MAnum_nodes2) IT = IDFLT
529     if (IT.EQ.2) GO TO 60
530     if (I.EQ.1) DirectionLargestComponent = -1
531     /* COPY forward_levels_p INTO backward_levels_p FOR EACH NODE IN CONNECTED COMPONENT
532     for (40 K=J,END
533     INODE = ConnectedComponents(K)
534     backward_levels_p(INODE) = forward_levels_p(INODE)
535     40 CONTINUE
536     /* UPDATE NACUM TO BE THE SAME AS NHIGH
537     for (50 K=1,num_levels
538     NACUM(K) = NHIGH(K)
539     50 CONTINUE
540     GO TO 80
541     /* UPDATE NACUM TO BE THE SAME AS NLOW
542     60 for (70 K=1,num_levels
543     NACUM(K) = NLOW(K)
544     70 CONTINUE
545     80 CONTINUE
546     RETURN
547     END
548     SUBROUTINE NUMBER(start_node2, NUM, pattern_p, backward_levels_p, degree_p, new_label_p, assigned_level_pST, NUM 10
549     * LSTPT, N, reverse_diameter_tree, newBandwidth, newProfile, IPFA, DirectionLargestComponent)
550     /* NUMBER PRODUCES THE NUMBERING OF THE GRAPH FOR MIN BANDWIDTH
551     /* start_node2- ON INPUT THE NODE TO BEGIN NUMBERING ON
552     /* NUM- ON INPUT AND OUTPUT, THE NEXT AVAILABLE NUMBER
553     /* backward_levels_p- THE LEVEL STRUCTURE TO BE USED IN NUMBERING
554     /* new_label_p- THE ARRAY USED TO STORE THE NEW NUMBERING
555     /* assigned_level_pST- ON OUTPUT CONTAINS LEVEL STRUCTURE
556     /* LSTPT[i]- ON OUTPUT, INDEX INTO assigned_level_pST TO FIRST NODE IN ITH assigned_level_p
557     /* LSTPT(I+1) - LSTPT[i] = NUMBER OF NODES IN ITH assigned_level_p
558     /* reverse_diameter_tree- =+1 if start_node2 IS FORWARD END OF PSEUDO-diameter
559     /* =-1 if start_node2 IS REVERSE END OF PSEUDO-diameter
560     /* newBandwidth- BANDWIDTH OF NEW NUMBERING COMPUTED BY NUMBER
561     /* newProfile- PROFILE OF NEW NUMBERING COMPUTED BY NUMBER
562     /* IPFA- WORKING STORAGE USED TO COMPUTE PROFILE AND BANDWIDTH
563     /* DirectionLargestComponent- INDICATES STEP DIRECTION USED IN NUMBERING(+1 OR -1)
564     /* USE INTEGER*2 pattern_p WITH AN IBM 360 OR 370.
565     INTEGER pattern_p
566     INTEGER start_node2, node_indexA, node_indexB, node_indexC, node_indexD, XA, XB, ConnectedComponentCounter, XD, CX, END,
567     * new_label_p, TEST
568     COMMON /GRA/ N, num_levels, ndeg_max
569     /* THE STORAGE IN COMMON BLOCKS CC AND assigned_level_pW IS NOW FREE AND CAN
570     /* BE USED FOR STACKS.
571     COMMON /assigned_level_pW/ node_indexA(100), node_indexB(100), node_indexC(100)
572     COMMON /CC/ node_indexD(100)
573     DIMENSION IPFA(1)
574     DIMENSION pattern_p(N,1), backward_levels_p(1), degree_p(1), new_label_p(1), assigned_level_pST(1),
575     * LSTPT(1)
576     /* SET UP assigned_level_pST AND LSTPT FROM backward_levels_p
577     for (10 i=0,i<N,++i)
578     IPFA[i] = 0
579     10 CONTINUE
580     NSTPT = 1
581     for (30 I=1,num_levels
582     LSTPT[i] = NSTPT
583     for (20 J=1,N
584     if (backward_levels_p(J)!=I) GO TO 20
585     assigned_level_pST(NSTPT) = J
586     NSTPT = NSTPT + 1
587     20 CONTINUE
588     30 CONTINUE
589     LSTPT(num_levels+1) = NSTPT
590     /* node_indexA, node_indexB, node_indexC AND node_indexD ARE STACKS WITH POINTERS
591     /* XA,XB,ConnectedComponentCounter, AND XD. CX IS A SPECIAL POINTER INTO node_indexC WHICH
592     /* INDICATES THE PARTICULAR NODE BEING PROCESSED.
593     /* first_available_in_list_of_tree_nodes KEEPS TRACK OF THE LEVEL WE ARE WORKING AT.
594     /* INITIALLY node_indexC CONTAINS ONLY THE INITIAL NODE, start_node2.
595     first_available_in_list_of_tree_nodes = 0
596     if (reverse_diameter_tree<0) first_available_in_list_of_tree_nodes = num_levels + 1
597     ConnectedComponentCounter = 1
598     node_indexC(ConnectedComponentCounter) = start_node2
599     40 CX = 1
600     XD = 0
601     first_available_in_list_of_tree_nodes = first_available_in_list_of_tree_nodes + reverse_diameter_tree
602     LST = LSTPT(first_available_in_list_of_tree_nodes)
603     LND = LSTPT(first_available_in_list_of_tree_nodes+1) - 1
604     /* BEGIN PROCESSING NODE node_indexC(CX)
605     50 IPRO = node_indexC(CX)
606     new_label_p(IPRO) = NUM
607     NUM = NUM + DirectionLargestComponent
608     END = degree_p(IPRO)
609     XA = 0
610     XB = 0
611     /* CHECK ALL ADJACENT NODES
612     for (80 I=1,END
613     TEST = pattern_p(IPRO,I)
614     INX = new_label_p(TEST)
615     /* ONLY NODES NOT NUMBERED OR ALREADY ON A STACK ARE ADDED
616     if (INX.EQ.0) GO TO 60
617     if (INX<0) GO TO 80
618     /* for (PRELIMINARY BANDWIDTH AND PROFILE CALCULATIONS
619     NBW = (new_label_p(IPRO)-INX)*DirectionLargestComponent
620     if (DirectionLargestComponent>0) INX = new_label_p(IPRO)
621     if (IPFA(INX)<NBW) IPFA(INX) = NBW
622     GO TO 80
623     60 new_label_p(TEST) = -1
624     /* PUT NODES ON SAME LEVEL ON node_indexA, ALL OTHERS ON node_indexB
625     if (backward_levels_p(TEST).EQ.backward_levels_p(IPRO)) GO TO 70
626     XB = XB + 1
627     node_indexB(XB) = TEST
628     GO TO 80
629     70 XA = XA + 1
630     node_indexA(XA) = TEST
631     80 CONTINUE
632     /* SORT node_indexA AND node_indexB INTO INCREASING degree_p AND ADD node_indexA TO node_indexC
633     /* AND node_indexB TO node_indexD
634     if (XA.EQ.0) GO TO 100
635     if (XA.EQ.1) GO TO 90
636     CALL Paso_SystemMatrixPattern_sortByDegree(node_indexC, node_indexA, ConnectedComponentCounter, XA, degree_p)
637     GO TO 100
638     90 ConnectedComponentCounter = ConnectedComponentCounter + 1
639     node_indexC(ConnectedComponentCounter) = node_indexA(XA)
640     100 if (XB.EQ.0) GO TO 120
641     if (XB.EQ.1) GO TO 110
642     CALL Paso_SystemMatrixPattern_sortByDegree(node_indexD, node_indexB, XD, XB, degree_p)
643     GO TO 120
644     110 XD = XD + 1
645     node_indexD(XD) = node_indexB(XB)
646     /* BE SURE TO PROCESS ALL NODES IN node_indexC
647     120 CX = CX + 1
648     if (ConnectedComponentCounter>=CX) GO TO 50
649     /* WHEN node_indexC IS EXHAUSTED LOOK FOR MIN degree_p NODE IN SAME LEVEL
650     /* WHICH HAS NOT BEEN PROCESSED
651     MAX = ndeg_max + 1
652     start_node2 = N + 1
653     for (130 I=LST,LND
654     TEST = assigned_level_pST[i]
655     if (new_label_p(TEST)!=0) GO TO 130
656     if (degree_p(TEST)>=MAX) GO TO 130
657     new_label_p(start_node2) = 0
658     new_label_p(TEST) = -1
659     MAX = degree_p(TEST)
660     start_node2 = TEST
661     130 CONTINUE
662     if (start_node2.EQ.N+1) GO TO 140
663     ConnectedComponentCounter = ConnectedComponentCounter + 1
664     node_indexC(ConnectedComponentCounter) = start_node2
665     GO TO 50
666     /* if node_indexD IS EMPTY WE ARE DONE, OTHERWISE COPY node_indexD ONTO node_indexC
667     /* AND BEGIN PROCESSING NEW node_indexC
668     140 if (XD.EQ.0) GO TO 160
669     for (150 I=1,XD
670     node_indexC[i] = node_indexD[i]
671     150 CONTINUE
672     ConnectedComponentCounter = XD
673     GO TO 40
674     /* for (FINAL BANDWIDTH AND PROFILE CALCULATIONS
675     160 for (170 i=0,i<N,++i)
676     if (IPFA[i]>newBandwidth) newBandwidth = IPFA[i]
677     newProfile = newProfile + IPFA[i]
678     170 CONTINUE
679     RETURN
680     END

  ViewVC Help
Powered by ViewVC 1.1.26