cs_scc.c
Go to the documentation of this file.
00001 #include "cs.h"
00002 /* find the strongly connected components of a square matrix */
00003 csd *cs_scc (cs *A)     /* matrix A temporarily modified, then restored */
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) ;                /* check inputs */
00009     n = A->n ; Ap = A->p ;
00010     D = cs_dalloc (n, 0) ;                          /* allocate result */
00011     AT = cs_transpose (A, 0) ;                      /* AT = A' */
00012     xi = cs_malloc (2*n+1, sizeof (int)) ;          /* get workspace */
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++)   /* first dfs(A) to find finish times (xi) */
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) ; /* restore A; unmark all nodes*/
00022     top = n ;
00023     nb = n ;
00024     for (k = 0 ; k < n ; k++)   /* dfs(A') to find strongly connnected comp */
00025     {
00026         i = xi [k] ;            /* get i in reverse order of finish times */
00027         if (CS_MARKED (ATp, i)) continue ;  /* skip node i if already ordered */
00028         r [nb--] = top ;        /* node i is the start of a component in p */
00029         top = cs_dfs (i, AT, top, p, pstack, NULL) ;
00030     }
00031     r [nb] = 0 ;                /* first block starts at zero; shift r up */
00032     for (k = nb ; k <= n ; k++) r [k-nb] = r [k] ;
00033     D->nb = nb = n-nb ;         /* nb = # of strongly connected components */
00034     for (b = 0 ; b < nb ; b++)  /* sort each block in natural order */
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 }


hogman_minimal
Author(s): Maintained by Juergen Sturm
autogenerated on Mon Oct 6 2014 00:06:58