22#ifndef EIGEN_SPARSE_AMD_H
23#define EIGEN_SPARSE_AMD_H
26#include "./InternalHeaderCheck.h"
33inline T amd_flip(
const T& i) {
38template <
typename StorageIndex>
39static StorageIndex cs_wclear(StorageIndex mark, StorageIndex lemax, StorageIndex* w, StorageIndex n) {
41 if (mark < 2 || (mark + lemax < 0)) {
42 for (k = 0; k < n; k++)
43 if (w[k] != 0) w[k] = 1;
50template <
typename StorageIndex>
51StorageIndex cs_tdfs(StorageIndex j, StorageIndex k, StorageIndex* head,
const StorageIndex* next, StorageIndex* post,
52 StorageIndex* stack) {
53 StorageIndex i, p, top = 0;
54 if (!head || !next || !post || !stack)
return (-1);
80template <
typename Scalar,
typename StorageIndex>
81void minimum_degree_ordering(SparseMatrix<Scalar, ColMajor, StorageIndex>& C,
82 PermutationMatrix<Dynamic, Dynamic, StorageIndex>& perm) {
83 StorageIndex d, dk, dext, lemax = 0, e, elenk, eln, i, j, k, k1, k2, k3, jlast, ln, dense, nzmax, mindeg = 0, nvi,
84 nvj, nvk, mark, wnvi, ok, nel = 0, p, p1, p2, p3, p4, pj, pk, pk1, pk2, pn, q, t, h;
87 using UnsignedIndex = std::make_unsigned_t<StorageIndex>;
90 StorageIndex n = StorageIndex(C.cols());
91 dense = std::max<StorageIndex>(16, StorageIndex(10 * numext::sqrt(
double(n))));
92 dense = (std::min)(n - 2, dense);
94 StorageIndex cnz = StorageIndex(C.nonZeros());
96 t = cnz + cnz / 5 + 2 * n;
100 ei_declare_aligned_stack_constructed_variable(StorageIndex, W, 8 * (n + 1), 0);
101 StorageIndex* len = W;
102 StorageIndex* nv = W + (n + 1);
103 StorageIndex* next = W + 2 * (n + 1);
104 StorageIndex* head = W + 3 * (n + 1);
105 StorageIndex* elen = W + 4 * (n + 1);
106 StorageIndex* degree = W + 5 * (n + 1);
107 StorageIndex* w = W + 6 * (n + 1);
108 StorageIndex* hhead = W + 7 * (n + 1);
109 StorageIndex* last = perm.indices().data();
112 StorageIndex* Cp = C.outerIndexPtr();
113 StorageIndex* Ci = C.innerIndexPtr();
114 for (k = 0; k < n; k++) len[k] = Cp[k + 1] - Cp[k];
118 for (i = 0; i <= n; i++) {
128 mark = internal::cs_wclear<StorageIndex>(0, 0, w, n);
131 for (i = 0; i < n; i++) {
132 bool has_diag =
false;
133 for (p = Cp[i]; p < Cp[i + 1]; ++p)
140 if (d == 1 && has_diag)
146 }
else if (d > dense || !has_diag)
154 if (head[d] != -1) last[head[d]] = i;
167 for (k = -1; mindeg < n && (k = head[mindeg]) == -1; mindeg++) {
169 if (next[k] != -1) last[next[k]] = -1;
170 head[mindeg] = next[k];
176 if (elenk > 0 && cnz + mindeg >= nzmax) {
177 for (j = 0; j < n; j++) {
185 for (q = 0, p = 0; p < cnz;)
187 j = amd_flip(Ci[p++]);
192 for (k3 = 0; k3 < len[j] - 1; k3++) Ci[q++] = Ci[p++];
202 pk1 = (elenk == 0) ? p : cnz;
204 for (k1 = 1; k1 <= elenk + 1; k1++) {
214 for (k2 = 1; k2 <= ln; k2++) {
217 if (nvi <= 0)
continue;
221 if (next[i] != -1) last[next[i]] = last[i];
224 next[last[i]] = next[i];
226 head[degree[i]] = next[i];
234 if (elenk != 0) cnz = pk2;
241 mark = internal::cs_wclear<StorageIndex>(mark, lemax, w, n);
242 for (pk = pk1; pk < pk2; pk++)
246 if (eln <= 0)
continue;
249 for (p = Cp[i]; p <= Cp[i] + eln - 1; p++)
254 }
else if (w[e] != 0)
256 w[e] = degree[e] + wnvi;
262 for (pk = pk1; pk < pk2; pk++)
266 p2 = p1 + elen[i] - 1;
268 for (hash = 0, d = 0, p = p1; p <= p2; p++)
277 hash += UnsignedIndex(e);
284 elen[i] = pn - p1 + 1;
287 for (p = p2 + 1; p < p4; p++)
291 if (nvj <= 0)
continue;
294 hash += UnsignedIndex(j);
306 degree[i] = std::min<StorageIndex>(degree[i], d);
310 len[i] = pn - p1 + 1;
311 h = StorageIndex(hash % UnsignedIndex(n));
318 lemax = std::max<StorageIndex>(lemax, dk);
319 mark = internal::cs_wclear<StorageIndex>(mark + lemax, lemax, w, n);
322 for (pk = pk1; pk < pk2; pk++) {
324 if (nv[i] >= 0)
continue;
328 for (; i != -1 && next[i] != -1; i = next[i], mark++) {
331 for (p = Cp[i] + 1; p <= Cp[i] + ln - 1; p++) w[Ci[p]] = mark;
333 for (j = next[i]; j != -1;)
335 ok = (len[j] == ln) && (elen[j] == eln);
336 for (p = Cp[j] + 1; ok && p <= Cp[j] + ln - 1; p++) {
337 if (w[Ci[p]] != mark) ok = 0;
356 for (p = pk1, pk = pk1; pk < pk2; pk++)
360 if (nvi <= 0)
continue;
362 d = degree[i] + dk - nvi;
363 d = std::min<StorageIndex>(d, n - nel - nvi);
364 if (head[d] != -1) last[head[d]] = i;
368 mindeg = std::min<StorageIndex>(mindeg, d);
379 if (elenk != 0) cnz = p;
383 for (i = 0; i < n; i++) Cp[i] = amd_flip(Cp[i]);
384 for (j = 0; j <= n; j++) head[j] = -1;
385 for (j = n; j >= 0; j--)
387 if (nv[j] > 0)
continue;
388 next[j] = head[Cp[j]];
391 for (e = n; e >= 0; e--)
393 if (nv[e] <= 0)
continue;
395 next[e] = head[Cp[e]];
399 for (k = 0, i = 0; i <= n; i++)
401 if (Cp[i] == -1) k = internal::cs_tdfs<StorageIndex>(i, k, head, next, perm.indices().data(), w);
404 perm.indices().conservativeResize(n);