lemon-project-template-glpk
view deps/glpk/src/amd/amd_post_tree.c @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 /* ========================================================================= */
2 /* === AMD_post_tree ======================================================= */
3 /* ========================================================================= */
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 /* ------------------------------------------------------------------------- */
12 /* Post-ordering of a supernodal elimination tree. */
14 #include "amd_internal.h"
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 ;
40 #if 0
41 /* --------------------------------------------------------------------- */
42 /* recursive version (Stack [ ] is not used): */
43 /* --------------------------------------------------------------------- */
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
55 /* --------------------------------------------------------------------- */
56 /* non-recursive version, using an explicit stack */
57 /* --------------------------------------------------------------------- */
59 /* push root on the stack */
60 head = 0 ;
61 Stack [0] = root ;
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) ;
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) ;
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 }
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
119 }
120 return (k) ;
121 }