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