alpar@1: /* ========================================================================= */
alpar@1: /* === AMD_post_tree ======================================================= */
alpar@1: /* ========================================================================= */
alpar@1: 
alpar@1: /* ------------------------------------------------------------------------- */
alpar@1: /* AMD, Copyright (c) Timothy A. Davis,                                      */
alpar@1: /* Patrick R. Amestoy, and Iain S. Duff.  See ../README.txt for License.     */
alpar@1: /* email: davis at cise.ufl.edu    CISE Department, Univ. of Florida.        */
alpar@1: /* web: http://www.cise.ufl.edu/research/sparse/amd                          */
alpar@1: /* ------------------------------------------------------------------------- */
alpar@1: 
alpar@1: /* Post-ordering of a supernodal elimination tree.  */
alpar@1: 
alpar@1: #include "amd_internal.h"
alpar@1: 
alpar@1: GLOBAL Int AMD_post_tree
alpar@1: (
alpar@1:     Int root,                   /* root of the tree */
alpar@1:     Int k,                      /* start numbering at k */
alpar@1:     Int Child [ ],              /* input argument of size nn, undefined on
alpar@1:                                  * output.  Child [i] is the head of a link
alpar@1:                                  * list of all nodes that are children of node
alpar@1:                                  * i in the tree. */
alpar@1:     const Int Sibling [ ],      /* input argument of size nn, not modified.
alpar@1:                                  * If f is a node in the link list of the
alpar@1:                                  * children of node i, then Sibling [f] is the
alpar@1:                                  * next child of node i.
alpar@1:                                  */
alpar@1:     Int Order [ ],              /* output order, of size nn.  Order [i] = k
alpar@1:                                  * if node i is the kth node of the reordered
alpar@1:                                  * tree. */
alpar@1:     Int Stack [ ]               /* workspace of size nn */
alpar@1: #ifndef NDEBUG
alpar@1:     , Int nn                    /* nodes are in the range 0..nn-1. */
alpar@1: #endif
alpar@1: )
alpar@1: {
alpar@1:     Int f, head, h, i ;
alpar@1: 
alpar@1: #if 0
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1:     /* recursive version (Stack [ ] is not used): */
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1: 
alpar@1:     /* this is simple, but can caouse stack overflow if nn is large */
alpar@1:     i = root ;
alpar@1:     for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
alpar@1:     {
alpar@1:         k = AMD_post_tree (f, k, Child, Sibling, Order, Stack, nn) ;
alpar@1:     }
alpar@1:     Order [i] = k++ ;
alpar@1:     return (k) ;
alpar@1: #endif
alpar@1: 
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1:     /* non-recursive version, using an explicit stack */
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1: 
alpar@1:     /* push root on the stack */
alpar@1:     head = 0 ;
alpar@1:     Stack [0] = root ;
alpar@1: 
alpar@1:     while (head >= 0)
alpar@1:     {
alpar@1:         /* get head of stack */
alpar@1:         ASSERT (head < nn) ;
alpar@1:         i = Stack [head] ;
alpar@1:         AMD_DEBUG1 (("head of stack "ID" \n", i)) ;
alpar@1:         ASSERT (i >= 0 && i < nn) ;
alpar@1: 
alpar@1:         if (Child [i] != EMPTY)
alpar@1:         {
alpar@1:             /* the children of i are not yet ordered */
alpar@1:             /* push each child onto the stack in reverse order */
alpar@1:             /* so that small ones at the head of the list get popped first */
alpar@1:             /* and the biggest one at the end of the list gets popped last */
alpar@1:             for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
alpar@1:             {
alpar@1:                 head++ ;
alpar@1:                 ASSERT (head < nn) ;
alpar@1:                 ASSERT (f >= 0 && f < nn) ;
alpar@1:             }
alpar@1:             h = head ;
alpar@1:             ASSERT (head < nn) ;
alpar@1:             for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
alpar@1:             {
alpar@1:                 ASSERT (h > 0) ;
alpar@1:                 Stack [h--] = f ;
alpar@1:                 AMD_DEBUG1 (("push "ID" on stack\n", f)) ;
alpar@1:                 ASSERT (f >= 0 && f < nn) ;
alpar@1:             }
alpar@1:             ASSERT (Stack [h] == i) ;
alpar@1: 
alpar@1:             /* delete child list so that i gets ordered next time we see it */
alpar@1:             Child [i] = EMPTY ;
alpar@1:         }
alpar@1:         else
alpar@1:         {
alpar@1:             /* the children of i (if there were any) are already ordered */
alpar@1:             /* remove i from the stack and order it.  Front i is kth front */
alpar@1:             head-- ;
alpar@1:             AMD_DEBUG1 (("pop "ID" order "ID"\n", i, k)) ;
alpar@1:             Order [i] = k++ ;
alpar@1:             ASSERT (k <= nn) ;
alpar@1:         }
alpar@1: 
alpar@1: #ifndef NDEBUG
alpar@1:         AMD_DEBUG1 (("\nStack:")) ;
alpar@1:         for (h = head ; h >= 0 ; h--)
alpar@1:         {
alpar@1:             Int j = Stack [h] ;
alpar@1:             AMD_DEBUG1 ((" "ID, j)) ;
alpar@1:             ASSERT (j >= 0 && j < nn) ;
alpar@1:         }
alpar@1:         AMD_DEBUG1 (("\n\n")) ;
alpar@1:         ASSERT (head < nn) ;
alpar@1: #endif
alpar@1: 
alpar@1:     }
alpar@1:     return (k) ;
alpar@1: }