EVSL  1.1.0 EigenValues Slicing Library
cs_scc.c
Go to the documentation of this file.
1 #include "cs.h"
2 /* find the strongly connected components of a square matrix */
3 csd *cs_scc (cs *A) /* matrix A temporarily modified, then restored */
4 {
5  CS_INT n, i, k, b, nb = 0, top, *xi, *pstack, *p, *r, *Ap, *ATp, *rcopy, *Blk ;
6  cs *AT ;
7  csd *D ;
8  if (!CS_CSC (A)) return (NULL) ; /* check inputs */
9  n = A->n ; Ap = A->p ;
10  D = cs_dalloc (n, 0) ; /* allocate result */
11  AT = cs_transpose (A, 0) ; /* AT = A' */
12  xi = cs_malloc (2*n+1, sizeof (CS_INT)) ; /* get workspace */
13  if (!D || !AT || !xi) return (cs_ddone (D, AT, xi, 0)) ;
14  Blk = xi ; rcopy = pstack = xi + n ;
15  p = D->p ; r = D->r ; ATp = AT->p ;
16  top = n ;
17  for (i = 0 ; i < n ; i++) /* first dfs(A) to find finish times (xi) */
18  {
19  if (!CS_MARKED (Ap, i)) top = cs_dfs (i, A, top, xi, pstack, NULL) ;
20  }
21  for (i = 0 ; i < n ; i++) CS_MARK (Ap, i) ; /* restore A; unmark all nodes*/
22  top = n ;
23  nb = n ;
24  for (k = 0 ; k < n ; k++) /* dfs(A') to find strongly connnected comp */
25  {
26  i = xi [k] ; /* get i in reverse order of finish times */
27  if (CS_MARKED (ATp, i)) continue ; /* skip node i if already ordered */
28  r [nb--] = top ; /* node i is the start of a component in p */
29  top = cs_dfs (i, AT, top, p, pstack, NULL) ;
30  }
31  r [nb] = 0 ; /* first block starts at zero; shift r up */
32  for (k = nb ; k <= n ; k++) r [k-nb] = r [k] ;
33  D->nb = nb = n-nb ; /* nb = # of strongly connected components */
34  for (b = 0 ; b < nb ; b++) /* sort each block in natural order */
35  {
36  for (k = r [b] ; k < r [b+1] ; k++) Blk [p [k]] = b ;
37  }
38  for (b = 0 ; b <= nb ; b++) rcopy [b] = r [b] ;
39  for (i = 0 ; i < n ; i++) p [rcopy [Blk [i]]++] = i ;
40  return (cs_ddone (D, AT, xi, 1)) ;
41 }
csd * cs_scc(cs *A)
Definition: cs_scc.c:3
#define CS_MARKED(w, j)
Definition: cs.h:657
#define cs
Definition: cs.h:637
#define CS_MARK(w, j)
Definition: cs.h:658
CS_INT cs_dfs(CS_INT j, cs *G, CS_INT top, CS_INT *xi, CS_INT *pstack, const CS_INT *pinv)
Definition: cs_dfs.c:3
#define csd
Definition: cs.h:690
#define CS_CSC(A)
Definition: cs.h:659
cs * cs_transpose(const cs *A, CS_INT values)
Definition: cs_transpose.c:3
#define CS_INT
Definition: cs.h:627
csd * cs_dalloc(CS_INT m, CS_INT n)
Definition: cs_util.c:66
void * cs_malloc(CS_INT n, size_t size)
Definition: cs_malloc.c:10
csd * cs_ddone(csd *D, cs *C, void *w, CS_INT ok)
Definition: cs_util.c:115