09 August 2013 12:21:30 PM

RCM_PRB
  C++ version
  Test the RCM library.

TEST01
  ADJ_SET sets up an adjacency matrix incrementally.

ADJ_SET - Note:
  Initializing adjacency information.
  Number of nodes NODE_NUM =  10
  Maximum adjacency ADJ_MAX = 90

  Creating and recording adjacency information:

        10         9
         6         5
         1         3
         2         1
         7         1
         5         5
         8         8
         1         9
         4         1
         1         9
         9         2
         1         3
        10         2
         4         9
         3         7
         6         9
         5        10
         6         2
         8         4
         2         6

  Random adjacency matrix:

  Sparse adjacency structure:

  Number of nodes       = 10
  Number of adjacencies = 30

  Node Min Max      Nonzeros 

     1     1     5          2       3       4       7       9
     2     6     9          1       6       9      10
     3    10    11          1       7
     4    12    14          1       8       9
     5    15    16          6      10
     6    17    19          2       5       9
     7    20    21          1       3
     8    22    22          4
     9    23    27          1       2       4       6      10
    10    28    30          2       5       9

  Nonzero structure of matrix:

         1 DXXX..X.X.
         2 XD...X..XX
         3 X.D...X...
         4 X..D...XX.
         5 ....DX...X
         6 .X..XD..X.
         7 X.X...D...
         8 ...X...D..
         9 XX.X.X..DX
        10 .X..X...XD

  Lower bandwidth = 8
  Lower envelope contains 15 nonzeros.

TEST02
  GENRCM reorders the nodes in a graph using
  the Reverse Cuthill McKee algorithm.

  Adjacency matrix:

  Sparse adjacency structure:

  Number of nodes       = 10
  Number of adjacencies = 28

  Node Min Max      Nonzeros 

     1     1     2          4       6
     2     3     6          3       5       7      10
     3     7     9          2       4       5
     4    10    13          1       3       6       9
     5    14    16          2       3       7
     6    17    20          1       4       7       8
     7    21    24          2       5       6       8
     8    25    26          6       7
     9    27    27          4
    10    28    28          2

  Nonzero structure of matrix:

         1 D..X.X....
         2 .DX.X.X..X
         3 .XDXX.....
         4 X.XD.X..X.
         5 .XX.D.X...
         6 X..X.DXX..
         7 .X..XXDX..
         8 .....XXD..
         9 ...X....D.
        10 .X.......D

  Lower bandwidth = 8
  Lower envelope contains 14 nonzeros.

  ADJ bandwidth = 17

  The RCM permutation and inverse:

         1         9         2
         2         1         9
         3         8         8
         4         6         5
         5         4         7
         6         7         4
         7         5         6
         8         3         3
         9         2         1
        10        10        10

  Permuted adjacency matrix:


  Nonzero structure of matrix:

         1 D...X.....
         2 .D.XX.....
         3 ..DX.X....
         4 .XXDXX....
         5 XX.XD..X..
         6 ..XX.DX.X.
         7 .....XDXX.
         8 ....X.XDX.
         9 .....XXXDX
        10 ........XD

  Lower bandwidth = 4
  Lower envelope contains 14 nonzeros.

  ADJ (permuted) bandwidth = 9

TEST03
  GENRCM generates the Reverse Cuthill McKee ordering.

  Do the test twice.  On the second test, randomly
  permute the initial nodes.

  TRIANGLE_NODE:

  Row:      1       2       3  
  Col

    1       1       2       6  
    2       7       6       2  
    3       2       3       7  
    4       8       7       3  
    5       3       4       8  
    6       9       8       4  
    7       4       5       9  
    8      10       9       5  
    9       6       7      11  
   10      12      11       7  
   11       7       8      12  
   12      13      12       8  
   13       8       9      13  
   14      14      13       9  
   15       9      10      14  
   16      15      14      10  
   17      11      12      16  
   18      17      16      12  
   19      12      13      17  
   20      18      17      13  
   21      13      14      18  
   22      19      18      14  
   23      14      15      19  
   24      20      19      15  
   25      16      17      21  
   26      22      21      17  
   27      17      18      22  
   28      23      22      18  
   29      18      19      23  
   30      24      23      19  
   31      19      20      24  
   32      25      24      20  


  ADJ array:

  Sparse adjacency structure:

  Number of nodes       = 25
  Number of adjacencies = 137

  Node Min Max      Nonzeros 

     1     1     3          1       2       6
     2     4     8          1       2       3       6       7
     3     9    13          2       3       4       7       8
     4    14    18          3       4       5       8       9
     5    19    22          4       5       9      10
     6    23    27          1       2       6       7      11
     7    28    34          2       3       6       7       8
                           11      12
     8    35    41          3       4       7       8       9
                           12      13
     9    42    48          4       5       8       9      10
                           13      14
    10    49    53          5       9      10      14      15
    11    54    58          6       7      11      12      16
    12    59    65          7       8      11      12      13
                           16      17
    13    66    72          8       9      12      13      14
                           17      18
    14    73    79          9      10      13      14      15
                           18      19
    15    80    84         10      14      15      19      20
    16    85    89         11      12      16      17      21
    17    90    96         12      13      16      17      18
                           21      22
    18    97   103         13      14      17      18      19
                           22      23
    19   104   110         14      15      18      19      20
                           23      24
    20   111   115         15      19      20      24      25
    21   116   119         16      17      21      22
    22   120   124         17      18      21      22      23
    23   125   129         18      19      22      23      24
    24   130   134         19      20      23      24      25
    25   135   137         20      24      25

  ADJ bandwidth = 11

  The RCM permutation:

         1         1
         2         6
         3         2
         4        11
         5         7
         6         3
         7        16
         8        12
         9         8
        10         4
        11        21
        12        17
        13        13
        14         9
        15         5
        16        22
        17        18
        18        14
        19        10
        20        23
        21        19
        22        15
        23        24
        24        20
        25        25

  Permuted ADJ bandwidth = 11

  The random permutation:

         1         6
         2        24
         3        22
         4        16
         5        13
         6         7
         7        11
         8         9
         9         8
        10        20
        11         1
        12        18
        13        12
        14        23
        15        14
        16         4
        17        25
        18        10
        19        19
        20         5
        21        17
        22        21
        23        15
        24         2
        25         3

  TRIANGLE_NODE:

  Row:      1       2       3  
  Col

    1       6      24       7  
    2      11       7      24  
    3      24      22      11  
    4       9      11      22  
    5      22      16       9  
    6       8       9      16  
    7      16      13       8  
    8      20       8      13  
    9       7      11       1  
   10      18       1      11  
   11      11       9      18  
   12      12      18       9  
   13       9       8      12  
   14      23      12       8  
   15       8      20      23  
   16      14      23      20  
   17       1      18       4  
   18      25       4      18  
   19      18      12      25  
   20      10      25      12  
   21      12      23      10  
   22      19      10      23  
   23      23      14      19  
   24       5      19      14  
   25       4      25      17  
   26      21      17      25  
   27      25      10      21  
   28      15      21      10  
   29      10      19      15  
   30       2      15      19  
   31      19       5       2  
   32       3       2       5  


  ADJ array:

  Sparse adjacency structure:

  Number of nodes       = 25
  Number of adjacencies = 137

  Node Min Max      Nonzeros 

     1     1     5          1       4       7      11      18
     2     6    10          2       3       5      15      19
     3    11    13          2       3       5
     4    14    18          1       4      17      18      25
     5    19    23          2       3       5      14      19
     6    24    26          6       7      24
     7    27    31          1       6       7      11      24
     8    32    38          8       9      12      13      16
                           20      23
     9    39    45          8       9      11      12      16
                           18      22
    10    46    52         10      12      15      19      21
                           23      25
    11    53    59          1       7       9      11      18
                           22      24
    12    60    66          8       9      10      12      18
                           23      25
    13    67    70          8      13      16      20
    14    71    75          5      14      19      20      23
    15    76    80          2      10      15      19      21
    16    81    85          8       9      13      16      22
    17    86    89          4      17      21      25
    18    90    96          1       4       9      11      12
                           18      25
    19    97   103          2       5      10      14      15
                           19      23
    20   104   108          8      13      14      20      23
    21   109   113         10      15      17      21      25
    22   114   118          9      11      16      22      24
    23   119   125          8      10      12      14      19
                           20      23
    24   126   130          6       7      11      22      24
    25   131   137          4      10      12      17      18
                           21      25

  ADJ bandwidth = 43

  The RCM permutation:

         1         3
         2         5
         3         2
         4        14
         5        19
         6        15
         7        20
         8        23
         9        10
        10        21
        11        13
        12         8
        13        12
        14        25
        15        17
        16        16
        17         9
        18        18
        19         4
        20        22
        21        11
        22         1
        23        24
        24         7
        25         6

  Permuted ADJ bandwidth = 11

TEST04
  GENRCM generates the Reverse Cuthill McKee ordering.

  The random permutation:

         1         6
         2        24
         3        22
         4        16
         5        13
         6         7
         7        11
         8         9
         9         8
        10        20
        11         1
        12        18
        13        12
        14        23
        15        14
        16         4
        17        25
        18        10
        19        19
        20         5
        21        17
        22        21
        23        15
        24         2
        25         3

  Permuted TRIANGLE_NODE

  Row:      1       2       3       4       5       6  
  Col

    1       6      22       1      24      11       7  
    2      12       1      22      18      11       9  
    3      22      13      12      16       8       9  
    4      14      12      13      23       8      20  
    5       1      12      17      18      25       4  
    6      15      17      12      21      25      10  
    7      12      14      15      23      19      10  
    8       3      15      14       2      19       5  


  ADJ array:

  Sparse adjacency structure:

  Number of nodes       = 25
  Number of adjacencies = 217

  Node Min Max      Nonzeros 

     1     1    12          1       4       6       7       9
                           11      12      17      18      22
                           24      25
     2    13    18          2       3       5      14      15
                           19
     3    19    24          2       3       5      14      15
                           19
     4    25    30          1       4      12      17      18
                           25
     5    31    36          2       3       5      14      15
                           19
     6    37    42          1       6       7      11      22
                           24
     7    43    48          1       6       7      11      22
                           24
     8    49    57          8       9      12      13      14
                           16      20      22      23
     9    58    66          1       8       9      11      12
                           13      16      18      22
    10    67    75         10      12      14      15      17
                           19      21      23      25
    11    76    84          1       6       7       9      11
                           12      18      22      24
    12    85   103          1       4       8       9      10
                           11      12      13      14      15
                           16      17      18      19      20
                           21      22      23      25
    13   104   112          8       9      12      13      14
                           16      20      22      23
    14   113   124          2       3       5       8      10
                           12      13      14      15      19
                           20      23
    15   125   136          2       3       5      10      12
                           14      15      17      19      21
                           23      25
    16   137   142          8       9      12      13      16
                           22
    17   143   151          1       4      10      12      15
                           17      18      21      25
    18   152   160          1       4       9      11      12
                           17      18      22      25
    19   161   169          2       3       5      10      12
                           14      15      19      23
    20   170   175          8      12      13      14      20
                           23
    21   176   181         10      12      15      17      21
                           25
    22   182   193          1       6       7       8       9
                           11      12      13      16      18
                           22      24
    23   194   202          8      10      12      13      14
                           15      19      20      23
    24   203   208          1       6       7      11      22
                           24
    25   209   217          1       4      10      12      15
                           17      18      21      25

  ADJ bandwidth = 49

  The RCM permutation:

         1         5
         2         3
         3         2
         4        23
         5        19
         6        20
         7        14
         8        15
         9        21
        10        10
        11        13
        12        16
        13         8
        14        12
        15        25
        16        18
        17        17
        18         9
        19         4
        20        22
        21        11
        22        24
        23         7
        24         1
        25         6

  Permuted ADJ bandwidth = 21

TEST05
  GRAPH_01_SIZE returns the sizes for graph 1.
  GRAPH_01_ADJ returns the adjacency for graph 1.
  ADJ_PRINT prints the adjacency information.

  Adjacency for GRAPH_01:

  Sparse adjacency structure:

  Number of nodes       = 10
  Number of adjacencies = 28

  Node Min Max      Nonzeros 

     1     1     2          4       6
     2     3     6          3       5       7      10
     3     7     9          2       4       5
     4    10    13          1       3       6       9
     5    14    16          2       3       7
     6    17    20          1       4       7       8
     7    21    24          2       5       6       8
     8    25    26          6       7
     9    27    27          4
    10    28    28          2

  Nonzero structure of matrix:

         1 D..X.X....
         2 .DX.X.X..X
         3 .XDXX.....
         4 X.XD.X..X.
         5 .XX.D.X...
         6 X..X.DXX..
         7 .X..XXDX..
         8 .....XXD..
         9 ...X....D.
        10 .X.......D

  Lower bandwidth = 8
  Lower envelope contains 14 nonzeros.

TEST06
  LEVEL_SET computes the level sets of a graph,
  given a root node (which defines level 1).

  Adjacency matrix:

  Sparse adjacency structure:

  Number of nodes       = 10
  Number of adjacencies = 28

  Node Min Max      Nonzeros 

     1     1     2          4       6
     2     3     6          3       5       7      10
     3     7     9          2       4       5
     4    10    13          1       3       6       9
     5    14    16          2       3       7
     6    17    20          1       4       7       8
     7    21    24          2       5       6       8
     8    25    26          6       7
     9    27    27          4
    10    28    28          2

  Nonzero structure of matrix:

         1 D..X.X....
         2 .DX.X.X..X
         3 .XDXX.....
         4 X.XD.X..X.
         5 .XX.D.X...
         6 X..X.DXX..
         7 .X..XXDX..
         8 .....XXD..
         9 ...X....D.
        10 .X.......D

  Lower bandwidth = 8
  Lower envelope contains 14 nonzeros.

LEVEL_SET_PRINT
  Show the level set structure of a rooted graph.
  The number of nodes is  10
  The number of levels is 4

  Level Min Max      Nonzeros

     1     1     1          3
     2     2     4          2       4       5
     3     5     9          7      10       1       6       9
     4    10    10          8

LEVEL_SET_PRINT
  Show the level set structure of a rooted graph.
  The number of nodes is  10
  The number of levels is 5

  Level Min Max      Nonzeros

     1     1     1         10
     2     2     2          2
     3     3     5          3       5       7
     4     6     8          4       6       8
     5     9    10          1       9

LEVEL_SET_PRINT
  Show the level set structure of a rooted graph.
  The number of nodes is  10
  The number of levels is 5

  Level Min Max      Nonzeros

     1     1     1          9
     2     2     2          4
     3     3     5          1       3       6
     4     6     9          2       5       7       8
     5    10    10         10

TEST07
  ROOT_FIND is given a node in the graph,
  and returns a better node to use as a starting
  point for reordering.

  Adjacency matrix:

  Sparse adjacency structure:

  Number of nodes       = 10
  Number of adjacencies = 28

  Node Min Max      Nonzeros 

     1     1     2          4       6
     2     3     6          3       5       7      10
     3     7     9          2       4       5
     4    10    13          1       3       6       9
     5    14    16          2       3       7
     6    17    20          1       4       7       8
     7    21    24          2       5       6       8
     8    25    26          6       7
     9    27    27          4
    10    28    28          2

  Nonzero structure of matrix:

         1 D..X.X....
         2 .DX.X.X..X
         3 .XDXX.....
         4 X.XD.X..X.
         5 .XX.D.X...
         6 X..X.DXX..
         7 .X..XXDX..
         8 .....XXD..
         9 ...X....D.
        10 .X.......D

  Lower bandwidth = 8
  Lower envelope contains 14 nonzeros.

  Starting root =    1
  Suggested root =   10
  Number of levels = 5

  Starting root =    2
  Suggested root =   10
  Number of levels = 5

  Starting root =    3
  Suggested root =   8
  Number of levels = 4

  Starting root =    4
  Suggested root =   9
  Number of levels = 5

  Starting root =    5
  Suggested root =   10
  Number of levels = 5

  Starting root =    6
  Suggested root =   9
  Number of levels = 5

  Starting root =    7
  Suggested root =   10
  Number of levels = 5

  Starting root =    8
  Suggested root =   10
  Number of levels = 5

  Starting root =    9
  Suggested root =   10
  Number of levels = 5

  Starting root =    10
  Suggested root =   9
  Number of levels = 5

TEST08
  TRIANGULATION_ORDER3_ADJ_COUNT counts the (lower)
  adjacencies defined by a triangulation.

  TRIANGLE_NODE

  Row:      1       2       3  
  Col

    1       1       2       6  
    2       7       6       2  
    3       2       3       7  
    4       8       7       3  
    5       3       4       8  
    6       9       8       4  
    7       4       5       9  
    8      10       9       5  
    9       6       7      11  
   10      12      11       7  
   11       7       8      12  
   12      13      12       8  
   13       8       9      13  
   14      14      13       9  
   15       9      10      14  
   16      15      14      10  
   17      11      12      16  
   18      17      16      12  
   19      12      13      17  
   20      18      17      13  
   21      13      14      18  
   22      19      18      14  
   23      14      15      19  
   24      20      19      15  
   25      16      17      21  
   26      22      21      17  
   27      17      18      22  
   28      23      22      18  
   29      18      19      23  
   30      24      23      19  
   31      19      20      24  
   32      25      24      20  


  ADJ_ROW

         1         1
         2         4
         3         9
         4        14
         5        19
         6        23
         7        28
         8        35
         9        42
        10        49
        11        54
        12        59
        13        66
        14        73
        15        80
        16        85
        17        90
        18        97
        19       104
        20       111
        21       116
        22       120
        23       125
        24       130
        25       135
        26       138

TEST09
  TRIANGULATION_ORDER3_ADJ_SET sets the (lower)
  adjacencies defined by a triangulation.

  TRIANGLE_NODE

  Row:      1       2       3  
  Col

    1       1       2       6  
    2       7       6       2  
    3       2       3       7  
    4       8       7       3  
    5       3       4       8  
    6       9       8       4  
    7       4       5       9  
    8      10       9       5  
    9       6       7      11  
   10      12      11       7  
   11       7       8      12  
   12      13      12       8  
   13       8       9      13  
   14      14      13       9  
   15       9      10      14  
   16      15      14      10  
   17      11      12      16  
   18      17      16      12  
   19      12      13      17  
   20      18      17      13  
   21      13      14      18  
   22      19      18      14  
   23      14      15      19  
   24      20      19      15  
   25      16      17      21  
   26      22      21      17  
   27      17      18      22  
   28      23      22      18  
   29      18      19      23  
   30      24      23      19  
   31      19      20      24  
   32      25      24      20  


  ADJ array:

  Sparse adjacency structure:

  Number of nodes       = 25
  Number of adjacencies = 137

  Node Min Max      Nonzeros 

     1     1     3          1       2       6
     2     4     8          1       2       3       6       7
     3     9    13          2       3       4       7       8
     4    14    18          3       4       5       8       9
     5    19    22          4       5       9      10
     6    23    27          1       2       6       7      11
     7    28    34          2       3       6       7       8
                           11      12
     8    35    41          3       4       7       8       9
                           12      13
     9    42    48          4       5       8       9      10
                           13      14
    10    49    53          5       9      10      14      15
    11    54    58          6       7      11      12      16
    12    59    65          7       8      11      12      13
                           16      17
    13    66    72          8       9      12      13      14
                           17      18
    14    73    79          9      10      13      14      15
                           18      19
    15    80    84         10      14      15      19      20
    16    85    89         11      12      16      17      21
    17    90    96         12      13      16      17      18
                           21      22
    18    97   103         13      14      17      18      19
                           22      23
    19   104   110         14      15      18      19      20
                           23      24
    20   111   115         15      19      20      24      25
    21   116   119         16      17      21      22
    22   120   124         17      18      21      22      23
    23   125   129         18      19      22      23      24
    24   130   134         19      20      23      24      25
    25   135   137         20      24      25

  ADJ bandwidth = 11

TEST10
  For a triangulation of a set of nodes,
  TRIANGULATION_NEIGHBOR_TRIANGLES determines the
    adjacency relationships between triangles.

  Triangles:

  Row:      1       2       3  
  Col

    1       3       4       1  
    2       3       1       2  
    3       3       2       8  
    4       2       1       5  
    5       8       2      13  
    6       8      13       9  
    7       3       8       9  
    8      13       2       5  
    9       9      13       7  
   10       7      13       5  
   11       6       7       5  
   12       9       7       6  
   13      10       9       6  
   14       6       5      12  
   15      11       6      12  
   16      10       6      11  


  Triangle neighbors:

  Row:      1       2       3  
  Col

    1      -1       2      -1  
    2       4       3       1  
    3       5       7       2  
    4      -1       8       2  
    5       8       6       3  
    6       9       7       5  
    7       6      -1       3  
    8       4      10       5  
    9      10      12       6  
   10       8      11       9  
   11      10      14      12  
   12      11      13       9  
   13      12      16      -1  
   14      -1      15      11  
   15      14      -1      16  
   16      15      -1      13  


TEST11
  TRIANGULATION_ORDER6_ADJ_COUNT counts the (lower)
  adjacencies defined by a triangulation.

  ADJ_ROW

         1         1
         2         7
         3        13
         4        25
         5        31
         6        40
         7        46
         8        55
         9        64
        10        73
        11        79
        12        91
        13       100
        14       119
        15       128
        16       140
        17       146
        18       155
        19       164
        20       173
        21       179
        22       188
        23       194
        24       206
        25       212
        26       218

TEST12
  TRIANGULATION_ORDER6_ADJ_SET sets the (lower)
  adjacencies defined by a triangulation.

  TRIANGLE_NODE

  Row:      1       2       3       4       5       6  
  Col

    1       1       3      11       2       7       6  
    2      13      11       3      12       7       8  
    3       3       5      13       4       9       8  
    4      15      13       5      14       9      10  
    5      11      13      21      12      17      16  
    6      23      21      13      22      17      18  
    7      13      15      23      14      19      18  
    8      25      23      15      24      19      20  


  ADJ array:

  Sparse adjacency structure:

  Number of nodes       = 25
  Number of adjacencies = 217

  Node Min Max      Nonzeros 

     1     1     6          1       2       3       6       7
                           11
     2     7    12          1       2       3       6       7
                           11
     3    13    24          1       2       3       4       5
                            6       7       8       9      11
                           12      13
     4    25    30          3       4       5       8       9
                           13
     5    31    39          3       4       5       8       9
                           10      13      14      15
     6    40    45          1       2       3       6       7
                           11
     7    46    54          1       2       3       6       7
                            8      11      12      13
     8    55    63          3       4       5       7       8
                            9      11      12      13
     9    64    72          3       4       5       8       9
                           10      13      14      15
    10    73    78          5       9      10      13      14
                           15
    11    79    90          1       2       3       6       7
                            8      11      12      13      16
                           17      21
    12    91    99          3       7       8      11      12
                           13      16      17      21
    13   100   118          3       4       5       7       8
                            9      10      11      12      13
                           14      15      16      17      18
                           19      21      22      23
    14   119   127          5       9      10      13      14
                           15      18      19      23
    15   128   139          5       9      10      13      14
                           15      18      19      20      23
                           24      25
    16   140   145         11      12      13      16      17
                           21
    17   146   154         11      12      13      16      17
                           18      21      22      23
    18   155   163         13      14      15      17      18
                           19      21      22      23
    19   164   172         13      14      15      18      19
                           20      23      24      25
    20   173   178         15      19      20      23      24
                           25
    21   179   187         11      12      13      16      17
                           18      21      22      23
    22   188   193         13      17      18      21      22
                           23
    23   194   205         13      14      15      17      18
                           19      20      21      22      23
                           24      25
    24   206   211         15      19      20      23      24
                           25
    25   212   217         15      19      20      23      24
                           25

  ADJ bandwidth = 21

RCM_PRB
  Normal end of execution.

09 August 2013 12:21:30 PM