Go to the documentation of this file.00001 #include "cs.h"
00002
00003 csd *cs_scc (cs *A)
00004 {
00005 int n, i, k, b, nb = 0, top, *xi, *pstack, *p, *r, *Ap, *ATp, *rcopy, *Blk ;
00006 cs *AT ;
00007 csd *D ;
00008 if (!CS_CSC (A)) return (NULL) ;
00009 n = A->n ; Ap = A->p ;
00010 D = cs_dalloc (n, 0) ;
00011 AT = cs_transpose (A, 0) ;
00012 xi = cs_malloc (2*n+1, sizeof (int)) ;
00013 if (!D || !AT || !xi) return (cs_ddone (D, AT, xi, 0)) ;
00014 Blk = xi ; rcopy = pstack = xi + n ;
00015 p = D->p ; r = D->r ; ATp = AT->p ;
00016 top = n ;
00017 for (i = 0 ; i < n ; i++)
00018 {
00019 if (!CS_MARKED (Ap, i)) top = cs_dfs (i, A, top, xi, pstack, NULL) ;
00020 }
00021 for (i = 0 ; i < n ; i++) CS_MARK (Ap, i) ;
00022 top = n ;
00023 nb = n ;
00024 for (k = 0 ; k < n ; k++)
00025 {
00026 i = xi [k] ;
00027 if (CS_MARKED (ATp, i)) continue ;
00028 r [nb--] = top ;
00029 top = cs_dfs (i, AT, top, p, pstack, NULL) ;
00030 }
00031 r [nb] = 0 ;
00032 for (k = nb ; k <= n ; k++) r [k-nb] = r [k] ;
00033 D->nb = nb = n-nb ;
00034 for (b = 0 ; b < nb ; b++)
00035 {
00036 for (k = r [b] ; k < r [b+1] ; k++) Blk [p [k]] = b ;
00037 }
00038 for (b = 0 ; b <= nb ; b++) rcopy [b] = r [b] ;
00039 for (i = 0 ; i < n ; i++) p [rcopy [Blk [i]]++] = i ;
00040 return (cs_ddone (D, AT, xi, 1)) ;
00041 }