← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/suitesparse/oneiric

« back to all changes in this revision

Viewing changes to CSparse/Source/cs_dfs.c

  • Committer: Bazaar Package Importer
  • Author(s): Nick Ellery
  • Date: 2009-06-14 19:15:52 UTC
  • mfrom: (7.2.2 sid)
  • Revision ID: james.westby@ubuntu.com-20090614191552-2hliya5q8n1quseu
Tags: 1:3.4.0-1ubuntu1
https://launchpad.net/bugs/387137
* Merge from debian unstable, remaining changes (LP: #387137):
  - debian/control:
    - demote libatlas-doc from recommends to suggests as it is not in main
    - drop recommends on doc-central as it is not in main

Show diffs side-by-side

added added

removed removed

Lines of Context:
CSparse/Source/cs_dfs.c
3
3
int cs_dfs (int j, cs *G, int top, int *xi, int *pstack, const int *pinv)
4
4
{
5
5
    int i, p, p2, done, jnew, head = 0, *Gp, *Gi ;
6
 
    if (!CS_CSC (G) || !xi || !pstack) return (-1) ;    /* check inputs */
 
6
    if (!CS_CSC (G) || !xi || !pstack) return (-1) ;    /* check inputs */
7
7
    Gp = G->p ; Gi = G->i ;
8
 
    xi [0] = j ;                /* initialize the recursion stack */
 
8
    xi [0] = j ;                /* initialize the recursion stack */
9
9
    while (head >= 0)
10
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
 
        }
 
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
34
    }
35
35
    return (top) ;
36
36
}