|
1 /* ========================================================================= */ |
|
2 /* === AMD_postorder ======================================================= */ |
|
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 /* Perform a postordering (via depth-first search) of an assembly tree. */ |
|
13 |
|
14 #include "amd_internal.h" |
|
15 |
|
16 GLOBAL void AMD_postorder |
|
17 ( |
|
18 /* inputs, not modified on output: */ |
|
19 Int nn, /* nodes are in the range 0..nn-1 */ |
|
20 Int Parent [ ], /* Parent [j] is the parent of j, or EMPTY if root */ |
|
21 Int Nv [ ], /* Nv [j] > 0 number of pivots represented by node j, |
|
22 * or zero if j is not a node. */ |
|
23 Int Fsize [ ], /* Fsize [j]: size of node j */ |
|
24 |
|
25 /* output, not defined on input: */ |
|
26 Int Order [ ], /* output post-order */ |
|
27 |
|
28 /* workspaces of size nn: */ |
|
29 Int Child [ ], |
|
30 Int Sibling [ ], |
|
31 Int Stack [ ] |
|
32 ) |
|
33 { |
|
34 Int i, j, k, parent, frsize, f, fprev, maxfrsize, bigfprev, bigf, fnext ; |
|
35 |
|
36 for (j = 0 ; j < nn ; j++) |
|
37 { |
|
38 Child [j] = EMPTY ; |
|
39 Sibling [j] = EMPTY ; |
|
40 } |
|
41 |
|
42 /* --------------------------------------------------------------------- */ |
|
43 /* place the children in link lists - bigger elements tend to be last */ |
|
44 /* --------------------------------------------------------------------- */ |
|
45 |
|
46 for (j = nn-1 ; j >= 0 ; j--) |
|
47 { |
|
48 if (Nv [j] > 0) |
|
49 { |
|
50 /* this is an element */ |
|
51 parent = Parent [j] ; |
|
52 if (parent != EMPTY) |
|
53 { |
|
54 /* place the element in link list of the children its parent */ |
|
55 /* bigger elements will tend to be at the end of the list */ |
|
56 Sibling [j] = Child [parent] ; |
|
57 Child [parent] = j ; |
|
58 } |
|
59 } |
|
60 } |
|
61 |
|
62 #ifndef NDEBUG |
|
63 { |
|
64 Int nels, ff, nchild ; |
|
65 AMD_DEBUG1 (("\n\n================================ AMD_postorder:\n")); |
|
66 nels = 0 ; |
|
67 for (j = 0 ; j < nn ; j++) |
|
68 { |
|
69 if (Nv [j] > 0) |
|
70 { |
|
71 AMD_DEBUG1 (( ""ID" : nels "ID" npiv "ID" size "ID |
|
72 " parent "ID" maxfr "ID"\n", j, nels, |
|
73 Nv [j], Fsize [j], Parent [j], Fsize [j])) ; |
|
74 /* this is an element */ |
|
75 /* dump the link list of children */ |
|
76 nchild = 0 ; |
|
77 AMD_DEBUG1 ((" Children: ")) ; |
|
78 for (ff = Child [j] ; ff != EMPTY ; ff = Sibling [ff]) |
|
79 { |
|
80 AMD_DEBUG1 ((ID" ", ff)) ; |
|
81 ASSERT (Parent [ff] == j) ; |
|
82 nchild++ ; |
|
83 ASSERT (nchild < nn) ; |
|
84 } |
|
85 AMD_DEBUG1 (("\n")) ; |
|
86 parent = Parent [j] ; |
|
87 if (parent != EMPTY) |
|
88 { |
|
89 ASSERT (Nv [parent] > 0) ; |
|
90 } |
|
91 nels++ ; |
|
92 } |
|
93 } |
|
94 } |
|
95 AMD_DEBUG1 (("\n\nGo through the children of each node, and put\n" |
|
96 "the biggest child last in each list:\n")) ; |
|
97 #endif |
|
98 |
|
99 /* --------------------------------------------------------------------- */ |
|
100 /* place the largest child last in the list of children for each node */ |
|
101 /* --------------------------------------------------------------------- */ |
|
102 |
|
103 for (i = 0 ; i < nn ; i++) |
|
104 { |
|
105 if (Nv [i] > 0 && Child [i] != EMPTY) |
|
106 { |
|
107 |
|
108 #ifndef NDEBUG |
|
109 Int nchild ; |
|
110 AMD_DEBUG1 (("Before partial sort, element "ID"\n", i)) ; |
|
111 nchild = 0 ; |
|
112 for (f = Child [i] ; f != EMPTY ; f = Sibling [f]) |
|
113 { |
|
114 ASSERT (f >= 0 && f < nn) ; |
|
115 AMD_DEBUG1 ((" f: "ID" size: "ID"\n", f, Fsize [f])) ; |
|
116 nchild++ ; |
|
117 ASSERT (nchild <= nn) ; |
|
118 } |
|
119 #endif |
|
120 |
|
121 /* find the biggest element in the child list */ |
|
122 fprev = EMPTY ; |
|
123 maxfrsize = EMPTY ; |
|
124 bigfprev = EMPTY ; |
|
125 bigf = EMPTY ; |
|
126 for (f = Child [i] ; f != EMPTY ; f = Sibling [f]) |
|
127 { |
|
128 ASSERT (f >= 0 && f < nn) ; |
|
129 frsize = Fsize [f] ; |
|
130 if (frsize >= maxfrsize) |
|
131 { |
|
132 /* this is the biggest seen so far */ |
|
133 maxfrsize = frsize ; |
|
134 bigfprev = fprev ; |
|
135 bigf = f ; |
|
136 } |
|
137 fprev = f ; |
|
138 } |
|
139 ASSERT (bigf != EMPTY) ; |
|
140 |
|
141 fnext = Sibling [bigf] ; |
|
142 |
|
143 AMD_DEBUG1 (("bigf "ID" maxfrsize "ID" bigfprev "ID" fnext "ID |
|
144 " fprev " ID"\n", bigf, maxfrsize, bigfprev, fnext, fprev)) ; |
|
145 |
|
146 if (fnext != EMPTY) |
|
147 { |
|
148 /* if fnext is EMPTY then bigf is already at the end of list */ |
|
149 |
|
150 if (bigfprev == EMPTY) |
|
151 { |
|
152 /* delete bigf from the element of the list */ |
|
153 Child [i] = fnext ; |
|
154 } |
|
155 else |
|
156 { |
|
157 /* delete bigf from the middle of the list */ |
|
158 Sibling [bigfprev] = fnext ; |
|
159 } |
|
160 |
|
161 /* put bigf at the end of the list */ |
|
162 Sibling [bigf] = EMPTY ; |
|
163 ASSERT (Child [i] != EMPTY) ; |
|
164 ASSERT (fprev != bigf) ; |
|
165 ASSERT (fprev != EMPTY) ; |
|
166 Sibling [fprev] = bigf ; |
|
167 } |
|
168 |
|
169 #ifndef NDEBUG |
|
170 AMD_DEBUG1 (("After partial sort, element "ID"\n", i)) ; |
|
171 for (f = Child [i] ; f != EMPTY ; f = Sibling [f]) |
|
172 { |
|
173 ASSERT (f >= 0 && f < nn) ; |
|
174 AMD_DEBUG1 ((" "ID" "ID"\n", f, Fsize [f])) ; |
|
175 ASSERT (Nv [f] > 0) ; |
|
176 nchild-- ; |
|
177 } |
|
178 ASSERT (nchild == 0) ; |
|
179 #endif |
|
180 |
|
181 } |
|
182 } |
|
183 |
|
184 /* --------------------------------------------------------------------- */ |
|
185 /* postorder the assembly tree */ |
|
186 /* --------------------------------------------------------------------- */ |
|
187 |
|
188 for (i = 0 ; i < nn ; i++) |
|
189 { |
|
190 Order [i] = EMPTY ; |
|
191 } |
|
192 |
|
193 k = 0 ; |
|
194 |
|
195 for (i = 0 ; i < nn ; i++) |
|
196 { |
|
197 if (Parent [i] == EMPTY && Nv [i] > 0) |
|
198 { |
|
199 AMD_DEBUG1 (("Root of assembly tree "ID"\n", i)) ; |
|
200 k = AMD_post_tree (i, k, Child, Sibling, Order, Stack |
|
201 #ifndef NDEBUG |
|
202 , nn |
|
203 #endif |
|
204 ) ; |
|
205 } |
|
206 } |
|
207 } |