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