lemon-project-template-glpk

comparison deps/glpk/src/amd/amd_postorder.c @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:c02c073c7524
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 }