1 #include "cs.h"
2 /* compute the etree of A (using triu(A), or A'A without forming A'A */
cs_etree(const cs * A,CS_INT ata)3 CS_INT *cs_etree (const cs *A, CS_INT ata)
4 {
5 CS_INT i, k, p, m, n, inext, *Ap, *Ai, *w, *parent, *ancestor, *prev ;
6 if (!CS_CSC (A)) return (NULL) ; /* check inputs */
7 m = A->m ; n = A->n ; Ap = A->p ; Ai = A->i ;
8 parent = cs_malloc (n, sizeof (CS_INT)) ; /* allocate result */
9 w = cs_malloc (n + (ata ? m : 0), sizeof (CS_INT)) ; /* get workspace */
10 if (!w || !parent) return (cs_idone (parent, NULL, w, 0)) ;
11 ancestor = w ; prev = w + n ;
12 if (ata) for (i = 0 ; i < m ; i++) prev [i] = -1 ;
13 for (k = 0 ; k < n ; k++)
14 {
15 parent [k] = -1 ; /* node k has no parent yet */
16 ancestor [k] = -1 ; /* nor does k have an ancestor */
17 for (p = Ap [k] ; p < Ap [k+1] ; p++)
18 {
19 i = ata ? (prev [Ai [p]]) : (Ai [p]) ;
20 for ( ; i != -1 && i < k ; i = inext) /* traverse from i to k */
21 {
22 inext = ancestor [i] ; /* inext = ancestor of i */
23 ancestor [i] = k ; /* path compression */
24 if (inext == -1) parent [i] = k ; /* no anc., parent is k */
25 }
26 if (ata) prev [Ai [p]] = k ;
27 }
28 }
29 return (cs_idone (parent, NULL, w, 1)) ;
30 }
31