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