1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/amd/amd_post_tree.c	Mon Dec 06 13:09:21 2010 +0100
     1.3 @@ -0,0 +1,121 @@
     1.4 +/* ========================================================================= */
     1.5 +/* === AMD_post_tree ======================================================= */
     1.6 +/* ========================================================================= */
     1.7 +
     1.8 +/* ------------------------------------------------------------------------- */
     1.9 +/* AMD, Copyright (c) Timothy A. Davis,                                      */
    1.10 +/* Patrick R. Amestoy, and Iain S. Duff.  See ../README.txt for License.     */
    1.11 +/* email: davis at cise.ufl.edu    CISE Department, Univ. of Florida.        */
    1.12 +/* web: http://www.cise.ufl.edu/research/sparse/amd                          */
    1.13 +/* ------------------------------------------------------------------------- */
    1.14 +
    1.15 +/* Post-ordering of a supernodal elimination tree.  */
    1.16 +
    1.17 +#include "amd_internal.h"
    1.18 +
    1.19 +GLOBAL Int AMD_post_tree
    1.20 +(
    1.21 +    Int root,                   /* root of the tree */
    1.22 +    Int k,                      /* start numbering at k */
    1.23 +    Int Child [ ],              /* input argument of size nn, undefined on
    1.24 +                                 * output.  Child [i] is the head of a link
    1.25 +                                 * list of all nodes that are children of node
    1.26 +                                 * i in the tree. */
    1.27 +    const Int Sibling [ ],      /* input argument of size nn, not modified.
    1.28 +                                 * If f is a node in the link list of the
    1.29 +                                 * children of node i, then Sibling [f] is the
    1.30 +                                 * next child of node i.
    1.31 +                                 */
    1.32 +    Int Order [ ],              /* output order, of size nn.  Order [i] = k
    1.33 +                                 * if node i is the kth node of the reordered
    1.34 +                                 * tree. */
    1.35 +    Int Stack [ ]               /* workspace of size nn */
    1.36 +#ifndef NDEBUG
    1.37 +    , Int nn                    /* nodes are in the range 0..nn-1. */
    1.38 +#endif
    1.39 +)
    1.40 +{
    1.41 +    Int f, head, h, i ;
    1.42 +
    1.43 +#if 0
    1.44 +    /* --------------------------------------------------------------------- */
    1.45 +    /* recursive version (Stack [ ] is not used): */
    1.46 +    /* --------------------------------------------------------------------- */
    1.47 +
    1.48 +    /* this is simple, but can caouse stack overflow if nn is large */
    1.49 +    i = root ;
    1.50 +    for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
    1.51 +    {
    1.52 +        k = AMD_post_tree (f, k, Child, Sibling, Order, Stack, nn) ;
    1.53 +    }
    1.54 +    Order [i] = k++ ;
    1.55 +    return (k) ;
    1.56 +#endif
    1.57 +
    1.58 +    /* --------------------------------------------------------------------- */
    1.59 +    /* non-recursive version, using an explicit stack */
    1.60 +    /* --------------------------------------------------------------------- */
    1.61 +
    1.62 +    /* push root on the stack */
    1.63 +    head = 0 ;
    1.64 +    Stack [0] = root ;
    1.65 +
    1.66 +    while (head >= 0)
    1.67 +    {
    1.68 +        /* get head of stack */
    1.69 +        ASSERT (head < nn) ;
    1.70 +        i = Stack [head] ;
    1.71 +        AMD_DEBUG1 (("head of stack "ID" \n", i)) ;
    1.72 +        ASSERT (i >= 0 && i < nn) ;
    1.73 +
    1.74 +        if (Child [i] != EMPTY)
    1.75 +        {
    1.76 +            /* the children of i are not yet ordered */
    1.77 +            /* push each child onto the stack in reverse order */
    1.78 +            /* so that small ones at the head of the list get popped first */
    1.79 +            /* and the biggest one at the end of the list gets popped last */
    1.80 +            for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
    1.81 +            {
    1.82 +                head++ ;
    1.83 +                ASSERT (head < nn) ;
    1.84 +                ASSERT (f >= 0 && f < nn) ;
    1.85 +            }
    1.86 +            h = head ;
    1.87 +            ASSERT (head < nn) ;
    1.88 +            for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
    1.89 +            {
    1.90 +                ASSERT (h > 0) ;
    1.91 +                Stack [h--] = f ;
    1.92 +                AMD_DEBUG1 (("push "ID" on stack\n", f)) ;
    1.93 +                ASSERT (f >= 0 && f < nn) ;
    1.94 +            }
    1.95 +            ASSERT (Stack [h] == i) ;
    1.96 +
    1.97 +            /* delete child list so that i gets ordered next time we see it */
    1.98 +            Child [i] = EMPTY ;
    1.99 +        }
   1.100 +        else
   1.101 +        {
   1.102 +            /* the children of i (if there were any) are already ordered */
   1.103 +            /* remove i from the stack and order it.  Front i is kth front */
   1.104 +            head-- ;
   1.105 +            AMD_DEBUG1 (("pop "ID" order "ID"\n", i, k)) ;
   1.106 +            Order [i] = k++ ;
   1.107 +            ASSERT (k <= nn) ;
   1.108 +        }
   1.109 +
   1.110 +#ifndef NDEBUG
   1.111 +        AMD_DEBUG1 (("\nStack:")) ;
   1.112 +        for (h = head ; h >= 0 ; h--)
   1.113 +        {
   1.114 +            Int j = Stack [h] ;
   1.115 +            AMD_DEBUG1 ((" "ID, j)) ;
   1.116 +            ASSERT (j >= 0 && j < nn) ;
   1.117 +        }
   1.118 +        AMD_DEBUG1 (("\n\n")) ;
   1.119 +        ASSERT (head < nn) ;
   1.120 +#endif
   1.121 +
   1.122 +    }
   1.123 +    return (k) ;
   1.124 +}