1 /* ========================================================================= */
2 /* === CAMD_postorder ====================================================== */
3 /* ========================================================================= */
4
5 /* ------------------------------------------------------------------------- */
6 /* CAMD, Copyright (c) Timothy A. Davis, Yanqing Chen, */
7 /* Patrick R. Amestoy, and Iain S. Duff. See ../README.txt for License. */
8 /* email: DrTimothyAldenDavis@gmail.com */
9 /* ------------------------------------------------------------------------- */
10
11 /* Perform a postordering (via depth-first search) of an assembly tree. */
12
13 #include "camd_internal.h"
14
CAMD_postorder(Int j,Int k,Int n,Int head[],Int next[],Int post[],Int stack[])15 GLOBAL Int CAMD_postorder
16 (
17 Int j, /* start at node j, a root of the assembly tree */
18 Int k, /* on input, next node is the kth node */
19 Int n, /* normal nodes 0 to n-1, place-holder node n */
20 Int head [], /* head of link list of children of each node */
21 Int next [], /* next[i] is the next child after i in link list */
22 Int post [], /* postordering, post [k] = p if p is the kth node */
23 Int stack [] /* recursion stack */
24 )
25 {
26 int i, p, top = 0 ;
27 stack [0] = j ; /* place j on the stack, maybe place-holder node n */
28 while (top >= 0) /* while (stack is not empty) */
29 {
30 p = stack [top] ; /* p = top of stack */
31 i = head [p] ; /* i = youngest child of p */
32 if (i == -1)
33 {
34 top-- ; /* p has no unordered children left */
35 if (p != n)
36 {
37 /* node p is the kth postordered node. Do not postorder the
38 * place-holder node n, which is the root of a subtree
39 * containing all dense and empty nodes. */
40 post [k++] = p ;
41 }
42 }
43 else
44 {
45 head [p] = next [i] ; /* remove i from children of p */
46 stack [++top] = i ; /* start dfs on child node i */
47 }
48 }
49 return (k) ;
50 }
51