cs_dfs.c
Go to the documentation of this file.
00001 #include "cs.h"
00002 /* depth-first-search of the graph of a matrix, starting at node j */
00003 int cs_dfs (int j, cs *G, int top, int *xi, int *pstack, const int *pinv)
00004 {
00005     int i, p, p2, done, jnew, head = 0, *Gp, *Gi ;
00006     if (!CS_CSC (G) || !xi || !pstack) return (-1) ;    /* check inputs */
00007     Gp = G->p ; Gi = G->i ;
00008     xi [0] = j ;                /* initialize the recursion stack */
00009     while (head >= 0)
00010     {
00011         j = xi [head] ;         /* get j from the top of the recursion stack */
00012         jnew = pinv ? (pinv [j]) : j ;
00013         if (!CS_MARKED (Gp, j))
00014         {
00015             CS_MARK (Gp, j) ;       /* mark node j as visited */
00016             pstack [head] = (jnew < 0) ? 0 : CS_UNFLIP (Gp [jnew]) ;
00017         }
00018         done = 1 ;                  /* node j done if no unvisited neighbors */
00019         p2 = (jnew < 0) ? 0 : CS_UNFLIP (Gp [jnew+1]) ;
00020         for (p = pstack [head] ; p < p2 ; p++)  /* examine all neighbors of j */
00021         {
00022             i = Gi [p] ;            /* consider neighbor node i */
00023             if (CS_MARKED (Gp, i)) continue ;   /* skip visited node i */
00024             pstack [head] = p ;     /* pause depth-first search of node j */
00025             xi [++head] = i ;       /* start dfs at node i */
00026             done = 0 ;              /* node j is not done */
00027             break ;                 /* break, to start dfs (i) */
00028         }
00029         if (done)               /* depth-first search at node j is done */
00030         {
00031             head-- ;            /* remove j from the recursion stack */
00032             xi [--top] = j ;    /* and place in the output stack */
00033         }
00034     }
00035     return (top) ;
00036 }


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