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

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1054 by gross, Tue Mar 20 09:39:11 2007 UTC revision 1055 by gross, Thu Mar 22 04:49:23 2007 UTC
# Line 24  Line 24 
24  /*    assigned_level_p(D2)             DECREASED FOR IBM 360 AND 370 COMPUTERS  /*    assigned_level_p(D2)             DECREASED FOR IBM 360 AND 370 COMPUTERS
25  /*    forward_levels_p(D2)           BY REPLACING INTEGER pattern_p BY  /*    forward_levels_p(D2)           BY REPLACING INTEGER pattern_p BY
26  /*    backward_levels_p(D2)           INTEGER*2 pattern_p IN SUBROUTINES Finley_Reduce,  /*    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.  /*    ConnectedComponents_p(D2)          Finley_Reduce_setCharacteristics, Finley_Reduce_findDiameter, Paso_BandwidthReduction_dropTree AND NUMBER.
28  /*  COMMON INFORMATION--THE FOLLOWING COMMON BLOCK MUST BE IN THE  /*  COMMON INFORMATION--THE FOLLOWING COMMON BLOCK MUST BE IN THE
29  /*  CALLING ROUTINE.  /*  CALLING ROUTINE.
30  /*    COMMON/GRA/N,num_levels,ndeg_max  /*    COMMON/GRA/N,num_levels,ndeg_max
# Line 51  Line 51 
51  /*    backward_levels_p[i]-  the level assigned to node i by Finley_Reduce.  /*    backward_levels_p[i]-  the level assigned to node i by Finley_Reduce.
52    
53  /*  WORKING STORAGE VARIABLE--  /*  WORKING STORAGE VARIABLE--
54  /*    ConnectedComponents  /*    ConnectedComponents_p
55  /*  LOCAL STORAGE--  /*  LOCAL STORAGE--
56  /*    COMMON/CC/-SUBROUTINES Finley_Reduce, SORT2 AND PIKassigned_level_p ASSUME THAT  /*    COMMON/CC/-SUBROUTINES Finley_Reduce, Paso_BandwidthReduction_sortConnectedComponentsInfos AND Paso_BandwidthReduction_chooseFinalLeveling ASSUME THAT
57  /*               THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.  /*               THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
58  /*               SUBROUTINE Finley_Reduce_findDiameter ASSUMES THAT THERE ARE AT MOST  /*               SUBROUTINE Finley_Reduce_findDiameter ASSUMES THAT THERE ARE AT MOST
59  /*               100 NODES IN THE LAST LEVEL.  /*               100 NODES IN THE LAST LEVEL.
60  /*    COMMON/assigned_level_pW/-SUBROUTINES Finley_Reduce_setup AND PIKassigned_level_p ASSUME THAT THERE  /*    COMMON/assigned_level_pW/-SUBROUTINES Paso_BandwidthReduction_setup AND Paso_BandwidthReduction_chooseFinalLeveling ASSUME THAT THERE
61  /*               ARE AT MOST 100 LEVELS.  /*               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)        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  /* USE INTEGER*2 pattern_p  WITH AN IBM 360 OR 370.  /* USE INTEGER*2 pattern_p  WITH AN IBM 360 OR 370.
64      integer NIN, ndeg_maxIN      integer NIN, ndeg_maxIN
65        INTEGER pattern_p        INTEGER pattern_p
66        INTEGER start_node, end_node, new_label_p, ConnectedComponentCounter, SORT2, last_available_node_number, ConnectedComponents,        INTEGER start_node, end_node, new_label_p, connected_component_counter, Paso_BandwidthReduction_sortConnectedComponentsInfos, last_available_node_number, ConnectedComponents_p,
67       * SIZE, STPT, first_available_node_number       * connected_component_size_p, connected_component_ptr, first_available_node_number
68        COMMON /GRA/ N, num_levels, ndeg_max        COMMON /GRA/ N, num_levels, ndeg_max
69  /* IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.  /* IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
70        COMMON /CC/ ConnectedComponentCounter, SIZE(50), STPT(50)        COMMON /CC/ connected_component_counter, connected_component_size_p(50), connected_component_ptr(50)
71        COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), NACUM(100)        COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), num_nodes_in_level_p(100)
72        DIMENSION ConnectedComponents(1), label_p(1)        DIMENSION ConnectedComponents_p(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),        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)       * degree_p(1)
75        newBandwidth = 0        newBandwidth = 0
# Line 95  c Line 95  c
95      /* COMPUTE degree_p OF EACH NODE AND ORIGINAL BANDWIDTH AND PROFILE*/      /* COMPUTE degree_p OF EACH NODE AND ORIGINAL BANDWIDTH AND PROFILE*/
96    
97  ===============================  ===============================
98  Paso_SystemMatrixpattern_p* pattern_p,  Paso_BandwidthReduction_p* pattern_p,
99    
100            
101      long initial_bandwidth, initial_profile      long initial_bandwidth, initial_profile
# Line 150  Paso_SystemMatrixpattern_p* pattern_p, Line 150  Paso_SystemMatrixpattern_p* pattern_p,
150       /* start_node and end_node are the ends of the diameter and       /* 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. */          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,        Finley_Reduce_findDiameter(*start_node,
154                                   assigned_level_p, forward_levels_p,backward_levels_p, ConnectedComponents, IDFLT)                                   end_node, pattern_p, degree_p,
155                                     assigned_level_p,
156                                     forward_levels_p,backward_levels_p,
157                                     ConnectedComponents_p,
158                                     IDFLT)
159        /* reverse_diameter_tree INDICATES THE END TO BEGIN NUMBERING ON */        /* reverse_diameter_tree INDICATES THE END TO BEGIN NUMBERING ON */
160        if (degree_p(start_node)>degree_p(end_node)) {        if (degree_p(start_node)>degree_p(end_node)) {
161              reverse_diameter_tree = TRUE;              reverse_diameter_tree = TRUE;
# Line 159  Paso_SystemMatrixpattern_p* pattern_p, Line 163  Paso_SystemMatrixpattern_p* pattern_p,
163        } else {        } else {
164              reverse_diameter_tree = FALSE;              reverse_diameter_tree = FALSE;
165        }        }
166  #########  
167        CALL Finley_Reduce_setup(assigned_level_p, forward_levels_p, backward_levels_p)        Paso_BandwidthReduction_setup(assigned_level_p, forward_levels_p, backward_levels_p)
168        /* find all the connected components  (ConnectedComponentCounter counts them) */        /* find all the connected components  */
169        ConnectedComponentCounter = 0;        connected_component_counter = 0;
170        LROOT = 1        LROOT = 1
171        first_available_in_list_of_tree_nodes = 1        first_available_in_list_of_tree_nodes = 1
172        for (i=0,i<N,++i) {        for (i=0,i<N,++i) {
173          if (assigned_level_p[i]==0) {          if (assigned_level_p[i]==0) {
174             ConnectedComponentCounter++;             connected_component_counter++;
175             STPT(ConnectedComponentCounter) = LROOT             connected_component_ptr[connected_component_counter] = LROOT
176             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)             Paso_BandwidthReduction_dropTree(I, pattern_p
177             SIZE(ConnectedComponentCounter) = first_node_in_bottom_level + last_level_width - LROOT                                        
178             LROOT = first_node_in_bottom_level + last_level_width                                         assigned_level_p,
179             first_available_in_list_of_tree_nodes = LROOT                                         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          }          }
191        }        }
192  /* on return from PIKassigned_level_p, DirectionLargestComponent indicates the direction the largest component fell. */        /* on return from Paso_BandwidthReduction_chooseFinalLeveling, DirectionLargestComponent
193  /* DirectionLargestComponent is modIFied now to indicate the numbering direction. num is set to the proper value for this direction. */           indicates the direction  the largest component fell.
194        if (SORT2(DMY)!=0) PIKassigned_level_p(forward_levels_p, backward_levels_p, ConnectedComponents, IDFLT, DirectionLargestComponent)           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        DirectionLargestComponent = DirectionLargestComponent*reverse_diameter_tree;        DirectionLargestComponent = DirectionLargestComponent*reverse_diameter_tree;
206        NUM= (DirectionLargestComponent<0) ?  last_available_node_number :first_available_node_number;        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,        CALL NUMBER(start_node, NUM, pattern_p, backward_levels_p, degree_p, new_label_p, forward_levels_p,
209       * assigned_level_p, N, reverse_diameter_tree, newBandwidth, newProfile, ConnectedComponents, DirectionLargestComponent)       * assigned_level_p, N, reverse_diameter_tree, newBandwidth, newProfile, ConnectedComponents_p, DirectionLargestComponent)
210    
211        /* update last_available_node_number or first_available_node_number after numbering */        /* update last_available_node_number or first_available_node_number after numbering */
212    
# Line 194  Paso_SystemMatrixpattern_p* pattern_p, Line 218  Paso_SystemMatrixpattern_p* pattern_p,
218     /* if original numbering is better than new one, set up to return it */     /* if original numbering is better than new one, set up to return it */
219    
220     if (newBandwidth > initial_bandwidth) {     if (newBandwidth > initial_bandwidth) {
221           for (i=0,i<N,++i)           for (i=0,i<N,++i) new_label_p[i] = label_p[i];
              new_label_p[i] = label_p[i];  
222           *newBandwidth = initial_bandwidth;           *newBandwidth = initial_bandwidth;
223           *newProfile = initial_profile;           *newProfile = initial_profile;
224     }     }
225       return;
226  }  }
227  ===============================================  ===============================================
228  /*  Finley_Reduce_setCharacteristics computes the degree_p of each node and stores it in the array degree_p. */  /*  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. */  /*  the bandwidth and profile for the original or input numbering  of the graph is computed also. */
230    
231  void Finley_Reduce_setCharacteristics(Paso_SystemMatrixpattern_p *pattern_p,  void Finley_Reduce_setCharacteristics(Paso_BandwidthReduction_p *pattern_p,
232                                        dim_t *degree_p,                                        dim_t *degree_p,
233                                        dim_t* label_p,                                        dim_t* label_p,
234                                        long *bandwidth,long *initial_profile) {                                        long *bandwidth,long *initial_profile) {
# Line 223  void Finley_Reduce_setCharacteristics(Pa Line 247  void Finley_Reduce_setCharacteristics(Pa
247          *bandwidth=MAX(*bandwidth,max_diff);          *bandwidth=MAX(*bandwidth,max_diff);
248       }       }
249  }  }
250  void Paso_SystemMatrixPattern_sortByDegree(index_t* node_index1, index_t* node_index2, dim_t* num_nodes1, dim_t num_nodes2, dim_t* degree_p)  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  {  {
256     /* Paso_SystemMatrixPattern_sortByDegree sorts node_index2 by degree_p of the NODE AND ADDS IT TO THE END     /* Paso_BandwidthReduction_sortByDegree sorts node_index2 by degree_p of the NODE AND ADDS IT TO THE END
257        OF node_index1 IN ORDER OF LOWEST TO HIGHEST degree_p.  num_nodes1 AND num_nodes2 ARE THE        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.        NUMBER OF NODES IN node_index1 AND node_index2 RESPECTIVELY.
259     */     */
260     register bool_t swapped=TRUE;     register bool_t swapped=TRUE;
261     register dim_t i, ipp;     register dim_t i, ipp;
262     register index_t node_index2_i, node_index2_ipp, temp;     register index_t node_index2_i, node_index2_ipp, temp;
263     register dim_t j=num_nodes2;     register dim_t j=num_nodes2-1;
264     while (swapped && j>1) {     while (swapped && j>1) {
265           j--;           j--;
266           swapped = FALSE;           swapped = FALSE;
# Line 295  void Finley_Reduce_findDiameter(index_t Line 323  void Finley_Reduce_findDiameter(index_t
323       /* find initial set of nodes as the end points of the tree created by root */       /* find initial set of nodes as the end points of the tree created by root */
324       while (find_new_starting_nodes) {       while (find_new_starting_nodes) {
325           num_tree_nodes = 0;           num_tree_nodes = 0;
326           /* zero assigned_level_p to indicate all nodes are available to Paso_SystemMatrixPattern_dropTree */           /* zero assigned_level_p to indicate all nodes are available to Paso_BandwidthReduction_dropTree */
327           for (i=0,i<N,++i) forward_levels_p[i] = -1;           for (i=0,i<N,++i) forward_levels_p[i] = -1;
328    
329           Paso_SystemMatrixPattern_dropTree(*(start_node),           Paso_BandwidthReduction_dropTree(*(start_node),
330                                             pattern_p,                                             pattern_p,
331                                             forward_levels_p,                                             forward_levels_p,
332                                             work2_p,                                             work2_p,
# Line 309  void Finley_Reduce_findDiameter(index_t Line 337  void Finley_Reduce_findDiameter(index_t
337    
338           node_list_len = 0;           node_list_len = 0;
339           /* sort last level by degree_p  and store in node_list_p */           /* sort last level by degree_p  and store in node_list_p */
340           Paso_SystemMatrixPattern_sortByDegree(node_list_p, &(work2_p[first_node_in_bottom_level]),           Paso_BandwidthReduction_sortByDegree(node_list_p, &(work2_p[first_node_in_bottom_level]),
341                                                 *node_list_len, last_level_width, degree_p)                                                 *node_list_len, last_level_width, degree_p)
342    
343           find_new_starting_nodes=FALSE;           find_new_starting_nodes=FALSE;
# Line 321  void Finley_Reduce_findDiameter(index_t Line 349  void Finley_Reduce_findDiameter(index_t
349         /* drop a tree from start_node2 */         /* drop a tree from start_node2 */
350         for (i=0;i<N;++i) assigned_level_p[i] = -1;         for (i=0;i<N;++i) assigned_level_p[i] = -1;
351         num_tree_nodes = 0;         num_tree_nodes = 0;
352         Paso_SystemMatrixPattern_dropTree(start_node2,         Paso_BandwidthReduction_dropTree(start_node2,
353                                           pattern_p,                                           pattern_p,
354                                           work1_p,                                           work1_p,
355                                           work2_p,                                           work2_p,
# Line 350  void Finley_Reduce_findDiameter(index_t Line 378  void Finley_Reduce_findDiameter(index_t
378        return        return
379  }  }
380    
381  void Paso_SystemMatrixPattern_dropTree(index_t root,  void Paso_BandwidthReduction_dropTree(index_t root,
382                                         Paso_SystemMatrixPattern *pattern_p,                                         Paso_SystemMatrixPattern *pattern_p,
383                                         index_t *assigned_level_p,                                         index_t *assigned_level_p,
384                                         index_t *list_of_tree_nodes_p,                                         index_t *list_of_tree_nodes_p,
# Line 361  void Paso_SystemMatrixPattern_dropTree(i Line 389  void Paso_SystemMatrixPattern_dropTree(i
389                                         dim_t *max_level_width, dim_t max_level_width_abort)                                         dim_t *max_level_width, dim_t max_level_width_abort)
390    
391  /*    /*  
392     Paso_SystemMatrixPattern_dropTree drops a tree in pattern_p from root     Paso_BandwidthReduction_dropTree drops a tree in pattern_p from root
393    
394     assigned_level_p-           array of length length pattern_p->N indicating available nodes with -1 entries.     assigned_level_p-           array of length length pattern_p->N indicating available nodes with -1 entries.
395                                 Paso_SystemMatrixPattern_dropTree enters level numbers .                                 Paso_BandwidthReduction_dropTree enters level numbers .
396    
397     list_of_tree_nodes_p -   on output contains node numbers used in tree (array of length pattern_p->N)     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]                                   sorted by levels where list_of_tree_nodes_p[first_available_in_list_of_tree_nodes]  
# Line 422  void Paso_SystemMatrixPattern_dropTree(i Line 450  void Paso_SystemMatrixPattern_dropTree(i
450     }     }
451  }  }
452    
453        SUBROUTINE Finley_Reduce_setup(assigned_level_p, forward_levels_p, backward_levels_p)                               SET   10  void Paso_BandwidthReduction_setup(dim_t N, dim_t num_levels,
454  /* Finley_Reduce_setup COMPUTES THE REVERSE LEVELING INFO FROM backward_levels_p AND STORES                                     index_t* assigned_level_p,
455  /* IT INTO backward_levels_p.  NACUM[i] IS INITIALIZED TO NODES/ITH LEVEL FOR NODES                                     index_t* forward_levels_p,
456  /* ON THE PSEUDO-diameter OF THE GRAPH.  assigned_level_p IS INITIALIZED TO NON-                                     index_t* backward_levels_p,
457  /* ZERO FOR NODES ON THE PSEUDO-diameter AND NODES IN A DifFERENT                                     dim_t* num_nodes_in_level_p)
458  /* COMPONENT OF THE GRAPH.  {
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        COMMON /GRA/ N, num_levels, ndeg_max        COMMON /GRA/ N, num_levels, ndeg_max
465  /* IT IS ASSUMED THAT THERE ARE AT MOST 100 LEVELS.        IT IS ASSUMED THAT THERE ARE AT MOST 100 LEVELS.
466        COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), NACUM(100)        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)        DIMENSION assigned_level_p(1), forward_levels_p(1), backward_levels_p(1)
468        for (10 I=1,num_levels      */
469          NACUM[i] = 0        register dim_t i, Itemp;  
470     10 CONTINUE        for (i=0;i<num_levels;++i) num_nodes_in_level_p[i] = 0;
471        for (30 i=0,i<N,++i)        for (i=0;i<N;++i) {
472          assigned_level_p[i] = 1          assigned_level_p[i] = 1;
473          backward_levels_p[i] = num_levels + 1 - backward_levels_p[i]          backward_levels_p[i] = num_levels - 1 - backward_levels_p[i];
474          Itemp = backward_levels_p[i]          Itemp = backward_levels_p[i]
475          if (Itemp>num_levels) GO TO 30          if (Itemp < num_levels) {
476          if (Itemp!=forward_levels_p[i]) GO TO 20              if (Itemp==forward_levels_p[i]) {
477          NACUM(Itemp) = NACUM(Itemp) + 1                num_nodes_in_level_p[Itemp]++;
478          GO TO 30            } else {
479     20   assigned_level_p[i] = 0               assigned_level_p[i] = 0;
480     30 CONTINUE            }
481        RETURN          }
482        END        }
483        INTEGER FUNCTION SORT2(DMY)                                       SOR   10        return;
484  /* SORT2 SORTS SIZE AND STPT INTO DESCENDING ORDER ACCORDING TO  }
485  /* VALUES OF SIZE. ConnectedComponentCounter=NUMBER OF ENTRIES IN EACH ARRAY  
486        INTEGER temp, ConnectedComponents, SIZE, STPT, ConnectedComponentCounter  bool_t Paso_BandwidthReduction_sortConnectedComponentsInfos(                                                          dim_t connected_component_counter,
487  /* IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.                                                             dim_t *connected_component_size_p,
488        COMMON /CC/ ConnectedComponentCounter, SIZE(50), STPT(50)                                                             index_t *connected_component_ptr)
489        SORT2 = 0  
490        if (ConnectedComponentCounter.EQ.0) RETURN  {                                
491        SORT2 = 1  /*
492        IND = ConnectedComponentCounter     Paso_BandwidthReduction_sortConnectedComponentsInfos sorts connected_component_size_p
493     10 ITEST = 0     and connected_component_ptr into descending order according to the values
494        IND = IND - 1     of connected_component_size_p.
495        if (IND<1) RETURN    
496        for (20 I=1,IND     connected_component_counter=number of entries in each array
497          J = I + 1      
498          if (SIZE[i]>=SIZE(J)) GO TO 20        INTEGER temp, ConnectedComponents_p, connected_component_size_p, connected_component_ptr, connected_component_counter
499          ITEST = 1        IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
500          temp = SIZE[i]        COMMON /CC/ connected_component_counter, connected_component_size_p(50), connected_component_ptr(50)
501          SIZE[i] = SIZE(J)  
502          SIZE(J) = temp  */
503          temp = STPT[i]        bool_t swapped = TRUE;
504          STPT[i] = STPT(J)        bool_t out = FALSE;
505          STPT(J) = temp        if (connected_component_counter>0) {
506     20 CONTINUE            out = TRUE;
507        if (ITEST.EQ.1) GO TO 10            j = connected_component_counter-1;
508        RETURN            while (j>1 && swapped) {
509        END              swapped = FALSE;
510        SUBROUTINE PIKassigned_level_p(forward_levels_p, backward_levels_p, ConnectedComponents, IDFLT, DirectionLargestComponent)             PIK   10              j--;
511  /* PIKassigned_level_p CHOOSES THE LEVEL STRUCTURE  USED IN NUMBERING GRAPH              for (i=0; i<j; i++) {
512  /* forward_levels_p-       ON INPUT CONTAINS FORWARD LEVELING INFO                 ipp= i + 1;
513  /* backward_levels_p-       ON INPUT CONTAINS REVERSE LEVELING INFO                 if (connected_component_size_p[i]<connected_component_size_p[ipp]) {
514  /*              ON OUTPUT THE FINAL LEVEL STRUCTURE CHOSEN                    swapped = TRUE;
515  /* ConnectedComponents-      ON INPUT CONTAINS CONNECTED COMPONENT INFO                    temp = connected_component_size_p[i];
516  /* IDFLT-       ON INPUT =1 if WDTH forward_levels_p<=WDTH backward_levels_p, =2 OTHERWISE                    connected_component_size_p[i] = connected_component_size_p[ipp];
517  /* NHIGH        KEEPS TRACK OF LEVEL WIDTHS FOR HIGH NUMBERING                    connected_component_size_p[ipp] = temp;
518  /* NLOW-        KEEPS TRACK OF LEVEL WIDTHS FOR LOW NUMBERING                    temp = connected_component_ptr[i];
519  /* NACUM-       KEEPS TRACK OF LEVEL WIDTHS FOR CHOSEN LEVEL STRUCTURE                    connected_component_ptr[i] = connected_component_ptr[ipp];
520  /* ConnectedComponentCounter-          NUMBER OF CONNECTED COMPONENTS                    connected_component_ptr[ipp] = temp;
521  /* SIZE[i]-     SIZE OF ITH CONNECTED COMPONENT                 }
522  /* STPT[i]-     INDEX INTO ConnectedComponentsE OF 1ST NODE IN ITH CON COMPT              }
523  /* DirectionLargestComponent-       reverse_diameter_tree WHICH INDICATES WHICH WAY THE LARGEST CONNECTED           }
524  /*              COMPONENT FELL.  =+1 if LOW AND -1 if HIGH        }
525        INTEGER ConnectedComponents, SIZE, STPT, ConnectedComponentCounter, END        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        COMMON /GRA/ N, num_levels, ndeg_max        COMMON /GRA/ N, num_levels, ndeg_max
556  /* IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 COMPONENTS AND    IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 COMPONENTS AND
557  /* THAT THERE ARE AT MOST 100 LEVELS.    THAT THERE ARE AT MOST 100 LEVELS.
558        COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), NACUM(100)        COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), num_nodes_in_level_p(100)
559        COMMON /CC/ ConnectedComponentCounter, SIZE(50), STPT(50)        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(1)        DIMENSION forward_levels_p(1), backward_levels_p(1), ConnectedComponents_p(1)
561  /* FOR EACH CONNECTED COMPONENT DO        
562        for (80 I=1,ConnectedComponentCounter  */
563          J = STPT[i]  /* FOR EACH CONNECTED COMPONENT DO */
564          END = SIZE[i] + J - 1        for (80 I=1,connected_component_counter
565  /* SET NHIGH AND NLOW EQUAL TO NACUM          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          for (10 K=1,num_levels          for (10 K=1,num_levels
569            NHIGH(K) = NACUM(K)            NHIGH(K) = num_nodes_in_level_p(K)
570            NLOW(K) = NACUM(K)            NLOW(K) = num_nodes_in_level_p(K)
571     10   CONTINUE     10   CONTINUE
572  /* UPDATE NHIGH AND NLOW FOR EACH NODE IN CONNECTED COMPONENT  /* UPDATE NHIGH AND NLOW FOR EACH NODE IN CONNECTED COMPONENT */
573          for (20 K=J,END          for (20 K=J,END
574            INODE = ConnectedComponents(K)            INODE = ConnectedComponents_p(K)
575            first_available_in_list_of_tree_nodesH = forward_levels_p(INODE)            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            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)            first_available_in_list_of_tree_nodesL = backward_levels_p(INODE)
# Line 515  void Paso_SystemMatrixPattern_dropTree(i Line 579  void Paso_SystemMatrixPattern_dropTree(i
579     20   CONTINUE     20   CONTINUE
580          MAnum_nodes1 = 0          MAnum_nodes1 = 0
581          MAnum_nodes2 = 0          MAnum_nodes2 = 0
582  /* SET MAnum_nodes1=LARGEST NEW NUMBER IN NHIGH  /* SET MAnum_nodes1=LARGEST NEW NUMBER IN NHIGH */
583  /* SET MAnum_nodes2=LARGEST NEW NUMBER IN NLOW  /* SET MAnum_nodes2=LARGEST NEW NUMBER IN NLOW */
584          for (30 K=1,num_levels          for (30 K=1,num_levels
585            if (2*NACUM(K).EQ.NLOW(K)+NHIGH(K)) GO TO 30            if (2*num_nodes_in_level_p(K).EQ.NLOW(K)+NHIGH(K)) GO TO 30
586            if (NHIGH(K)>MAnum_nodes1) MAnum_nodes1 = NHIGH(K)            if (NHIGH(K)>MAnum_nodes1) MAnum_nodes1 = NHIGH(K)
587            if (NLOW(K)>MAnum_nodes2) MAnum_nodes2 = NLOW(K)            if (NLOW(K)>MAnum_nodes2) MAnum_nodes2 = NLOW(K)
588     30   CONTINUE     30   CONTINUE
589  /* SET IT= NUMBER OF LEVEL STRUCTURE TO BE USED  /* SET IT= NUMBER OF LEVEL STRUCTURE TO BE USED */
590          IT = 1          IT = 1
591          if (MAnum_nodes1>MAnum_nodes2) IT = 2          if (MAnum_nodes1>MAnum_nodes2) IT = 2
592          if (MAnum_nodes1.EQ.MAnum_nodes2) IT = IDFLT          if (MAnum_nodes1.EQ.MAnum_nodes2) IT = IDFLT
593          if (IT.EQ.2) GO TO 60          if (IT.EQ.2) GO TO 60
594          if (I.EQ.1) DirectionLargestComponent = -1          if (I.EQ.1) DirectionLargestComponent = -1
595  /* COPY forward_levels_p INTO backward_levels_p FOR EACH NODE IN CONNECTED COMPONENT  /* COPY forward_levels_p INTO backward_levels_p FOR EACH NODE IN CONNECTED COMPONENT */
596          for (40 K=J,END          for (40 K=J,END
597            INODE = ConnectedComponents(K)            INODE = ConnectedComponents_p(K)
598            backward_levels_p(INODE) = forward_levels_p(INODE)            backward_levels_p(INODE) = forward_levels_p(INODE)
599     40   CONTINUE     40   CONTINUE
600  /* UPDATE NACUM TO BE THE SAME AS NHIGH  /* UPDATE num_nodes_in_level_p TO BE THE SAME AS NHIGH */
601          for (50 K=1,num_levels          for (50 K=1,num_levels
602            NACUM(K) = NHIGH(K)            num_nodes_in_level_p(K) = NHIGH(K)
603     50   CONTINUE     50   CONTINUE
604          GO TO 80          GO TO 80
605  /* UPDATE NACUM TO BE THE SAME AS NLOW  /* UPDATE num_nodes_in_level_p TO BE THE SAME AS NLOW */
606     60   for (70 K=1,num_levels     60   for (70 K=1,num_levels
607            NACUM(K) = NLOW(K)            num_nodes_in_level_p(K) = NLOW(K)
608     70   CONTINUE     70   CONTINUE
609     80 CONTINUE     80 CONTINUE
610        RETURN     return;
611        END  }
612    
613        SUBROUTINE NUMBER(start_node2, NUM, pattern_p, backward_levels_p, degree_p, new_label_p, assigned_level_pST,     NUM   10        SUBROUTINE NUMBER(start_node2, NUM, pattern_p, backward_levels_p, degree_p, new_label_p, assigned_level_pST,     NUM   10
614       * LSTPT, N, reverse_diameter_tree, newBandwidth, newProfile, IPFA, DirectionLargestComponent)       * Lconnected_component_ptr, N, reverse_diameter_tree, newBandwidth, newProfile, IPFA, DirectionLargestComponent)
615  /*  NUMBER PRODUCES THE NUMBERING OF THE GRAPH FOR MIN BANDWIDTH  /*  NUMBER PRODUCES THE NUMBERING OF THE GRAPH FOR MIN BANDWIDTH
616  /*  start_node2-         ON INPUT THE NODE TO BEGIN NUMBERING ON  /*  start_node2-         ON INPUT THE NODE TO BEGIN NUMBERING ON
617  /*  NUM-         ON INPUT AND OUTPUT, THE NEXT AVAILABLE NUMBER  /*  NUM-         ON INPUT AND OUTPUT, THE NEXT AVAILABLE NUMBER
618  /*  backward_levels_p-       THE LEVEL STRUCTURE TO BE USED IN NUMBERING  /*  backward_levels_p-       THE LEVEL STRUCTURE TO BE USED IN NUMBERING
619  /*  new_label_p-       THE ARRAY USED TO STORE THE NEW NUMBERING  /*  new_label_p-       THE ARRAY USED TO STORE THE NEW NUMBERING
620  /*  assigned_level_pST-       ON OUTPUT CONTAINS LEVEL STRUCTURE  /*  assigned_level_pST-       ON OUTPUT CONTAINS LEVEL STRUCTURE
621  /*  LSTPT[i]-    ON OUTPUT, INDEX INTO assigned_level_pST TO FIRST NODE IN ITH assigned_level_p  /*  Lconnected_component_ptr[i]-    ON OUTPUT, INDEX INTO assigned_level_pST TO FIRST NODE IN ITH assigned_level_p
622  /*               LSTPT(I+1) - LSTPT[i] = NUMBER OF NODES IN ITH assigned_level_p  /*               Lconnected_component_ptr(I+1) - Lconnected_component_ptr[i] = NUMBER OF NODES IN ITH assigned_level_p
623  /*  reverse_diameter_tree-        =+1 if start_node2 IS FORWARD END OF PSEUDO-diameter  /*  reverse_diameter_tree-        =+1 if start_node2 IS FORWARD END OF PSEUDO-diameter
624  /*               =-1 if start_node2 IS REVERSE END OF PSEUDO-diameter  /*               =-1 if start_node2 IS REVERSE END OF PSEUDO-diameter
625  /*  newBandwidth-        BANDWIDTH OF NEW NUMBERING COMPUTED BY NUMBER  /*  newBandwidth-        BANDWIDTH OF NEW NUMBERING COMPUTED BY NUMBER
# Line 563  void Paso_SystemMatrixPattern_dropTree(i Line 628  void Paso_SystemMatrixPattern_dropTree(i
628  /*  DirectionLargestComponent-       INDICATES STEP DIRECTION USED IN NUMBERING(+1 OR -1)  /*  DirectionLargestComponent-       INDICATES STEP DIRECTION USED IN NUMBERING(+1 OR -1)
629  /* USE INTEGER*2 pattern_p  WITH AN IBM 360 OR 370.  /* USE INTEGER*2 pattern_p  WITH AN IBM 360 OR 370.
630        INTEGER pattern_p        INTEGER pattern_p
631        INTEGER start_node2, node_indexA, node_indexB, node_indexC, node_indexD, XA, XB, ConnectedComponentCounter, XD, CX, END,        INTEGER start_node2, node_indexA, node_indexB, node_indexC, node_indexD, XA, XB, connected_component_counter, XD, CX, END,
632       * new_label_p, TEST       * new_label_p, TEST
633        COMMON /GRA/ N, num_levels, ndeg_max        COMMON /GRA/ N, num_levels, ndeg_max
634  /* THE STORAGE IN COMMON BLOCKS CC AND assigned_level_pW IS NOW FREE AND CAN  /* THE STORAGE IN COMMON BLOCKS CC AND assigned_level_pW IS NOW FREE AND CAN
# Line 572  void Paso_SystemMatrixPattern_dropTree(i Line 637  void Paso_SystemMatrixPattern_dropTree(i
637        COMMON /CC/ node_indexD(100)        COMMON /CC/ node_indexD(100)
638        DIMENSION IPFA(1)        DIMENSION IPFA(1)
639        DIMENSION pattern_p(N,1), backward_levels_p(1), degree_p(1), new_label_p(1), assigned_level_pST(1),        DIMENSION pattern_p(N,1), backward_levels_p(1), degree_p(1), new_label_p(1), assigned_level_pST(1),
640       * LSTPT(1)       * Lconnected_component_ptr(1)
641  /* SET UP assigned_level_pST AND LSTPT FROM backward_levels_p  /* SET UP assigned_level_pST AND Lconnected_component_ptr FROM backward_levels_p
642        for (10 i=0,i<N,++i)        for (10 i=0,i<N,++i)
643          IPFA[i] = 0          IPFA[i] = 0
644     10 CONTINUE     10 CONTINUE
645        NSTPT = 1        Nconnected_component_ptr = 1
646        for (30 I=1,num_levels        for (30 I=1,num_levels
647          LSTPT[i] = NSTPT          Lconnected_component_ptr[i] = Nconnected_component_ptr
648          for (20 J=1,N          for (20 J=1,N
649            if (backward_levels_p(J)!=I) GO TO 20            if (backward_levels_p(J)!=I) GO TO 20
650            assigned_level_pST(NSTPT) = J            assigned_level_pST(Nconnected_component_ptr) = J
651            NSTPT = NSTPT + 1            Nconnected_component_ptr = Nconnected_component_ptr + 1
652     20   CONTINUE     20   CONTINUE
653     30 CONTINUE     30 CONTINUE
654        LSTPT(num_levels+1) = NSTPT        Lconnected_component_ptr(num_levels+1) = Nconnected_component_ptr
655  /* node_indexA, node_indexB, node_indexC AND node_indexD ARE STACKS WITH POINTERS  /* node_indexA, node_indexB, node_indexC AND node_indexD ARE STACKS WITH POINTERS
656  /* XA,XB,ConnectedComponentCounter, AND XD.  CX IS A SPECIAL POINTER INTO node_indexC WHICH  /* XA,XB,connected_component_counter, AND XD.  CX IS A SPECIAL POINTER INTO node_indexC WHICH
657  /* INDICATES THE PARTICULAR NODE BEING PROCESSED.  /* INDICATES THE PARTICULAR NODE BEING PROCESSED.
658  /* first_available_in_list_of_tree_nodes KEEPS TRACK OF THE LEVEL WE ARE WORKING AT.  /* 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.  /* INITIALLY node_indexC CONTAINS ONLY THE INITIAL NODE, start_node2.
660        first_available_in_list_of_tree_nodes = 0        first_available_in_list_of_tree_nodes = 0
661        if (reverse_diameter_tree<0) first_available_in_list_of_tree_nodes = num_levels + 1        if (reverse_diameter_tree<0) first_available_in_list_of_tree_nodes = num_levels + 1
662        ConnectedComponentCounter = 1        connected_component_counter = 1
663        node_indexC(ConnectedComponentCounter) = start_node2        node_indexC(connected_component_counter) = start_node2
664     40 CX = 1     40 CX = 1
665        XD = 0        XD = 0
666        first_available_in_list_of_tree_nodes = first_available_in_list_of_tree_nodes + reverse_diameter_tree        first_available_in_list_of_tree_nodes = first_available_in_list_of_tree_nodes + reverse_diameter_tree
667        LST = LSTPT(first_available_in_list_of_tree_nodes)        LST = Lconnected_component_ptr(first_available_in_list_of_tree_nodes)
668        LND = LSTPT(first_available_in_list_of_tree_nodes+1) - 1        LND = Lconnected_component_ptr(first_available_in_list_of_tree_nodes+1) - 1
669  /* BEGIN PROCESSING NODE node_indexC(CX)  /* BEGIN PROCESSING NODE node_indexC(CX)
670     50 IPRO = node_indexC(CX)     50 IPRO = node_indexC(CX)
671        new_label_p(IPRO) = NUM        new_label_p(IPRO) = NUM
# Line 633  void Paso_SystemMatrixPattern_dropTree(i Line 698  void Paso_SystemMatrixPattern_dropTree(i
698  /* AND node_indexB TO node_indexD  /* AND node_indexB TO node_indexD
699        if (XA.EQ.0) GO TO 100        if (XA.EQ.0) GO TO 100
700        if (XA.EQ.1) GO TO 90        if (XA.EQ.1) GO TO 90
701        CALL Paso_SystemMatrixPattern_sortByDegree(node_indexC, node_indexA, ConnectedComponentCounter, XA, degree_p)        CALL Paso_BandwidthReduction_sortByDegree(node_indexC, node_indexA, connected_component_counter, XA, degree_p)
702        GO TO 100        GO TO 100
703     90 ConnectedComponentCounter = ConnectedComponentCounter + 1     90 connected_component_counter = connected_component_counter + 1
704        node_indexC(ConnectedComponentCounter) = node_indexA(XA)        node_indexC(connected_component_counter) = node_indexA(XA)
705    100 if (XB.EQ.0) GO TO 120    100 if (XB.EQ.0) GO TO 120
706        if (XB.EQ.1) GO TO 110        if (XB.EQ.1) GO TO 110
707        CALL Paso_SystemMatrixPattern_sortByDegree(node_indexD, node_indexB, XD, XB, degree_p)        CALL Paso_BandwidthReduction_sortByDegree(node_indexD, node_indexB, XD, XB, degree_p)
708        GO TO 120        GO TO 120
709    110 XD = XD + 1    110 XD = XD + 1
710        node_indexD(XD) = node_indexB(XB)        node_indexD(XD) = node_indexB(XB)
711  /* BE SURE TO PROCESS ALL NODES IN node_indexC  /* BE SURE TO PROCESS ALL NODES IN node_indexC
712    120 CX = CX + 1    120 CX = CX + 1
713        if (ConnectedComponentCounter>=CX) GO TO 50        if (connected_component_counter>=CX) GO TO 50
714  /* WHEN node_indexC IS EXHAUSTED LOOK FOR MIN degree_p NODE IN SAME LEVEL  /* WHEN node_indexC IS EXHAUSTED LOOK FOR MIN degree_p NODE IN SAME LEVEL
715  /* WHICH HAS NOT BEEN PROCESSED  /* WHICH HAS NOT BEEN PROCESSED
716        MAX = ndeg_max + 1        MAX = ndeg_max + 1
# Line 660  void Paso_SystemMatrixPattern_dropTree(i Line 725  void Paso_SystemMatrixPattern_dropTree(i
725          start_node2 = TEST          start_node2 = TEST
726    130 CONTINUE    130 CONTINUE
727        if (start_node2.EQ.N+1) GO TO 140        if (start_node2.EQ.N+1) GO TO 140
728        ConnectedComponentCounter = ConnectedComponentCounter + 1        connected_component_counter = connected_component_counter + 1
729        node_indexC(ConnectedComponentCounter) = start_node2        node_indexC(connected_component_counter) = start_node2
730        GO TO 50        GO TO 50
731  /* if node_indexD IS EMPTY WE ARE DONE, OTHERWISE COPY node_indexD ONTO node_indexC  /* if node_indexD IS EMPTY WE ARE DONE, OTHERWISE COPY node_indexD ONTO node_indexC
732  /* AND BEGIN PROCESSING NEW node_indexC  /* AND BEGIN PROCESSING NEW node_indexC
# Line 669  void Paso_SystemMatrixPattern_dropTree(i Line 734  void Paso_SystemMatrixPattern_dropTree(i
734        for (150 I=1,XD        for (150 I=1,XD
735          node_indexC[i] = node_indexD[i]          node_indexC[i] = node_indexD[i]
736    150 CONTINUE    150 CONTINUE
737        ConnectedComponentCounter = XD        connected_component_counter = XD
738        GO TO 40        GO TO 40
739  /* for (FINAL BANDWIDTH AND PROFILE CALCULATIONS  /* for (FINAL BANDWIDTH AND PROFILE CALCULATIONS
740    160 for (170 i=0,i<N,++i)    160 for (170 i=0,i<N,++i)
Legend:
Removed from v.1054  
changed lines
  Added in v.1055
  ViewVC Help
Powered by ViewVC 1.1.26