31 #ifndef SPARSE_COLETREE_H 32 #define SPARSE_COLETREE_H 39 template<
typename Index,
typename IndexVector>
60 template <
typename MatrixType,
typename IndexVector>
61 int coletree(
const MatrixType& mat, IndexVector& parent, IndexVector& firstRowElt,
typename MatrixType::StorageIndex *perm=0)
63 typedef typename MatrixType::StorageIndex StorageIndex;
64 StorageIndex nc = convert_index<StorageIndex>(mat.cols());
65 StorageIndex m = convert_index<StorageIndex>(mat.rows());
66 StorageIndex diagSize = (std::min)(nc,m);
71 parent.resize(mat.cols());
73 firstRowElt.resize(m);
74 firstRowElt.setConstant(nc);
75 firstRowElt.segment(0, diagSize).setLinSpaced(diagSize, 0, diagSize-1);
77 for (StorageIndex col = 0; col < nc; col++)
79 StorageIndex pcol = col;
80 if(perm) pcol = perm[col];
81 for (
typename MatrixType::InnerIterator it(mat, pcol); it; ++it)
84 firstRowElt(row) = (std::min)(firstRowElt(row), col);
91 StorageIndex rset, cset, rroot;
92 for (StorageIndex col = 0; col < nc; col++)
101 StorageIndex pcol = col;
102 if(perm) pcol = perm[col];
103 for (
typename MatrixType::InnerIterator it(mat, pcol); it||!found_diag; ++it)
106 if(it) i = it.index();
107 if (i == col) found_diag =
true;
109 StorageIndex row = firstRowElt(i);
110 if (row >= col)
continue;
111 rset = internal::etree_find(row, pp);
129 template <
typename IndexVector>
130 void nr_etdfs (
typename IndexVector::Scalar n, IndexVector& parent, IndexVector& first_kid, IndexVector& next_kid, IndexVector& post,
typename IndexVector::Scalar postnum)
132 typedef typename IndexVector::Scalar StorageIndex;
133 StorageIndex current = n, first, next;
137 first = first_kid(current);
143 post(current) = postnum++;
146 next = next_kid(current);
150 current = parent(current);
152 post(current) = postnum++;
155 next = next_kid(current);
158 if (postnum == n+1)
return;
177 template <
typename IndexVector>
178 void treePostorder(
typename IndexVector::Scalar n, IndexVector& parent, IndexVector& post)
180 typedef typename IndexVector::Scalar StorageIndex;
181 IndexVector first_kid, next_kid;
182 StorageIndex postnum;
184 first_kid.resize(n+1);
185 next_kid.setZero(n+1);
189 first_kid.setConstant(-1);
190 for (StorageIndex v = n-1; v >= 0; v--)
192 StorageIndex dad = parent(v);
193 next_kid(v) = first_kid(dad);
199 internal::nr_etdfs(n, parent, first_kid, next_kid, post, postnum);
206 #endif // SPARSE_COLETREE_H Namespace containing all symbols from the Eigen library.
Definition: Core:141
EIGEN_DEFAULT_DENSE_INDEX_TYPE Index
The Index type as used for the API.
Definition: Meta.h:74
Definition: Eigen_Colamd.h:50