Coverage Report

Created: 2023-09-25 06:05

/src/igraph/vendor/cs/cs_dfs.c
Line
Count
Source (jump to first uncovered line)
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
0
{
5
0
    CS_INT i, p, p2, done, jnew, head = 0, *Gp, *Gi ;
6
0
    if (!CS_CSC (G) || !xi || !pstack) return (-1) ;    /* check inputs */
7
0
    Gp = G->p ; Gi = G->i ;
8
0
    xi [0] = j ;                /* initialize the recursion stack */
9
0
    while (head >= 0)
10
0
    {
11
0
        j = xi [head] ;         /* get j from the top of the recursion stack */
12
0
        jnew = pinv ? (pinv [j]) : j ;
13
0
        if (!CS_MARKED (Gp, j))
14
0
        {
15
0
            CS_MARK (Gp, j) ;       /* mark node j as visited */
16
0
            pstack [head] = (jnew < 0) ? 0 : CS_UNFLIP (Gp [jnew]) ;
17
0
        }
18
0
        done = 1 ;                  /* node j done if no unvisited neighbors */
19
0
        p2 = (jnew < 0) ? 0 : CS_UNFLIP (Gp [jnew+1]) ;
20
0
        for (p = pstack [head] ; p < p2 ; p++)  /* examine all neighbors of j */
21
0
        {
22
0
            i = Gi [p] ;            /* consider neighbor node i */
23
0
            if (CS_MARKED (Gp, i)) continue ;   /* skip visited node i */
24
0
            pstack [head] = p ;     /* pause depth-first search of node j */
25
0
            xi [++head] = i ;       /* start dfs at node i */
26
0
            done = 0 ;              /* node j is not done */
27
0
            break ;                 /* break, to start dfs (i) */
28
0
        }
29
0
        if (done)               /* depth-first search at node j is done */
30
0
        {
31
0
            head-- ;            /* remove j from the recursion stack */
32
0
            xi [--top] = j ;    /* and place in the output stack */
33
0
        }
34
0
    }
35
0
    return (top) ;
36
0
}