Amesos Package Browser (Single Doxygen Collection)
Development
src
SuiteSparse
CHOLMOD
Cholesky
amesos_cholmod_postorder.c
Go to the documentation of this file.
1
/* ========================================================================== */
2
/* === Cholesky/cholmod_postorder =========================================== */
3
/* ========================================================================== */
4
5
/* -----------------------------------------------------------------------------
6
* CHOLMOD/Cholesky Module. Copyright (C) 2005-2006, Timothy A. Davis
7
* The CHOLMOD/Cholesky Module is licensed under Version 2.1 of the GNU
8
* Lesser General Public License. See lesser.txt for a text of the license.
9
* CHOLMOD is also available under other licenses; contact authors for details.
10
* http://www.cise.ufl.edu/research/sparse
11
* -------------------------------------------------------------------------- */
12
13
/* Compute the postorder of a tree. */
14
15
#ifndef NCHOLESKY
16
17
#include "
amesos_cholmod_internal.h
"
18
#include "
amesos_cholmod_cholesky.h
"
19
20
21
/* ========================================================================== */
22
/* === dfs ================================================================== */
23
/* ========================================================================== */
24
25
/* The code below includes both a recursive and non-recursive depth-first-search
26
* of a tree. The recursive code is simpler, but can lead to stack overflow.
27
* It is left here for reference, to understand what the non-recursive code
28
* is computing. To try the recursive version, uncomment the following
29
* #define, or compile the code with -DRECURSIVE. Be aware that stack
30
* overflow may occur.
31
#define RECURSIVE
32
*/
33
34
#ifdef RECURSIVE
35
36
/* recursive version: a working code for reference only, not actual use */
37
38
static
Int
amesos_dfs
/* return the new value of k */
39
(
40
Int
p,
/* start a DFS at node p */
41
Int
k,
/* start the node numbering at k */
42
Int
Post [ ],
/* Post ordering, modified on output */
43
Int
Head [ ],
/* Head [p] = youngest child of p; EMPTY on output */
44
Int
Next [ ],
/* Next [j] = sibling of j; unmodified */
45
Int
Pstack [ ]
/* unused */
46
)
47
{
48
Int
j ;
49
/* start a DFS at each child of node p */
50
for
(j = Head [p] ; j !=
EMPTY
; j = Next [j])
51
{
52
/* start a DFS at child node j */
53
k =
amesos_dfs
(j, k, Post, Head, Next, Pstack) ;
54
}
55
Post [k++] = p ;
/* order node p as the kth node */
56
Head [p] =
EMPTY
;
/* link list p no longer needed */
57
return
(k) ;
/* the next node will be numbered k */
58
}
59
60
#else
61
62
/* non-recursive version for actual use */
63
64
static
Int
amesos_dfs
/* return the new value of k */
65
(
66
Int
p,
/* start the DFS at a root node p */
67
Int
k,
/* start the node numbering at k */
68
Int
Post [ ],
/* Post ordering, modified on output */
69
Int
Head [ ],
/* Head [p] = youngest child of p; EMPTY on output */
70
Int
Next [ ],
/* Next [j] = sibling of j; unmodified */
71
Int
Pstack [ ]
/* workspace of size n, undefined on input or output */
72
)
73
{
74
Int
j, phead ;
75
76
/* put the root node on the stack */
77
Pstack [0] = p ;
78
phead = 0 ;
79
80
/* while the stack is not empty, do: */
81
while
(phead >= 0)
82
{
83
/* grab the node p from top of the stack and get its youngest child j */
84
p = Pstack [phead] ;
85
j = Head [p] ;
86
if
(j ==
EMPTY
)
87
{
88
/* all children of p ordered. remove p from stack and order it */
89
phead-- ;
90
Post [k++] = p ;
/* order node p as the kth node */
91
}
92
else
93
{
94
/* leave p on the stack. Start a DFS at child node j by putting
95
* j on the stack and removing j from the list of children of p. */
96
Head [p] = Next [j] ;
97
Pstack [++phead] = j ;
98
}
99
}
100
return
(k) ;
/* the next node will be numbered k */
101
}
102
103
#endif
104
105
/* ========================================================================== */
106
/* === cholmod_postorder ==================================================== */
107
/* ========================================================================== */
108
109
/* Postorder a tree. The tree is either an elimination tree (the output from
110
* from cholmod_etree) or a component tree (from cholmod_nested_dissection).
111
*
112
* An elimination tree is a complete tree of n nodes with Parent [j] > j or
113
* Parent [j] = EMPTY if j is a root. On output Post [0..n-1] is a complete
114
* permutation vector.
115
*
116
* A component tree is a subset of 0..n-1. Parent [j] = -2 if node j is not
117
* in the component tree. Parent [j] = EMPTY if j is a root of the component
118
* tree, and Parent [j] is in the range 0 to n-1 if j is in the component
119
* tree but not a root. On output, Post [k] is defined only for nodes in
120
* the component tree. Post [k] = j if node j is the kth node in the
121
* postordered component tree, where k is in the range 0 to the number of
122
* components minus 1.
123
*
124
* Node j is ignored and not included in the postorder if Parent [j] < EMPTY.
125
*
126
* As a result, check_parent (Parent, n,...) may fail on input, since
127
* cholmod_check_parent assumes Parent is an elimination tree. Similarly,
128
* cholmod_check_perm (Post, ...) may fail on output, since Post is a partial
129
* permutation if Parent is a component tree.
130
*
131
* An optional node weight can be given. When starting a postorder at node j,
132
* the children of j are ordered in decreasing order of their weight.
133
* If no weights are given (Weight is NULL) then children are ordered in
134
* decreasing order of their node number. The weight of a node must be in the
135
* range 0 to n-1. Weights outside that range are silently converted to that
136
* range (weights < 0 are treated as zero, and weights >= n are treated as n-1).
137
*
138
*
139
* workspace: Head (n), Iwork (2*n)
140
*/
141
142
UF_long
CHOLMOD
(postorder)
/* return # of nodes postordered */
143
(
144
/* ---- input ---- */
145
Int
*Parent,
/* size n. Parent [j] = p if p is the parent of j */
146
size_t
n,
147
Int
*Weight,
/* size n, optional. Weight [j] is weight of node j */
148
/* ---- output --- */
149
Int
*Post,
/* size n. Post [k] = j is kth in postordered tree */
150
/* --------------- */
151
cholmod_common
*Common
152
)
153
{
154
Int
*Head, *Next, *Pstack, *Iwork ;
155
Int
j, p, k, w, nextj ;
156
size_t
s ;
157
int
ok =
TRUE
;
158
159
/* ---------------------------------------------------------------------- */
160
/* check inputs */
161
/* ---------------------------------------------------------------------- */
162
163
RETURN_IF_NULL_COMMON
(
EMPTY
) ;
164
RETURN_IF_NULL
(Parent,
EMPTY
) ;
165
RETURN_IF_NULL
(Post,
EMPTY
) ;
166
Common->status =
CHOLMOD_OK
;
167
168
/* ---------------------------------------------------------------------- */
169
/* allocate workspace */
170
/* ---------------------------------------------------------------------- */
171
172
/* s = 2*n */
173
s =
CHOLMOD
(
mult_size_t
) (n, 2, &ok) ;
174
if
(!ok)
175
{
176
ERROR
(
CHOLMOD_TOO_LARGE
,
"problem too large"
) ;
177
return
(
EMPTY
) ;
178
}
179
180
CHOLMOD
(
allocate_work
) (n, s, 0, Common) ;
181
if
(Common->status <
CHOLMOD_OK
)
182
{
183
return
(
EMPTY
) ;
184
}
185
ASSERT
(
CHOLMOD
(
dump_work
) (
TRUE
,
TRUE
, 0, Common)) ;
186
187
/* ---------------------------------------------------------------------- */
188
/* get inputs */
189
/* ---------------------------------------------------------------------- */
190
191
Head = Common->Head ;
/* size n+1, initially all EMPTY */
192
Iwork = Common->Iwork ;
193
Next = Iwork ;
/* size n (i/i/l) */
194
Pstack = Iwork + n ;
/* size n (i/i/l) */
195
196
/* ---------------------------------------------------------------------- */
197
/* construct a link list of children for each node */
198
/* ---------------------------------------------------------------------- */
199
200
if
(Weight ==
NULL
)
201
{
202
203
/* in reverse order so children are in ascending order in each list */
204
for
(j = n-1 ; j >= 0 ; j--)
205
{
206
p = Parent [j] ;
207
if
(p >= 0 && p < ((
Int
) n))
208
{
209
/* add j to the list of children for node p */
210
Next [j] = Head [p] ;
211
Head [p] = j ;
212
}
213
}
214
215
/* Head [p] = j if j is the youngest (least-numbered) child of p */
216
/* Next [j1] = j2 if j2 is the next-oldest sibling of j1 */
217
218
}
219
else
220
{
221
222
/* First, construct a set of link lists according to Weight.
223
*
224
* Whead [w] = j if node j is the first node in bucket w.
225
* Next [j1] = j2 if node j2 follows j1 in a link list.
226
*/
227
228
Int
*Whead = Pstack ;
/* use Pstack as workspace for Whead [ */
229
230
for
(w = 0 ; w < ((
Int
) n) ; w++)
231
{
232
Whead [w] =
EMPTY
;
233
}
234
/* do in forward order, so nodes that ties are ordered by node index */
235
for
(j = 0 ; j < ((
Int
) n) ; j++)
236
{
237
p = Parent [j] ;
238
if
(p >= 0 && p < ((
Int
) n))
239
{
240
w = Weight [j] ;
241
w =
MAX
(0, w) ;
242
w =
MIN
(w, ((
Int
) n) - 1) ;
243
/* place node j at the head of link list for weight w */
244
Next [j] = Whead [w] ;
245
Whead [w] = j ;
246
}
247
}
248
249
/* traverse weight buckets, placing each node in its parent's list */
250
for
(w = n-1 ; w >= 0 ; w--)
251
{
252
for
(j = Whead [w] ; j !=
EMPTY
; j = nextj)
253
{
254
nextj = Next [j] ;
255
/* put node j in the link list of its parent */
256
p = Parent [j] ;
257
ASSERT
(p >= 0 && p < ((
Int
) n)) ;
258
Next [j] = Head [p] ;
259
Head [p] = j ;
260
}
261
}
262
263
/* Whead no longer needed ] */
264
/* Head [p] = j if j is the lightest child of p */
265
/* Next [j1] = j2 if j2 is the next-heaviest sibling of j1 */
266
}
267
268
/* ---------------------------------------------------------------------- */
269
/* start a DFS at each root node of the etree */
270
/* ---------------------------------------------------------------------- */
271
272
k = 0 ;
273
for
(j = 0 ; j < ((
Int
) n) ; j++)
274
{
275
if
(Parent [j] ==
EMPTY
)
276
{
277
/* j is the root of a tree; start a DFS here */
278
k =
amesos_dfs
(j, k, Post, Head, Next, Pstack) ;
279
}
280
}
281
282
/* this would normally be EMPTY already, unless Parent is invalid */
283
for
(j = 0 ; j < ((
Int
) n) ; j++)
284
{
285
Head [j] =
EMPTY
;
286
}
287
288
PRINT1
((
"postordered "
ID
" nodes\n"
, k)) ;
289
ASSERT
(
CHOLMOD
(
dump_work
) (
TRUE
,
TRUE
, 0, Common)) ;
290
return
(k) ;
291
}
292
#endif
CHOLMOD_TOO_LARGE
#define CHOLMOD_TOO_LARGE
Definition:
amesos_cholmod_core.h:367
cholmod_common_struct
Definition:
amesos_cholmod_core.h:393
EMPTY
#define EMPTY
Definition:
amesos_amd_internal.h:144
Int
#define Int
Definition:
amesos_amd_internal.h:190
PRINT1
#define PRINT1(params)
Definition:
amesos_cholmod_internal.h:380
RETURN_IF_NULL_COMMON
#define RETURN_IF_NULL_COMMON(result)
Definition:
amesos_cholmod_internal.h:126
mult_size_t
size_t CHOLMOD() mult_size_t(size_t a, size_t k, int *ok)
Definition:
amesos_cholmod_l_memory.c:79
dump_work
int CHOLMOD() dump_work(int flag, int head, UF_long wsize, cholmod_common *Common)
Definition:
amesos_cholmod_check.c:2556
MAX
#define MAX(a, b)
Definition:
amesos_amd_internal.h:125
NULL
#define NULL
Definition:
amesos_amd_internal.h:153
ASSERT
#define ASSERT(expression)
Definition:
amesos_amd_internal.h:331
ID
#define ID
Definition:
amesos_amd_internal.h:191
amesos_cholmod_cholesky.h
amesos_cholmod_internal.h
CHOLMOD_OK
#define CHOLMOD_OK
Definition:
amesos_cholmod_core.h:364
allocate_work
int CHOLMOD() allocate_work(size_t nrow, size_t iworksize, size_t xworksize, cholmod_common *Common)
Definition:
amesos_cholmod_common.c:345
RETURN_IF_NULL
#define RETURN_IF_NULL(A, result)
Definition:
amesos_cholmod_internal.h:113
MIN
#define MIN(a, b)
Definition:
amesos_amd_internal.h:126
CHOLMOD
UF_long CHOLMOD(postorder)
Definition:
amesos_cholmod_postorder.c:142
amesos_dfs
static Int amesos_dfs(Int p, Int k, Int Post [], Int Head [], Int Next [], Int Pstack [])
Definition:
amesos_cholmod_postorder.c:65
UF_long
#define UF_long
Definition:
amesos_UFconfig.h:60
ERROR
#define ERROR(status, msg)
Definition:
amesos_cholmod_internal.h:108
TRUE
#define TRUE
Definition:
amesos_amd_internal.h:140
Generated by
1.8.14