EVSL  1.1.0 EigenValues Slicing Library
cs_etree.c
Go to the documentation of this file.
1 #include "cs.h"
2 /* compute the etree of A (using triu(A), or A'A without forming A'A */
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 }
#define cs
Definition: cs.h:637
CS_INT * cs_etree(const cs *A, CS_INT ata)
Definition: cs_etree.c:3
#define CS_CSC(A)
Definition: cs.h:659
#define CS_INT
Definition: cs.h:627
void * cs_malloc(CS_INT n, size_t size)
Definition: cs_malloc.c:10
CS_INT * cs_idone(CS_INT *p, cs *C, void *w, CS_INT ok)
Definition: cs_util.c:98