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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1050 - (show annotations)
Tue Mar 20 09:39:11 2007 UTC (12 years, 11 months ago) by gross
File size: 31446 byte(s)
rename so compilation does not fail
1
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