! Determine which rows of a general sparse matrix can be computed together. \param color is a vector with color.size() == m. For i = 0 , ... , m-1, color[i] is the color for the corresponding row of the matrix. If color[i1]==color[i2], (i1, j1) is in sparsity pattern, and (i2, j2) is in sparsity pattern, then j1 is not equal to j2. \param m is the number of rows in the matrix. \param n is the n
| 46 | */ |
| 47 | // ---------------------------------------------------------------------- |
| 48 | void cppad_colpack_general( |
| 49 | CppAD::vector<size_t>& color , |
| 50 | size_t m , |
| 51 | size_t n , |
| 52 | const CppAD::vector<unsigned int*>& adolc_pattern ) |
| 53 | { size_t i, k; |
| 54 | CPPAD_ASSERT_UNKNOWN( adolc_pattern.size() == m ); |
| 55 | CPPAD_ASSERT_UNKNOWN( color.size() == m ); |
| 56 | |
| 57 | // Use adolc sparsity pattern to create corresponding bipartite graph |
| 58 | ColPack::BipartiteGraphPartialColoringInterface graph( |
| 59 | SRC_MEM_ADOLC, |
| 60 | adolc_pattern.data(), |
| 61 | m, |
| 62 | n |
| 63 | ); |
| 64 | |
| 65 | // row ordered Partial-Distance-Two-Coloring of the bipartite graph |
| 66 | graph.PartialDistanceTwoColoring( |
| 67 | "SMALLEST_LAST", "ROW_PARTIAL_DISTANCE_TWO" |
| 68 | ); |
| 69 | |
| 70 | // ---------------------------------------------------------------------- |
| 71 | // If we had access to BipartiteGraphPartialColoring::m_vi_LeftVertexColors |
| 72 | // we could access the coloring and not need to go through seed matrix; see |
| 73 | // BipartiteGraphPartialColoring::GetLeftSeedMatrix_unmanaged in colpack |
| 74 | // and cppad_colpack_symmetric below. |
| 75 | // ---------------------------------------------------------------------- |
| 76 | |
| 77 | // Use coloring information to create seed matrix |
| 78 | int n_seed_row; |
| 79 | int n_seed_col; |
| 80 | double** seed_matrix = graph.GetSeedMatrix(&n_seed_row, &n_seed_col); |
| 81 | CPPAD_ASSERT_UNKNOWN( size_t(n_seed_col) == m ); |
| 82 | |
| 83 | // now return coloring in format required by CppAD |
| 84 | for(i = 0; i < m; i++) |
| 85 | color[i] = m; |
| 86 | for(k = 0; k < size_t(n_seed_row); k++) |
| 87 | { for(i = 0; i < m; i++) |
| 88 | { if( seed_matrix[k][i] != 0.0 ) |
| 89 | { // check that entries in the seed matrix are zero or one |
| 90 | CPPAD_ASSERT_UNKNOWN( seed_matrix[k][i] == 1.0 ); |
| 91 | // check that no row appears twice in the coloring |
| 92 | CPPAD_ASSERT_UNKNOWN( color[i] == m ); |
| 93 | // only need include rows with non-zero entries |
| 94 | if( adolc_pattern[i][0] != 0 ) |
| 95 | { // set color for this row |
| 96 | color[i] = k; |
| 97 | } |
| 98 | } |
| 99 | } |
| 100 | } |
| 101 | # ifndef NDEBUG |
| 102 | // check non-zero versus color for each row |
| 103 | for(i = 0; i < m; i++) |
| 104 | { |
| 105 | // if there is a color for row i, check that it has non-zero entries |
no test coverage detected