EVSL  1.1.0
EigenValues Slicing Library
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros
cs_dfs.c
Go to the documentation of this file.
1 #include "cs.h"
2 /* depth-first-search of the graph of a matrix, starting at node j */
3 CS_INT cs_dfs (CS_INT j, cs *G, CS_INT top, CS_INT *xi, CS_INT *pstack, const CS_INT *pinv)
4 {
5  CS_INT i, p, p2, done, jnew, head = 0, *Gp, *Gi ;
6  if (!CS_CSC (G) || !xi || !pstack) return (-1) ; /* check inputs */
7  Gp = G->p ; Gi = G->i ;
8  xi [0] = j ; /* initialize the recursion stack */
9  while (head >= 0)
10  {
11  j = xi [head] ; /* get j from the top of the recursion stack */
12  jnew = pinv ? (pinv [j]) : j ;
13  if (!CS_MARKED (Gp, j))
14  {
15  CS_MARK (Gp, j) ; /* mark node j as visited */
16  pstack [head] = (jnew < 0) ? 0 : CS_UNFLIP (Gp [jnew]) ;
17  }
18  done = 1 ; /* node j done if no unvisited neighbors */
19  p2 = (jnew < 0) ? 0 : CS_UNFLIP (Gp [jnew+1]) ;
20  for (p = pstack [head] ; p < p2 ; p++) /* examine all neighbors of j */
21  {
22  i = Gi [p] ; /* consider neighbor node i */
23  if (CS_MARKED (Gp, i)) continue ; /* skip visited node i */
24  pstack [head] = p ; /* pause depth-first search of node j */
25  xi [++head] = i ; /* start dfs at node i */
26  done = 0 ; /* node j is not done */
27  break ; /* break, to start dfs (i) */
28  }
29  if (done) /* depth-first search at node j is done */
30  {
31  head-- ; /* remove j from the recursion stack */
32  xi [--top] = j ; /* and place in the output stack */
33  }
34  }
35  return (top) ;
36 }
#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 CS_UNFLIP(i)
Definition: cs.h:656
#define CS_CSC(A)
Definition: cs.h:659
#define CS_INT
Definition: cs.h:627