25 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
38 template<typename T> inline T amd_flip(const T& i) { return -i-2; }  in amd_flip()
55   return (mark);     /* at this point, w[0..n-1] < mark holds */  in cs_wclear()
58 /* depth-first search and postorder of a tree rooted at node j */
63   if(!head || !next || !post || !stack) return (-1);    /* check inputs */  in cs_tdfs()
69     if(i == -1)  in cs_tdfs()
71       top--;                 /* p has no unordered children left */  in cs_tdfs()
89   * \param[out] perm the permutation P reducing the fill-in of the input matrix \a C
104   dense = (std::min)(n-2, dense);  in minimum_degree_ordering()
114   StorageIndex* nv      = W +   (n+1);  in minimum_degree_ordering()  local
123   /* --- Initialize quotient graph ---------------------------------------- */  in minimum_degree_ordering()
127     len[k] = Cp[k+1] - Cp[k];  in minimum_degree_ordering()
133     head[i]   = -1;                     // degree list i is empty  in minimum_degree_ordering()
134     last[i]   = -1;  in minimum_degree_ordering()
135     next[i]   = -1;  in minimum_degree_ordering()
136     hhead[i]  = -1;                     // hash list i is empty   in minimum_degree_ordering()
137     nv[i]     = 1;                      // node i is just one node  in minimum_degree_ordering()
144   /* --- Initialize degree lists ------------------------------------------ */  in minimum_degree_ordering()
158       elen[i] = -2;                 /* element i is dead */  in minimum_degree_ordering()
160       Cp[i] = -1;                   /* i is a root of assembly tree */  in minimum_degree_ordering()
165       nv[i] = 0;                    /* absorb i into element n */  in minimum_degree_ordering()
166       elen[i] = -1;                 /* node i is dead */  in minimum_degree_ordering()
169       nv[n]++;  in minimum_degree_ordering()
173       if(head[d] != -1) last[head[d]] = i;  in minimum_degree_ordering()
179   elen[n] = -2;                         /* n is a dead element */  in minimum_degree_ordering()
180   Cp[n] = -1;                           /* n is a root of assembly tree */  in minimum_degree_ordering()
185     /* --- Select node of minimum approximate degree -------------------- */  in minimum_degree_ordering()
186     for(k = -1; mindeg < n && (k = head[mindeg]) == -1; mindeg++) {}  in minimum_degree_ordering()
187     if(next[k] != -1) last[next[k]] = -1;  in minimum_degree_ordering()
190     nvk = nv[k];                      /* # of nodes k represents */  in minimum_degree_ordering()
191     nel += nvk;                        /* nv[k] nodes of A eliminated */  in minimum_degree_ordering()
193     /* --- Garbage collection ------------------------------------------- */  in minimum_degree_ordering()
210           for(k3 = 0; k3 < len[j]-1; k3++) Ci[q++] = Ci[p++];  in minimum_degree_ordering()
213       cnz = q;                       /* Ci[cnz...nzmax-1] now free */  in minimum_degree_ordering()
216     /* --- Construct new element ---------------------------------------- */  in minimum_degree_ordering()
218     nv[k] = -nvk;                     /* flag k as in Lk */  in minimum_degree_ordering()
228         ln = len[k] - elenk;      /* length of list of nodes in k */  in minimum_degree_ordering()
239         if((nvi = nv[i]) <= 0) continue; /* node i dead, or seen */  in minimum_degree_ordering()
241         nv[i] = -nvi;             /* negate nv[i] to denote i in Lk*/  in minimum_degree_ordering()
243         if(next[i] != -1) last[next[i]] = last[i];  in minimum_degree_ordering()
244         if(last[i] != -1)         /* remove i from degree list */  in minimum_degree_ordering()
260     degree[k] = dk;                   /* external degree of k - |Lk\i| */  in minimum_degree_ordering()
261     Cp[k] = pk1;                      /* element k is in Ci[pk1..pk2-1] */  in minimum_degree_ordering()
262     len[k] = pk2 - pk1;  in minimum_degree_ordering()
263     elen[k] = -2;                     /* k is now an element */  in minimum_degree_ordering()
265     /* --- Find set differences ----------------------------------------- */  in minimum_degree_ordering()
271       nvi = -nv[i];                      /* nv[i] was negated */  in minimum_degree_ordering()
272       wnvi = mark - nvi;  in minimum_degree_ordering()
273       for(p = Cp[i]; p <= Cp[i] + eln - 1; p++)  /* scan Ei */  in minimum_degree_ordering()
278           w[e] -= nvi;          /* decrement |Le\Lk| */  in minimum_degree_ordering()
287     /* --- Degree update ------------------------------------------------ */  in minimum_degree_ordering()
292       p2 = p1 + elen[i] - 1;  in minimum_degree_ordering()
299           dext = w[e] - mark;   /* dext = |Le\Lk| */  in minimum_degree_ordering()
308             Cp[e] = amd_flip (k);  /* aggressive absorb. e->k */  in minimum_degree_ordering()
313       elen[i] = pn - p1 + 1;        /* elen[i] = |Ei| */  in minimum_degree_ordering()
319         if((nvj = nv[j]) <= 0) continue; /* node j dead or in Lk */  in minimum_degree_ordering()
327         nvi = -nv[i];  in minimum_degree_ordering()
328         dk -= nvi;                 /* |Lk| -= |i| */  in minimum_degree_ordering()
329         nvk += nvi;                /* |k| += nv[i] */  in minimum_degree_ordering()
331         nv[i] = 0;  in minimum_degree_ordering()
332         elen[i] = -1;             /* node i is dead */  in minimum_degree_ordering()
340         len[i] = pn - p1 + 1;     /* new len of adj. list of node i */  in minimum_degree_ordering()
351     /* --- Supernode detection ------------------------------------------ */  in minimum_degree_ordering()
355       if(nv[i] >= 0) continue;         /* skip if i is dead */  in minimum_degree_ordering()
358       hhead[h] = -1;                    /* hash bucket will be empty */  in minimum_degree_ordering()
359       for(; i != -1 && next[i] != -1; i = next[i], mark++)  in minimum_degree_ordering()
363         for(p = Cp[i]+1; p <= Cp[i] + ln-1; p++) w[Ci[p]] = mark;  in minimum_degree_ordering()
365         for(j = next[i]; j != -1; ) /* compare i with all j */  in minimum_degree_ordering()
368           for(p = Cp[j] + 1; ok && p <= Cp[j] + ln - 1; p++)  in minimum_degree_ordering()
375             nv[i] += nv[j];  in minimum_degree_ordering()
376             nv[j] = 0;  in minimum_degree_ordering()
377             elen[j] = -1;         /* node j is dead */  in minimum_degree_ordering()
390     /* --- Finalize new element------------------------------------------ */  in minimum_degree_ordering()
394       if((nvi = -nv[i]) <= 0) continue;/* skip if i is dead */  in minimum_degree_ordering()
395       nv[i] = nvi;                      /* restore nv[i] */  in minimum_degree_ordering()
396       d = degree[i] + dk - nvi;         /* compute external degree(i) */  in minimum_degree_ordering()
397       d = std::min<StorageIndex> (d, n - nel - nvi);  in minimum_degree_ordering()
398       if(head[d] != -1) last[head[d]] = i;  in minimum_degree_ordering()
400       last[i] = -1;  in minimum_degree_ordering()
406     nv[k] = nvk;                      /* # nodes absorbed into k */  in minimum_degree_ordering()
407     if((len[k] = p-pk1) == 0)         /* length of adj list of element k*/  in minimum_degree_ordering()
409       Cp[k] = -1;                   /* k is a root of the tree */  in minimum_degree_ordering()
415   /* --- Postordering ----------------------------------------------------- */  in minimum_degree_ordering()
417   for(j = 0; j <= n; j++) head[j] = -1;  in minimum_degree_ordering()
418   for(j = n; j >= 0; j--)              /* place unordered nodes in lists */  in minimum_degree_ordering()
420     if(nv[j] > 0) continue;          /* skip if j is an element */  in minimum_degree_ordering()
424   for(e = n; e >= 0; e--)              /* place elements in lists */  in minimum_degree_ordering()
426     if(nv[e] <= 0) continue;         /* skip unless e is an element */  in minimum_degree_ordering()
427     if(Cp[e] != -1)  in minimum_degree_ordering()
435     if(Cp[i] == -1) k = internal::cs_tdfs<StorageIndex>(i, k, head, next, perm.indices().data(), w);  in minimum_degree_ordering()