/src/igraph/vendor/cs/cs_tdfs.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "cs.h" |
2 | | /* depth-first search and postorder of a tree rooted at node j */ |
3 | | CS_INT cs_tdfs (CS_INT j, CS_INT k, CS_INT *head, const CS_INT *next, CS_INT *post, CS_INT *stack) |
4 | 0 | { |
5 | 0 | CS_INT i, p, top = 0 ; |
6 | 0 | if (!head || !next || !post || !stack) return (-1) ; /* check inputs */ |
7 | 0 | stack [0] = j ; /* place j on the stack */ |
8 | 0 | while (top >= 0) /* while (stack is not empty) */ |
9 | 0 | { |
10 | 0 | p = stack [top] ; /* p = top of stack */ |
11 | 0 | i = head [p] ; /* i = youngest child of p */ |
12 | 0 | if (i == -1) |
13 | 0 | { |
14 | 0 | top-- ; /* p has no unordered children left */ |
15 | 0 | post [k++] = p ; /* node p is the kth postordered node */ |
16 | 0 | } |
17 | 0 | else |
18 | 0 | { |
19 | 0 | head [p] = next [i] ; /* remove i from children of p */ |
20 | 0 | stack [++top] = i ; /* start dfs on child node i */ |
21 | 0 | } |
22 | 0 | } |
23 | 0 | return (k) ; |
24 | 0 | } |