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