cs_etree.c
Go to the documentation of this file.
00001 #include "cs.h"
00002 /* compute the etree of A (using triu(A), or A'A without forming A'A */
00003 int *cs_etree (const cs *A, int ata)
00004 {
00005     int i, k, p, m, n, inext, *Ap, *Ai, *w, *parent, *ancestor, *prev ;
00006     if (!CS_CSC (A)) return (NULL) ;        /* check inputs */
00007     m = A->m ; n = A->n ; Ap = A->p ; Ai = A->i ;
00008     parent = cs_malloc (n, sizeof (int)) ;              /* allocate result */
00009     w = cs_malloc (n + (ata ? m : 0), sizeof (int)) ;   /* get workspace */
00010     if (!w || !parent) return (cs_idone (parent, NULL, w, 0)) ;
00011     ancestor = w ; prev = w + n ;
00012     if (ata) for (i = 0 ; i < m ; i++) prev [i] = -1 ;
00013     for (k = 0 ; k < n ; k++)
00014     {
00015         parent [k] = -1 ;                   /* node k has no parent yet */
00016         ancestor [k] = -1 ;                 /* nor does k have an ancestor */
00017         for (p = Ap [k] ; p < Ap [k+1] ; p++)
00018         {
00019             i = ata ? (prev [Ai [p]]) : (Ai [p]) ;
00020             for ( ; i != -1 && i < k ; i = inext)   /* traverse from i to k */
00021             {
00022                 inext = ancestor [i] ;              /* inext = ancestor of i */
00023                 ancestor [i] = k ;                  /* path compression */
00024                 if (inext == -1) parent [i] = k ;   /* no anc., parent is k */
00025             }
00026             if (ata) prev [Ai [p]] = k ;
00027         }
00028     }
00029     return (cs_idone (parent, NULL, w, 1)) ;
00030 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines


hogman_minimal
Author(s): Maintained by Juergen Sturm
autogenerated on Wed Dec 26 2012 15:36:47