1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include "cs.h"
/* find the strongly connected components of a square matrix */
csd *cs_scc (cs *A) /* matrix A temporarily modified, then restored */
{
int n, i, k, b = 0, top, *xi, *pstack, *P, *R, *Ap, *ATp ;
cs *AT ;
csd *D ;
if (!A) return (NULL) ;
n = A->n ; Ap = A->p ;
D = cs_dalloc (n, 0) ;
AT = cs_transpose (A, 0) ; /* AT = A' */
xi = cs_malloc (2*n, sizeof (int)) ; /* allocate workspace */
pstack = xi + n ;
if (!D || !AT || !xi) return (cs_ddone (D, AT, xi, 0)) ;
P = D->P ; R = D->R ; ATp = AT->p ;
top = n ;
for (i = 0 ; i < n ; i++) /* first dfs(A) to find finish times (xi) */
{
if (!CS_MARKED (Ap,i)) top = cs_dfs (i, A, top, xi, pstack, NULL) ;
}
for (i = 0 ; i < n ; i++) CS_MARK (Ap, i) ; /* restore A; unmark all nodes*/
top = n ;
b = n ;
for (k = 0 ; k < n ; k++) /* dfs(A') to find strongly connnected comp. */
{
i = xi [k] ; /* get i in reverse order of finish times */
if (CS_MARKED (ATp,i)) continue ; /* skip node i if already ordered */
R [b--] = top ; /* node i is the start of a component in P */
top = cs_dfs (i, AT, top, P, pstack, NULL) ;
}
R [b] = 0 ; /* first block starts at zero; shift R up */
for (k = b ; k <= n ; k++) R [k-b] = R [k] ;
D->nb = R [n+1] = b = n-b ; /* b = # of strongly connected components */
return (cs_ddone (D, AT, xi, 1)) ;
}
|
