/[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 1055 - (hide annotations)
Thu Mar 22 04:49:23 2007 UTC (12 years, 11 months ago) by gross
File size: 35072 byte(s)
a bit of work towards the bandwidth optimizer
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 gross 1055 /* ConnectedComponents_p(D2) Finley_Reduce_setCharacteristics, Finley_Reduce_findDiameter, Paso_BandwidthReduction_dropTree AND NUMBER.
28 gross 1050 /* 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 gross 1055 /* ConnectedComponents_p
55 gross 1050 /* LOCAL STORAGE--
56 gross 1055 /* COMMON/CC/-SUBROUTINES Finley_Reduce, Paso_BandwidthReduction_sortConnectedComponentsInfos AND Paso_BandwidthReduction_chooseFinalLeveling ASSUME THAT
57 gross 1050 /* 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 gross 1055 /* COMMON/assigned_level_pW/-SUBROUTINES Paso_BandwidthReduction_setup AND Paso_BandwidthReduction_chooseFinalLeveling ASSUME THAT THERE
61 gross 1050 /* ARE AT MOST 100 LEVELS.
62 gross 1055 SUBROUTINE Finley_Reduce(pattern_p, N, label_p, new_label_p, degree_p, assigned_level_p, forward_levels_p,backward_levels_p, ConnectedComponents_p, newBandwidth, newProfile, NIN, ndeg_maxIN)
63 gross 1050 /* USE INTEGER*2 pattern_p WITH AN IBM 360 OR 370.
64     integer NIN, ndeg_maxIN
65     INTEGER pattern_p
66 gross 1055 INTEGER start_node, end_node, new_label_p, connected_component_counter, Paso_BandwidthReduction_sortConnectedComponentsInfos, last_available_node_number, ConnectedComponents_p,
67     * connected_component_size_p, connected_component_ptr, first_available_node_number
68 gross 1050 COMMON /GRA/ N, num_levels, ndeg_max
69     /* IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
70 gross 1055 COMMON /CC/ connected_component_counter, connected_component_size_p(50), connected_component_ptr(50)
71     COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), num_nodes_in_level_p(100)
72     DIMENSION ConnectedComponents_p(1), label_p(1)
73 gross 1050 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 gross 1055 Paso_BandwidthReduction_p* pattern_p,
99 gross 1050
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 gross 1055 Finley_Reduce_findDiameter(*start_node,
154     end_node, pattern_p, degree_p,
155     assigned_level_p,
156     forward_levels_p,backward_levels_p,
157     ConnectedComponents_p,
158     IDFLT)
159 gross 1050 /* reverse_diameter_tree INDICATES THE END TO BEGIN NUMBERING ON */
160     if (degree_p(start_node)>degree_p(end_node)) {
161     reverse_diameter_tree = TRUE;
162     start_node = end_node;
163     } else {
164     reverse_diameter_tree = FALSE;
165     }
166 gross 1055
167     Paso_BandwidthReduction_setup(assigned_level_p, forward_levels_p, backward_levels_p)
168     /* find all the connected components */
169     connected_component_counter = 0;
170 gross 1050 LROOT = 1
171     first_available_in_list_of_tree_nodes = 1
172     for (i=0,i<N,++i) {
173     if (assigned_level_p[i]==0) {
174 gross 1055 connected_component_counter++;
175     connected_component_ptr[connected_component_counter] = LROOT
176     Paso_BandwidthReduction_dropTree(I, pattern_p
177    
178     assigned_level_p,
179     index_t *list_of_tree_nodes_p,
180     &last_level_width,
181     &first_node_in_bottom_level,
182     &first_available_in_list_of_tree_nodes,
183     &num_levels,
184     &max_level_width, N)
185    
186     connected_component_size_p[connected_component_counter] =
187     first_node_in_bottom_level + last_level_width - LROOT;
188     LROOT = first_node_in_bottom_level + last_level_width;
189     first_available_in_list_of_tree_nodes = LROOT;
190 gross 1050 }
191     }
192 gross 1055 /* on return from Paso_BandwidthReduction_chooseFinalLeveling, DirectionLargestComponent
193     indicates the direction the largest component fell.
194     DirectionLargestComponent is modIFied now to indicate the numbering direction.
195     num is set to the proper value for this direction. */
196     if (Paso_BandwidthReduction_sortConnectedComponentsInfos(connected_component_counter,
197     connected_component_size_p,
198     connected_component_ptr) {
199     Paso_BandwidthReduction_chooseFinalLeveling(forward_levels_p,
200     backward_levels_p,
201     ConnectedComponents_p,
202     IDFLT,
203     DirectionLargestComponent)
204     }
205 gross 1050 DirectionLargestComponent = DirectionLargestComponent*reverse_diameter_tree;
206     NUM= (DirectionLargestComponent<0) ? last_available_node_number :first_available_node_number;
207    
208     CALL NUMBER(start_node, NUM, pattern_p, backward_levels_p, degree_p, new_label_p, forward_levels_p,
209 gross 1055 * assigned_level_p, N, reverse_diameter_tree, newBandwidth, newProfile, ConnectedComponents_p, DirectionLargestComponent)
210 gross 1050
211     /* update last_available_node_number or first_available_node_number after numbering */
212    
213     if (DirectionLargestComponent<0) last_available_node_number = NUM;
214     if (DirectionLargestComponent>0) first_available_node_number = NUM;
215    
216     }
217    
218     /* if original numbering is better than new one, set up to return it */
219    
220     if (newBandwidth > initial_bandwidth) {
221 gross 1055 for (i=0,i<N,++i) new_label_p[i] = label_p[i];
222 gross 1050 *newBandwidth = initial_bandwidth;
223     *newProfile = initial_profile;
224     }
225 gross 1055 return;
226 gross 1050 }
227     ===============================================
228     /* Finley_Reduce_setCharacteristics computes the degree_p of each node and stores it in the array degree_p. */
229     /* the bandwidth and profile for the original or input numbering of the graph is computed also. */
230    
231 gross 1055 void Finley_Reduce_setCharacteristics(Paso_BandwidthReduction_p *pattern_p,
232 gross 1050 dim_t *degree_p,
233     dim_t* label_p,
234     long *bandwidth,long *initial_profile) {
235    
236     long max_diff;
237     dim_t i;
238     *bandwidth = 0;
239     *profile = 0;
240     for (i=0,i<pattern_p->n_ptr,++i) {
241     max_diff = 0;
242     for (iptr=pattern_p->ptr[i],iptr<pattern_p->ptr[i+1],++i) {
243     diff = label_p[i] - label_p(pattern_p->index[iptr]);
244     max_diff = MAX(max_diff,diff);
245     }
246     *profile + = max_diff;
247     *bandwidth=MAX(*bandwidth,max_diff);
248     }
249     }
250 gross 1055 void Paso_BandwidthReduction_sortByDegree(index_t* node_index1,
251     index_t* node_index2,
252     dim_t* num_nodes1,
253     dim_t num_nodes2,
254     dim_t* degree_p)
255 gross 1050 {
256 gross 1055 /* Paso_BandwidthReduction_sortByDegree sorts node_index2 by degree_p of the NODE AND ADDS IT TO THE END
257 gross 1050 OF node_index1 IN ORDER OF LOWEST TO HIGHEST degree_p. num_nodes1 AND num_nodes2 ARE THE
258     NUMBER OF NODES IN node_index1 AND node_index2 RESPECTIVELY.
259     */
260     register bool_t swapped=TRUE;
261     register dim_t i, ipp;
262     register index_t node_index2_i, node_index2_ipp, temp;
263 gross 1055 register dim_t j=num_nodes2-1;
264 gross 1050 while (swapped && j>1) {
265     j--;
266     swapped = FALSE;
267     for (i=0; i<j; ++i) {
268     ipp=i+1
269     node_index2_i = node_index2[i]
270     node_index2_ipp = node_index2[ipp]
271     if (degree_p[node_index2_i]>degree_p[node_index2_ipp]) {
272     swapped= TRUE;
273     temp = node_index2[i];
274     node_index2[i] = node_index2[ipp];
275     node_index2[ipp] = temp;
276     }
277     }
278     }
279     for (i=0; i< num_nodes2; ++i) {
280     (*num_nodes1)++;
281     node_index1[num_nodes1] = node_index2[i]
282     }
283     return;
284     }
285    
286    
287     void Finley_Reduce_findDiameter(index_t *start_node,
288     index_t *end_node,
289     Paso_SystemMatrixPattern *pattern_p,
290     dim_t* degree_p,
291     index_t* forward_levels_p,
292     index_t* backward_levels_p,
293     *IDFLT,
294     index_t* work1_p,
295     index_t* work2_p,
296     index_t* node_list_p,
297     )
298     /*
299     Finley_Reduce_findDiameter is the control procedure for finding the pseudo-diameter of pattern
300     as well as the level structure from each end
301    
302     start_node- on input this is the node number of the first attempt at finding a diameter.
303     on output it contains the actual number used.
304     end_node - on output contains other end of diameter
305     forward_levels_p- ARRAY CONTAINING LEVEL STRUCTURE WITH start_node AS ROOT
306     backward_levels_p- ARRAY CONTAINING LEVEL STRUCTURE WITH end_node AS ROOT
307     IDFLT- reverse_diameter_tree USED IN PICKING FINAL LEVEL STRUCTURE, SET
308     =1 if WIDTH OF forward_levels_p <= WIDTH OF backward_levels_p, OTHERWISE =2
309     assigned_level_p, list_of_tree_nodes_p- WORKING STORAGE
310    
311     */
312    
313    
314     /* COMMON /GRA/ N, num_levels, ndeg_max
315     IT IS ASSUMED THAT THE LAST LEVEL HAS AT MOST 100 NODES.
316     COMMON /CC/ node_list(100)
317     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)
318     */
319     dim_t num_tree_nodes;
320     dim_t N= pattern->n_ptr;
321     bool_t find_new_starting_nodes=TRUE;
322    
323     /* find initial set of nodes as the end points of the tree created by root */
324     while (find_new_starting_nodes) {
325     num_tree_nodes = 0;
326 gross 1055 /* zero assigned_level_p to indicate all nodes are available to Paso_BandwidthReduction_dropTree */
327 gross 1050 for (i=0,i<N,++i) forward_levels_p[i] = -1;
328    
329 gross 1055 Paso_BandwidthReduction_dropTree(*(start_node),
330 gross 1050 pattern_p,
331     forward_levels_p,
332     work2_p,
333     degree_p,
334     num_tree_nodes, first_node_in_bottom_level,
335     first_available_in_list_of_tree_nodes,
336     num_levels, max_level_width_abort1, N)
337    
338     node_list_len = 0;
339     /* sort last level by degree_p and store in node_list_p */
340 gross 1055 Paso_BandwidthReduction_sortByDegree(node_list_p, &(work2_p[first_node_in_bottom_level]),
341 gross 1050 *node_list_len, last_level_width, degree_p)
342    
343     find_new_starting_nodes=FALSE;
344     /* now start searching from the ends points of the initial search */
345     NDXN=0;
346     while (NDXN < node_list_len) {
347     start_node2 = node_list[NDXN];
348    
349     /* drop a tree from start_node2 */
350     for (i=0;i<N;++i) assigned_level_p[i] = -1;
351     num_tree_nodes = 0;
352 gross 1055 Paso_BandwidthReduction_dropTree(start_node2,
353 gross 1050 pattern_p,
354     work1_p,
355     work2_p,
356     degree_p, last_level_width, first_node_in_bottom_level,
357     num_tree_nodes,
358     num_levels2,
359     max_level_width, max_level_width_abort);
360     if (num_levels2<num_levels) {
361     start_node = start_node2
362     find_new_starting_nodes=TRUE;
363     break;
364     }
365     /* STORE NARROWEST REVERSE LEVEL STRUCTURE IN backward_levels_p */
366     if (max_level_width<max_level_width_abort) {
367     max_level_width_abort = max_level_width;
368     end_node = start_node2;
369     for (i=0;i<N;++i) backward_levels_p[i] = work1_p[i];
370     }
371     NDXN++;
372     }
373     if (max_level_width_abort2<=max_level_width_abort1)
374     *IDFLT = 2
375     } else {
376     *IDFLT=1
377     }
378     return
379     }
380    
381 gross 1055 void Paso_BandwidthReduction_dropTree(index_t root,
382 gross 1050 Paso_SystemMatrixPattern *pattern_p,
383     index_t *assigned_level_p,
384     index_t *list_of_tree_nodes_p,
385     index_t *last_level_width,
386     index_t *first_node_in_bottom_level,
387     index_t *first_available_in_list_of_tree_nodes,
388     dim_t *num_levels,
389     dim_t *max_level_width, dim_t max_level_width_abort)
390    
391     /*
392 gross 1055 Paso_BandwidthReduction_dropTree drops a tree in pattern_p from root
393 gross 1050
394     assigned_level_p- array of length length pattern_p->N indicating available nodes with -1 entries.
395 gross 1055 Paso_BandwidthReduction_dropTree enters level numbers .
396 gross 1050
397     list_of_tree_nodes_p - on output contains node numbers used in tree (array of length pattern_p->N)
398     sorted by levels where list_of_tree_nodes_p[first_available_in_list_of_tree_nodes]
399     contains root and list_of_tree_nodes_p[first_node_in_bottom_level+last_level_width-1]
400     contains last node entered)
401    
402     last_level_width - on output contains width of last level
403     first_node_in_bottom_level - on output contains index into list_of_tree_nodes_p of first node in last level
404    
405     first_available_in_list_of_tree_nodes-
406     on input the first available location in list_of_tree_nodes_p
407     usually zero but if list_of_tree_nodes_p is used to store previous
408     connected components, first_available_in_list_of_tree_nodes is
409     next available location. on output the
410    
411     num_levels - number of levels
412    
413     max_level_width - on output contains the maximum level width
414     max_level_width_abort- input param which triggers early return if max_level_width becomes >= max_level_width_abort
415    
416     */
417    
418     dim_t j;
419     index_t node_now;
420     index_t i_top = first_available_in_list_of_tree_nodes;
421     index_t i_now = first_available_in_list_of_tree_nodes;
422     *max_level_width = 0;
423     *first_node_in_bottom_level = first_available_in_list_of_tree_nodes;
424     *top_level = first_available_in_list_of_tree_nodes + 1;
425     *num_levels = 0
426    
427     assigned_level_p[root] = *num_levels;
428     list_of_tree_nodes_p[i_top] = root;
429    
430     while ( ( max_level_width<max_level_width_abort ) && ( i_top >=top_level ) ) {
431    
432     num_levels++;
433    
434     while (i_now>=top_level) {
435     node_now = list_of_tree_nodes_p[i_now];
436     for (j=pattern_p->iptr[node_now],j<pattern_p->iptr[node_now+1],++j) {
437     index = pattern_p->index[j];
438     if (assigned_level_p[index]<0) {
439     assigned_level_p[index] = (*num_levels);
440     i_top++;
441     list_of_tree_nodes_p[i_top] = index
442     }
443     }
444     i_now++;
445     }
446     *last_level_width = top_level - first_node_in_bottom_level;
447     *max_level_width = MAX(*max_level_width, last_level_width);
448     *first_node_in_bottom_level = i_now;
449     *top_level = i_top + 1;
450     }
451     }
452    
453 gross 1055 void Paso_BandwidthReduction_setup(dim_t N, dim_t num_levels,
454     index_t* assigned_level_p,
455     index_t* forward_levels_p,
456     index_t* backward_levels_p,
457     dim_t* num_nodes_in_level_p)
458     {
459     /* Paso_BandwidthReduction_setup COMPUTES THE REVERSE LEVELING INFO FROM backward_levels_p AND STORES
460     IT INTO backward_levels_p. num_nodes_in_level_p[i] IS INITIALIZED TO NODES/ITH LEVEL FOR NODES
461     ON THE PSEUDO-diameter OF THE GRAPH. assigned_level_p IS INITIALIZED TO NON-
462     ZERO FOR NODES ON THE PSEUDO-diameter AND NODES IN A DifFERENT
463     COMPONENT OF THE GRAPH.
464 gross 1050 COMMON /GRA/ N, num_levels, ndeg_max
465 gross 1055 IT IS ASSUMED THAT THERE ARE AT MOST 100 LEVELS.
466     COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), num_nodes_in_level_p(100)
467     DIMENSION assigned_level_p(1), forward_levels_p(1), backward_levels_p(1)
468     */
469     register dim_t i, Itemp;
470     for (i=0;i<num_levels;++i) num_nodes_in_level_p[i] = 0;
471     for (i=0;i<N;++i) {
472     assigned_level_p[i] = 1;
473     backward_levels_p[i] = num_levels - 1 - backward_levels_p[i];
474 gross 1050 Itemp = backward_levels_p[i]
475 gross 1055 if (Itemp < num_levels) {
476     if (Itemp==forward_levels_p[i]) {
477     num_nodes_in_level_p[Itemp]++;
478     } else {
479     assigned_level_p[i] = 0;
480     }
481     }
482     }
483     return;
484     }
485    
486     bool_t Paso_BandwidthReduction_sortConnectedComponentsInfos( dim_t connected_component_counter,
487     dim_t *connected_component_size_p,
488     index_t *connected_component_ptr)
489    
490     {
491     /*
492     Paso_BandwidthReduction_sortConnectedComponentsInfos sorts connected_component_size_p
493     and connected_component_ptr into descending order according to the values
494     of connected_component_size_p.
495    
496     connected_component_counter=number of entries in each array
497    
498     INTEGER temp, ConnectedComponents_p, connected_component_size_p, connected_component_ptr, connected_component_counter
499     IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
500     COMMON /CC/ connected_component_counter, connected_component_size_p(50), connected_component_ptr(50)
501    
502     */
503     bool_t swapped = TRUE;
504     bool_t out = FALSE;
505     if (connected_component_counter>0) {
506     out = TRUE;
507     j = connected_component_counter-1;
508     while (j>1 && swapped) {
509     swapped = FALSE;
510     j--;
511     for (i=0; i<j; i++) {
512     ipp= i + 1;
513     if (connected_component_size_p[i]<connected_component_size_p[ipp]) {
514     swapped = TRUE;
515     temp = connected_component_size_p[i];
516     connected_component_size_p[i] = connected_component_size_p[ipp];
517     connected_component_size_p[ipp] = temp;
518     temp = connected_component_ptr[i];
519     connected_component_ptr[i] = connected_component_ptr[ipp];
520     connected_component_ptr[ipp] = temp;
521     }
522     }
523     }
524     }
525     return out;
526     }
527     void Paso_BandwidthReduction_chooseFinalLeveling(
528     index_t *forward_levels_p,
529     index_t *backward_levels_p,
530     index_t *ConnectedComponents_p,
531     IDFLT,
532     DirectionLargestComponent
533     connected_component_counter
534     connected_component_size_p
535     connected_component_ptr)
536     /*
537    
538     Paso_BandwidthReduction_chooseFinalLeveling chooses the level structure used in
539     numbering graph
540    
541     forward_levels_p- on input contains forward leveling info
542     backward_levels_p- on input contains reverse leveling info
543     on output the final level structure chosen
544     ConnectedComponents_p - ON INPUT CONTAINS CONNECTED COMPONENT INFO
545     IDFLT- ON INPUT =1 if WDTH forward_levels_p<=WDTH backward_levels_p, =2 OTHERWISE
546     NHIGH KEEPS TRACK OF LEVEL WIDTHS FOR HIGH NUMBERING
547     NLOW- KEEPS TRACK OF LEVEL WIDTHS FOR LOW NUMBERING
548     num_nodes_in_level_p- KEEPS TRACK OF LEVEL WIDTHS FOR CHOSEN LEVEL STRUCTURE
549     connected_component_counter- NUMBER OF CONNECTED COMPONENTS
550     connected_component_size_p[i]- connected_component_size_p OF ITH CONNECTED COMPONENT
551     connected_component_ptr[i]- INDEX INTO ConnectedComponents_pE OF 1ST NODE IN ITH CON COMPT
552     DirectionLargestComponent- reverse_diameter_tree WHICH INDICATES WHICH WAY THE LARGEST CONNECTED COMPONENT FELL. =+1 if LOW AND -1 if HIGH
553    
554     INTEGER ConnectedComponents_p, connected_component_size_p, connected_component_ptr, connected_component_counter, END
555 gross 1050 COMMON /GRA/ N, num_levels, ndeg_max
556 gross 1055 IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 COMPONENTS AND
557     THAT THERE ARE AT MOST 100 LEVELS.
558     COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), num_nodes_in_level_p(100)
559     COMMON /CC/ connected_component_counter, connected_component_size_p(50), connected_component_ptr(50)
560     DIMENSION forward_levels_p(1), backward_levels_p(1), ConnectedComponents_p(1)
561    
562     */
563     /* FOR EACH CONNECTED COMPONENT DO */
564     for (80 I=1,connected_component_counter
565     J = connected_component_ptr[i]
566     END = connected_component_size_p[i] + J - 1
567     /* SET NHIGH AND NLOW EQUAL TO num_nodes_in_level_p */
568 gross 1050 for (10 K=1,num_levels
569 gross 1055 NHIGH(K) = num_nodes_in_level_p(K)
570     NLOW(K) = num_nodes_in_level_p(K)
571 gross 1050 10 CONTINUE
572 gross 1055 /* UPDATE NHIGH AND NLOW FOR EACH NODE IN CONNECTED COMPONENT */
573 gross 1050 for (20 K=J,END
574 gross 1055 INODE = ConnectedComponents_p(K)
575 gross 1050 first_available_in_list_of_tree_nodesH = forward_levels_p(INODE)
576     NHIGH(first_available_in_list_of_tree_nodesH) = NHIGH(first_available_in_list_of_tree_nodesH) + 1
577     first_available_in_list_of_tree_nodesL = backward_levels_p(INODE)
578     NLOW(first_available_in_list_of_tree_nodesL) = NLOW(first_available_in_list_of_tree_nodesL) + 1
579     20 CONTINUE
580     MAnum_nodes1 = 0
581     MAnum_nodes2 = 0
582 gross 1055 /* SET MAnum_nodes1=LARGEST NEW NUMBER IN NHIGH */
583     /* SET MAnum_nodes2=LARGEST NEW NUMBER IN NLOW */
584 gross 1050 for (30 K=1,num_levels
585 gross 1055 if (2*num_nodes_in_level_p(K).EQ.NLOW(K)+NHIGH(K)) GO TO 30
586 gross 1050 if (NHIGH(K)>MAnum_nodes1) MAnum_nodes1 = NHIGH(K)
587     if (NLOW(K)>MAnum_nodes2) MAnum_nodes2 = NLOW(K)
588     30 CONTINUE
589 gross 1055 /* SET IT= NUMBER OF LEVEL STRUCTURE TO BE USED */
590 gross 1050 IT = 1
591     if (MAnum_nodes1>MAnum_nodes2) IT = 2
592     if (MAnum_nodes1.EQ.MAnum_nodes2) IT = IDFLT
593     if (IT.EQ.2) GO TO 60
594     if (I.EQ.1) DirectionLargestComponent = -1
595 gross 1055 /* COPY forward_levels_p INTO backward_levels_p FOR EACH NODE IN CONNECTED COMPONENT */
596 gross 1050 for (40 K=J,END
597 gross 1055 INODE = ConnectedComponents_p(K)
598 gross 1050 backward_levels_p(INODE) = forward_levels_p(INODE)
599     40 CONTINUE
600 gross 1055 /* UPDATE num_nodes_in_level_p TO BE THE SAME AS NHIGH */
601 gross 1050 for (50 K=1,num_levels
602 gross 1055 num_nodes_in_level_p(K) = NHIGH(K)
603 gross 1050 50 CONTINUE
604     GO TO 80
605 gross 1055 /* UPDATE num_nodes_in_level_p TO BE THE SAME AS NLOW */
606 gross 1050 60 for (70 K=1,num_levels
607 gross 1055 num_nodes_in_level_p(K) = NLOW(K)
608 gross 1050 70 CONTINUE
609     80 CONTINUE
610 gross 1055 return;
611     }
612    
613 gross 1050 SUBROUTINE NUMBER(start_node2, NUM, pattern_p, backward_levels_p, degree_p, new_label_p, assigned_level_pST, NUM 10
614 gross 1055 * Lconnected_component_ptr, N, reverse_diameter_tree, newBandwidth, newProfile, IPFA, DirectionLargestComponent)
615 gross 1050 /* NUMBER PRODUCES THE NUMBERING OF THE GRAPH FOR MIN BANDWIDTH
616     /* start_node2- ON INPUT THE NODE TO BEGIN NUMBERING ON
617     /* NUM- ON INPUT AND OUTPUT, THE NEXT AVAILABLE NUMBER
618     /* backward_levels_p- THE LEVEL STRUCTURE TO BE USED IN NUMBERING
619     /* new_label_p- THE ARRAY USED TO STORE THE NEW NUMBERING
620     /* assigned_level_pST- ON OUTPUT CONTAINS LEVEL STRUCTURE
621 gross 1055 /* Lconnected_component_ptr[i]- ON OUTPUT, INDEX INTO assigned_level_pST TO FIRST NODE IN ITH assigned_level_p
622     /* Lconnected_component_ptr(I+1) - Lconnected_component_ptr[i] = NUMBER OF NODES IN ITH assigned_level_p
623 gross 1050 /* reverse_diameter_tree- =+1 if start_node2 IS FORWARD END OF PSEUDO-diameter
624     /* =-1 if start_node2 IS REVERSE END OF PSEUDO-diameter
625     /* newBandwidth- BANDWIDTH OF NEW NUMBERING COMPUTED BY NUMBER
626     /* newProfile- PROFILE OF NEW NUMBERING COMPUTED BY NUMBER
627     /* IPFA- WORKING STORAGE USED TO COMPUTE PROFILE AND BANDWIDTH
628     /* DirectionLargestComponent- INDICATES STEP DIRECTION USED IN NUMBERING(+1 OR -1)
629     /* USE INTEGER*2 pattern_p WITH AN IBM 360 OR 370.
630     INTEGER pattern_p
631 gross 1055 INTEGER start_node2, node_indexA, node_indexB, node_indexC, node_indexD, XA, XB, connected_component_counter, XD, CX, END,
632 gross 1050 * new_label_p, TEST
633     COMMON /GRA/ N, num_levels, ndeg_max
634     /* THE STORAGE IN COMMON BLOCKS CC AND assigned_level_pW IS NOW FREE AND CAN
635     /* BE USED FOR STACKS.
636     COMMON /assigned_level_pW/ node_indexA(100), node_indexB(100), node_indexC(100)
637     COMMON /CC/ node_indexD(100)
638     DIMENSION IPFA(1)
639     DIMENSION pattern_p(N,1), backward_levels_p(1), degree_p(1), new_label_p(1), assigned_level_pST(1),
640 gross 1055 * Lconnected_component_ptr(1)
641     /* SET UP assigned_level_pST AND Lconnected_component_ptr FROM backward_levels_p
642 gross 1050 for (10 i=0,i<N,++i)
643     IPFA[i] = 0
644     10 CONTINUE
645 gross 1055 Nconnected_component_ptr = 1
646 gross 1050 for (30 I=1,num_levels
647 gross 1055 Lconnected_component_ptr[i] = Nconnected_component_ptr
648 gross 1050 for (20 J=1,N
649     if (backward_levels_p(J)!=I) GO TO 20
650 gross 1055 assigned_level_pST(Nconnected_component_ptr) = J
651     Nconnected_component_ptr = Nconnected_component_ptr + 1
652 gross 1050 20 CONTINUE
653     30 CONTINUE
654 gross 1055 Lconnected_component_ptr(num_levels+1) = Nconnected_component_ptr
655 gross 1050 /* node_indexA, node_indexB, node_indexC AND node_indexD ARE STACKS WITH POINTERS
656 gross 1055 /* XA,XB,connected_component_counter, AND XD. CX IS A SPECIAL POINTER INTO node_indexC WHICH
657 gross 1050 /* INDICATES THE PARTICULAR NODE BEING PROCESSED.
658     /* first_available_in_list_of_tree_nodes KEEPS TRACK OF THE LEVEL WE ARE WORKING AT.
659     /* INITIALLY node_indexC CONTAINS ONLY THE INITIAL NODE, start_node2.
660     first_available_in_list_of_tree_nodes = 0
661     if (reverse_diameter_tree<0) first_available_in_list_of_tree_nodes = num_levels + 1
662 gross 1055 connected_component_counter = 1
663     node_indexC(connected_component_counter) = start_node2
664 gross 1050 40 CX = 1
665     XD = 0
666     first_available_in_list_of_tree_nodes = first_available_in_list_of_tree_nodes + reverse_diameter_tree
667 gross 1055 LST = Lconnected_component_ptr(first_available_in_list_of_tree_nodes)
668     LND = Lconnected_component_ptr(first_available_in_list_of_tree_nodes+1) - 1
669 gross 1050 /* BEGIN PROCESSING NODE node_indexC(CX)
670     50 IPRO = node_indexC(CX)
671     new_label_p(IPRO) = NUM
672     NUM = NUM + DirectionLargestComponent
673     END = degree_p(IPRO)
674     XA = 0
675     XB = 0
676     /* CHECK ALL ADJACENT NODES
677     for (80 I=1,END
678     TEST = pattern_p(IPRO,I)
679     INX = new_label_p(TEST)
680     /* ONLY NODES NOT NUMBERED OR ALREADY ON A STACK ARE ADDED
681     if (INX.EQ.0) GO TO 60
682     if (INX<0) GO TO 80
683     /* for (PRELIMINARY BANDWIDTH AND PROFILE CALCULATIONS
684     NBW = (new_label_p(IPRO)-INX)*DirectionLargestComponent
685     if (DirectionLargestComponent>0) INX = new_label_p(IPRO)
686     if (IPFA(INX)<NBW) IPFA(INX) = NBW
687     GO TO 80
688     60 new_label_p(TEST) = -1
689     /* PUT NODES ON SAME LEVEL ON node_indexA, ALL OTHERS ON node_indexB
690     if (backward_levels_p(TEST).EQ.backward_levels_p(IPRO)) GO TO 70
691     XB = XB + 1
692     node_indexB(XB) = TEST
693     GO TO 80
694     70 XA = XA + 1
695     node_indexA(XA) = TEST
696     80 CONTINUE
697     /* SORT node_indexA AND node_indexB INTO INCREASING degree_p AND ADD node_indexA TO node_indexC
698     /* AND node_indexB TO node_indexD
699     if (XA.EQ.0) GO TO 100
700     if (XA.EQ.1) GO TO 90
701 gross 1055 CALL Paso_BandwidthReduction_sortByDegree(node_indexC, node_indexA, connected_component_counter, XA, degree_p)
702 gross 1050 GO TO 100
703 gross 1055 90 connected_component_counter = connected_component_counter + 1
704     node_indexC(connected_component_counter) = node_indexA(XA)
705 gross 1050 100 if (XB.EQ.0) GO TO 120
706     if (XB.EQ.1) GO TO 110
707 gross 1055 CALL Paso_BandwidthReduction_sortByDegree(node_indexD, node_indexB, XD, XB, degree_p)
708 gross 1050 GO TO 120
709     110 XD = XD + 1
710     node_indexD(XD) = node_indexB(XB)
711     /* BE SURE TO PROCESS ALL NODES IN node_indexC
712     120 CX = CX + 1
713 gross 1055 if (connected_component_counter>=CX) GO TO 50
714 gross 1050 /* WHEN node_indexC IS EXHAUSTED LOOK FOR MIN degree_p NODE IN SAME LEVEL
715     /* WHICH HAS NOT BEEN PROCESSED
716     MAX = ndeg_max + 1
717     start_node2 = N + 1
718     for (130 I=LST,LND
719     TEST = assigned_level_pST[i]
720     if (new_label_p(TEST)!=0) GO TO 130
721     if (degree_p(TEST)>=MAX) GO TO 130
722     new_label_p(start_node2) = 0
723     new_label_p(TEST) = -1
724     MAX = degree_p(TEST)
725     start_node2 = TEST
726     130 CONTINUE
727     if (start_node2.EQ.N+1) GO TO 140
728 gross 1055 connected_component_counter = connected_component_counter + 1
729     node_indexC(connected_component_counter) = start_node2
730 gross 1050 GO TO 50
731     /* if node_indexD IS EMPTY WE ARE DONE, OTHERWISE COPY node_indexD ONTO node_indexC
732     /* AND BEGIN PROCESSING NEW node_indexC
733     140 if (XD.EQ.0) GO TO 160
734     for (150 I=1,XD
735     node_indexC[i] = node_indexD[i]
736     150 CONTINUE
737 gross 1055 connected_component_counter = XD
738 gross 1050 GO TO 40
739     /* for (FINAL BANDWIDTH AND PROFILE CALCULATIONS
740     160 for (170 i=0,i<N,++i)
741     if (IPFA[i]>newBandwidth) newBandwidth = IPFA[i]
742     newProfile = newProfile + IPFA[i]
743     170 CONTINUE
744     RETURN
745     END

  ViewVC Help
Powered by ViewVC 1.1.26