Amesos Package Browser (Single Doxygen Collection)
Development
src
SuiteSparse
AMD
Source
amesos_amd_post_tree.c
Go to the documentation of this file.
1
/* ========================================================================= */
2
/* === AMD_post_tree ======================================================= */
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
/* Post-ordering of a supernodal elimination tree. */
13
14
#include "
amesos_amd_internal.h
"
15
16
GLOBAL
Int
AMD_post_tree
17
(
18
Int
root,
/* root of the tree */
19
Int
k,
/* start numbering at k */
20
Int
Child [ ],
/* input argument of size nn, undefined on
21
* output. Child [i] is the head of a link
22
* list of all nodes that are children of node
23
* i in the tree. */
24
const
Int
Sibling [ ],
/* input argument of size nn, not modified.
25
* If f is a node in the link list of the
26
* children of node i, then Sibling [f] is the
27
* next child of node i.
28
*/
29
Int
Order [ ],
/* output order, of size nn. Order [i] = k
30
* if node i is the kth node of the reordered
31
* tree. */
32
Int
Stack [ ]
/* workspace of size nn */
33
#ifndef
NDEBUG
34
,
Int
nn
/* nodes are in the range 0..nn-1. */
35
#endif
36
)
37
{
38
Int
f
, head, h, i ;
39
40
#if 0
41
/* --------------------------------------------------------------------- */
42
/* recursive version (Stack [ ] is not used): */
43
/* --------------------------------------------------------------------- */
44
45
/* this is simple, but can caouse stack overflow if nn is large */
46
i = root ;
47
for
(
f
= Child [i] ;
f
!=
EMPTY
;
f
= Sibling [
f
])
48
{
49
k =
AMD_post_tree
(
f
, k, Child, Sibling, Order, Stack, nn) ;
50
}
51
Order [i] = k++ ;
52
return
(k) ;
53
#endif
54
55
/* --------------------------------------------------------------------- */
56
/* non-recursive version, using an explicit stack */
57
/* --------------------------------------------------------------------- */
58
59
/* push root on the stack */
60
head = 0 ;
61
Stack [0] = root ;
62
63
while
(head >= 0)
64
{
65
/* get head of stack */
66
ASSERT
(head < nn) ;
67
i = Stack [head] ;
68
AMD_DEBUG1
((
"head of stack "
ID
" \n"
, i)) ;
69
ASSERT
(i >= 0 && i < nn) ;
70
71
if
(Child [i] !=
EMPTY
)
72
{
73
/* the children of i are not yet ordered */
74
/* push each child onto the stack in reverse order */
75
/* so that small ones at the head of the list get popped first */
76
/* and the biggest one at the end of the list gets popped last */
77
for
(
f
= Child [i] ;
f
!=
EMPTY
;
f
= Sibling [
f
])
78
{
79
head++ ;
80
ASSERT
(head < nn) ;
81
ASSERT
(
f
>= 0 &&
f
< nn) ;
82
}
83
h = head ;
84
ASSERT
(head < nn) ;
85
for
(
f
= Child [i] ;
f
!=
EMPTY
;
f
= Sibling [
f
])
86
{
87
ASSERT
(h > 0) ;
88
Stack [h--] =
f
;
89
AMD_DEBUG1
((
"push "
ID
" on stack\n"
,
f
)) ;
90
ASSERT
(
f
>= 0 &&
f
< nn) ;
91
}
92
ASSERT
(Stack [h] == i) ;
93
94
/* delete child list so that i gets ordered next time we see it */
95
Child [i] =
EMPTY
;
96
}
97
else
98
{
99
/* the children of i (if there were any) are already ordered */
100
/* remove i from the stack and order it. Front i is kth front */
101
head-- ;
102
AMD_DEBUG1
((
"pop "
ID
" order "
ID
"\n"
, i, k)) ;
103
Order [i] = k++ ;
104
ASSERT
(k <= nn) ;
105
}
106
107
#ifndef NDEBUG
108
AMD_DEBUG1
((
"\nStack:"
)) ;
109
for
(h = head ; h >= 0 ; h--)
110
{
111
Int
j = Stack [h] ;
112
AMD_DEBUG1
((
" "
ID
, j)) ;
113
ASSERT
(j >= 0 && j < nn) ;
114
}
115
AMD_DEBUG1
((
"\n\n"
)) ;
116
ASSERT
(head < nn) ;
117
#endif
118
119
}
120
return
(k) ;
121
}
f
void f()
EMPTY
#define EMPTY
Definition:
amesos_amd_internal.h:144
GLOBAL
#define GLOBAL
Definition:
amesos_amd_internal.h:143
AMD_DEBUG1
#define AMD_DEBUG1(params)
Definition:
amesos_amd_internal.h:335
Int
#define Int
Definition:
amesos_amd_internal.h:190
ASSERT
#define ASSERT(expression)
Definition:
amesos_amd_internal.h:331
NDEBUG
#define NDEBUG
Definition:
amesos_btf_internal.h:29
ID
#define ID
Definition:
amesos_amd_internal.h:191
AMD_post_tree
GLOBAL Int AMD_post_tree(Int root, Int k, Int Child [], const Int Sibling [], Int Order [], Int Stack [], Int nn)
Definition:
amesos_amd_post_tree.c:17
amesos_amd_internal.h
Generated by
1.8.14