amesos_amd_post_tree.c

Go to the documentation of this file.

/* ========================================================================= */
/* === 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 "amesos_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" \n", 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\n", 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"\n", i, k)) ;
      Order [i] = k++ ;
      ASSERT (k <= nn) ;
  }

#ifndef NDEBUG
  AMD_DEBUG1 (("\nStack:")) ;
  for (h = head ; h >= 0 ; h--)
  {
      Int j = Stack [h] ;
      AMD_DEBUG1 ((" "ID, j)) ;
      ASSERT (j >= 0 && j < nn) ;
  }
  AMD_DEBUG1 (("\n\n")) ;
  ASSERT (head < nn) ;
#endif

    }
    return (k) ;
}