1 /* ========================================================================= */
2 /* === AMD_post_tree ======================================================= */
3 /* ========================================================================= */
4
5 /* ------------------------------------------------------------------------- */
6 /* AMD, Copyright (c) Timothy A. Davis, */
7 /* Patrick R. Amestoy, and Iain S. Duff. See ../README.txt for License. */
8 /* email: DrTimothyAldenDavis@gmail.com */
9 /* ------------------------------------------------------------------------- */
10
11 /* Post-ordering of a supernodal elimination tree. */
12
13 #include "amd_internal.h"
14
AMD_post_tree(Int root,Int k,Int Child[],const Int Sibling[],Int Order[],Int Stack[],Int nn)15 GLOBAL Int AMD_post_tree
16 (
17 Int root, /* root of the tree */
18 Int k, /* start numbering at k */
19 Int Child [ ], /* input argument of size nn, undefined on
20 * output. Child [i] is the head of a link
21 * list of all nodes that are children of node
22 * i in the tree. */
23 const Int Sibling [ ], /* input argument of size nn, not modified.
24 * If f is a node in the link list of the
25 * children of node i, then Sibling [f] is the
26 * next child of node i.
27 */
28 Int Order [ ], /* output order, of size nn. Order [i] = k
29 * if node i is the kth node of the reordered
30 * tree. */
31 Int Stack [ ] /* workspace of size nn */
32 #ifndef NDEBUG
33 , Int nn /* nodes are in the range 0..nn-1. */
34 #endif
35 )
36 {
37 Int f, head, h, i ;
38
39 #if 0
40 /* --------------------------------------------------------------------- */
41 /* recursive version (Stack [ ] is not used): */
42 /* --------------------------------------------------------------------- */
43
44 /* this is simple, but can caouse stack overflow if nn is large */
45 i = root ;
46 for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
47 {
48 k = AMD_post_tree (f, k, Child, Sibling, Order, Stack, nn) ;
49 }
50 Order [i] = k++ ;
51 return (k) ;
52 #endif
53
54 /* --------------------------------------------------------------------- */
55 /* non-recursive version, using an explicit stack */
56 /* --------------------------------------------------------------------- */
57
58 /* push root on the stack */
59 head = 0 ;
60 Stack [0] = root ;
61
62 while (head >= 0)
63 {
64 /* get head of stack */
65 ASSERT (head < nn) ;
66 i = Stack [head] ;
67 AMD_DEBUG1 (("head of stack "ID" \n", i)) ;
68 ASSERT (i >= 0 && i < nn) ;
69
70 if (Child [i] != EMPTY)
71 {
72 /* the children of i are not yet ordered */
73 /* push each child onto the stack in reverse order */
74 /* so that small ones at the head of the list get popped first */
75 /* and the biggest one at the end of the list gets popped last */
76 for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
77 {
78 head++ ;
79 ASSERT (head < nn) ;
80 ASSERT (f >= 0 && f < nn) ;
81 }
82 h = head ;
83 ASSERT (head < nn) ;
84 for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
85 {
86 ASSERT (h > 0) ;
87 Stack [h--] = f ;
88 AMD_DEBUG1 (("push "ID" on stack\n", f)) ;
89 ASSERT (f >= 0 && f < nn) ;
90 }
91 ASSERT (Stack [h] == i) ;
92
93 /* delete child list so that i gets ordered next time we see it */
94 Child [i] = EMPTY ;
95 }
96 else
97 {
98 /* the children of i (if there were any) are already ordered */
99 /* remove i from the stack and order it. Front i is kth front */
100 head-- ;
101 AMD_DEBUG1 (("pop "ID" order "ID"\n", i, k)) ;
102 Order [i] = k++ ;
103 ASSERT (k <= nn) ;
104 }
105
106 #ifndef NDEBUG
107 AMD_DEBUG1 (("\nStack:")) ;
108 for (h = head ; h >= 0 ; h--)
109 {
110 Int j = Stack [h] ;
111 AMD_DEBUG1 ((" "ID, j)) ;
112 ASSERT (j >= 0 && j < nn) ;
113 }
114 AMD_DEBUG1 (("\n\n")) ;
115 ASSERT (head < nn) ;
116 #endif
117
118 }
119 return (k) ;
120 }
121