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