31#ifndef SPARSE_COLETREE_H
32#define SPARSE_COLETREE_H
35#include "./InternalHeaderCheck.h"
42template <
typename Index,
typename IndexVector>
43Index etree_find(Index i, IndexVector& pp) {
61template <
typename MatrixType,
typename IndexVector>
62int coletree(
const MatrixType& mat, IndexVector& parent, IndexVector& firstRowElt,
63 typename MatrixType::StorageIndex* perm = 0) {
64 using StorageIndex =
typename MatrixType::StorageIndex;
65 StorageIndex nc = convert_index<StorageIndex>(mat.cols());
66 StorageIndex m = convert_index<StorageIndex>(mat.rows());
67 StorageIndex diagSize = (std::min)(nc, m);
72 parent.resize(mat.cols());
74 firstRowElt.resize(m);
75 firstRowElt.setConstant(nc);
76 firstRowElt.segment(0, diagSize).setLinSpaced(diagSize, 0, diagSize - 1);
78 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) {
83 firstRowElt(row) = (std::min)(firstRowElt(row), col);
90 StorageIndex rset, cset, rroot;
91 for (StorageIndex col = 0; col < nc; col++) {
92 found_diag = col >= m;
99 StorageIndex pcol = col;
100 if (perm) pcol = perm[col];
101 for (
typename MatrixType::InnerIterator it(mat, pcol); it || !found_diag;
104 if (it) i = it.index();
105 if (i == col) found_diag =
true;
107 StorageIndex row = firstRowElt(i);
108 if (row >= col)
continue;
109 rset = internal::etree_find(row, pp);
126template <
typename IndexVector>
127void nr_etdfs(
typename IndexVector::Scalar n, IndexVector& parent, IndexVector& first_kid, IndexVector& next_kid,
128 IndexVector& post,
typename IndexVector::Scalar postnum) {
129 using StorageIndex =
typename IndexVector::Scalar;
130 StorageIndex current = n, first, next;
131 while (postnum != n) {
132 first = first_kid(current);
137 post(current) = postnum++;
140 next = next_kid(current);
143 current = parent(current);
145 post(current) = postnum++;
148 next = next_kid(current);
151 if (postnum == n + 1)
return;
162enum class PostorderChildren { Increasing, Decreasing };
171template <
typename IndexVector>
172void treePostorder(
typename IndexVector::Scalar n, IndexVector& parent, IndexVector& post,
173 PostorderChildren order = PostorderChildren::Increasing) {
174 using StorageIndex =
typename IndexVector::Scalar;
175 IndexVector first_kid, next_kid;
176 StorageIndex postnum;
178 first_kid.resize(n + 1);
179 next_kid.setZero(n + 1);
183 first_kid.setConstant(-1);
184 const auto prependToParent = [&](StorageIndex v) {
185 StorageIndex dad = parent(v);
186 next_kid(v) = first_kid(dad);
189 if (order == PostorderChildren::Increasing) {
190 for (StorageIndex v = n - 1; v >= 0; v--) prependToParent(v);
192 for (StorageIndex v = 0; v < n; v++) prependToParent(v);
197 internal::nr_etdfs(n, parent, first_kid, next_kid, post, postnum);