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
36
37
38
39
|
// CXSparse/Source/cs_dfs: depth-first search
// CXSparse, Copyright (c) 2006-2022, Timothy A. Davis. All Rights Reserved.
// SPDX-License-Identifier: LGPL-2.1+
#include "cs.h"
/* depth-first-search of the graph of a matrix, starting at node j */
CS_INT cs_dfs (CS_INT j, cs *G, CS_INT top, CS_INT *xi, CS_INT *pstack, const CS_INT *pinv)
{
CS_INT i, p, p2, done, jnew, head = 0, *Gp, *Gi ;
if (!CS_CSC (G) || !xi || !pstack) return (-1) ; /* check inputs */
Gp = G->p ; Gi = G->i ;
xi [0] = j ; /* initialize the recursion stack */
while (head >= 0)
{
j = xi [head] ; /* get j from the top of the recursion stack */
jnew = pinv ? (pinv [j]) : j ;
if (!CS_MARKED (Gp, j))
{
CS_MARK (Gp, j) ; /* mark node j as visited */
pstack [head] = (jnew < 0) ? 0 : CS_UNFLIP (Gp [jnew]) ;
}
done = 1 ; /* node j done if no unvisited neighbors */
p2 = (jnew < 0) ? 0 : CS_UNFLIP (Gp [jnew+1]) ;
for (p = pstack [head] ; p < p2 ; p++) /* examine all neighbors of j */
{
i = Gi [p] ; /* consider neighbor node i */
if (CS_MARKED (Gp, i)) continue ; /* skip visited node i */
pstack [head] = p ; /* pause depth-first search of node j */
xi [++head] = i ; /* start dfs at node i */
done = 0 ; /* node j is not done */
break ; /* break, to start dfs (i) */
}
if (done) /* depth-first search at node j is done */
{
head-- ; /* remove j from the recursion stack */
xi [--top] = j ; /* and place in the output stack */
}
}
return (top) ;
}
|
