Blame view
fvn_sparse/AMD/Source/amd_post_tree.c
3.69 KB
422234dc3
git-svn-id: https...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
/* ========================================================================= */
/* === AMD_post_tree ======================================================= */
/* ========================================================================= */
/* ------------------------------------------------------------------------- */
/* AMD, Copyright (c) Timothy A. Davis, */
/* Patrick R. Amestoy, and Iain S. Duff. See ../README.txt for License. */
/* email: davis at cise.ufl.edu CISE Department, Univ. of Florida. */
/* web: http://www.cise.ufl.edu/research/sparse/amd */
/* ------------------------------------------------------------------------- */
/* Post-ordering of a supernodal elimination tree. */
#include "amd_internal.h"
GLOBAL Int AMD_post_tree
(
Int root, /* root of the tree */
Int k, /* start numbering at k */
Int Child [ ], /* input argument of size nn, undefined on
* output. Child [i] is the head of a link
* list of all nodes that are children of node
* i in the tree. */
const Int Sibling [ ], /* input argument of size nn, not modified.
* If f is a node in the link list of the
* children of node i, then Sibling [f] is the
* next child of node i.
*/
Int Order [ ], /* output order, of size nn. Order [i] = k
* if node i is the kth node of the reordered
* tree. */
Int Stack [ ] /* workspace of size nn */
#ifndef NDEBUG
, Int nn /* nodes are in the range 0..nn-1. */
#endif
)
{
Int f, head, h, i ;
#if 0
/* --------------------------------------------------------------------- */
/* recursive version (Stack [ ] is not used): */
/* --------------------------------------------------------------------- */
/* this is simple, but can caouse stack overflow if nn is large */
i = root ;
for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
{
k = AMD_post_tree (f, k, Child, Sibling, Order, Stack, nn) ;
}
Order [i] = k++ ;
return (k) ;
#endif
/* --------------------------------------------------------------------- */
/* non-recursive version, using an explicit stack */
/* --------------------------------------------------------------------- */
/* push root on the stack */
head = 0 ;
Stack [0] = root ;
while (head >= 0)
{
/* get head of stack */
ASSERT (head < nn) ;
i = Stack [head] ;
AMD_DEBUG1 (("head of stack "ID"
", i)) ;
ASSERT (i >= 0 && i < nn) ;
if (Child [i] != EMPTY)
{
/* the children of i are not yet ordered */
/* push each child onto the stack in reverse order */
/* so that small ones at the head of the list get popped first */
/* and the biggest one at the end of the list gets popped last */
for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
{
head++ ;
ASSERT (head < nn) ;
ASSERT (f >= 0 && f < nn) ;
}
h = head ;
ASSERT (head < nn) ;
for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
{
ASSERT (h > 0) ;
Stack [h--] = f ;
AMD_DEBUG1 (("push "ID" on stack
", f)) ;
ASSERT (f >= 0 && f < nn) ;
}
ASSERT (Stack [h] == i) ;
/* delete child list so that i gets ordered next time we see it */
Child [i] = EMPTY ;
}
else
{
/* the children of i (if there were any) are already ordered */
/* remove i from the stack and order it. Front i is kth front */
head-- ;
AMD_DEBUG1 (("pop "ID" order "ID"
", i, k)) ;
Order [i] = k++ ;
ASSERT (k <= nn) ;
}
#ifndef NDEBUG
AMD_DEBUG1 (("
Stack:")) ;
for (h = head ; h >= 0 ; h--)
{
Int j = Stack [h] ;
AMD_DEBUG1 ((" "ID, j)) ;
ASSERT (j >= 0 && j < nn) ;
}
AMD_DEBUG1 (("
")) ;
ASSERT (head < nn) ;
#endif
}
return (k) ;
}
|