amesos_amd_postorder.c

Go to the documentation of this file.

/* ========================================================================= */
/* === AMD_postorder ======================================================= */
/* ========================================================================= */

/* ------------------------------------------------------------------------- */
/* 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                          */
/* ------------------------------------------------------------------------- */

/* Perform a postordering (via depth-first search) of an assembly tree. */

#include "amesos_amd_internal.h"

GLOBAL void AMD_postorder
(
    /* inputs, not modified on output: */
    Int nn,   /* nodes are in the range 0..nn-1 */
    Int Parent [ ], /* Parent [j] is the parent of j, or EMPTY if root */
    Int Nv [ ],   /* Nv [j] > 0 number of pivots represented by node j,
       * or zero if j is not a node. */
    Int Fsize [ ],  /* Fsize [j]: size of node j */

    /* output, not defined on input: */
    Int Order [ ],  /* output post-order */

    /* workspaces of size nn: */
    Int Child [ ],
    Int Sibling [ ],
    Int Stack [ ]
)
{
    Int i, j, k, parent, frsize, f, fprev, maxfrsize, bigfprev, bigf, fnext ;

    for (j = 0 ; j < nn ; j++)
    {
  Child [j] = EMPTY ;
  Sibling [j] = EMPTY ;
    }

    /* --------------------------------------------------------------------- */
    /* place the children in link lists - bigger elements tend to be last */
    /* --------------------------------------------------------------------- */

    for (j = nn-1 ; j >= 0 ; j--)
    {
  if (Nv [j] > 0)
  {
      /* this is an element */
      parent = Parent [j] ;
      if (parent != EMPTY)
      {
    /* place the element in link list of the children its parent */
    /* bigger elements will tend to be at the end of the list */
    Sibling [j] = Child [parent] ;
    Child [parent] = j ;
      }
  }
    }

#ifndef NDEBUG
    {
  Int nels, ff, nchild ;
  AMD_DEBUG1 (("\n\n================================ AMD_postorder:\n"));
  nels = 0 ;
  for (j = 0 ; j < nn ; j++)
  {
      if (Nv [j] > 0)
      {
    AMD_DEBUG1 (( ""ID" :  nels "ID" npiv "ID" size "ID
        " parent "ID" maxfr "ID"\n", j, nels,
        Nv [j], Fsize [j], Parent [j], Fsize [j])) ;
    /* this is an element */
    /* dump the link list of children */
    nchild = 0 ;
    AMD_DEBUG1 (("    Children: ")) ;
    for (ff = Child [j] ; ff != EMPTY ; ff = Sibling [ff])
    {
        AMD_DEBUG1 ((ID" ", ff)) ;
        ASSERT (Parent [ff] == j) ;
        nchild++ ;
        ASSERT (nchild < nn) ;
    }
    AMD_DEBUG1 (("\n")) ;
    parent = Parent [j] ;
    if (parent != EMPTY)
    {
        ASSERT (Nv [parent] > 0) ;
    }
    nels++ ;
      }
  }
    }
    AMD_DEBUG1 (("\n\nGo through the children of each node, and put\n"
     "the biggest child last in each list:\n")) ;
#endif

    /* --------------------------------------------------------------------- */
    /* place the largest child last in the list of children for each node */
    /* --------------------------------------------------------------------- */

    for (i = 0 ; i < nn ; i++)
    {
  if (Nv [i] > 0 && Child [i] != EMPTY)
  {

#ifndef NDEBUG
      Int nchild ;
      AMD_DEBUG1 (("Before partial sort, element "ID"\n", i)) ;
      nchild = 0 ;
      for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
      {
    ASSERT (f >= 0 && f < nn) ;
    AMD_DEBUG1 (("      f: "ID"  size: "ID"\n", f, Fsize [f])) ;
    nchild++ ;
    ASSERT (nchild <= nn) ;
      }
#endif

      /* find the biggest element in the child list */
      fprev = EMPTY ;
      maxfrsize = EMPTY ;
      bigfprev = EMPTY ;
      bigf = EMPTY ;
      for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
      {
    ASSERT (f >= 0 && f < nn) ;
    frsize = Fsize [f] ;
    if (frsize >= maxfrsize)
    {
        /* this is the biggest seen so far */
        maxfrsize = frsize ;
        bigfprev = fprev ;
        bigf = f ;
    }
    fprev = f ;
      }
      ASSERT (bigf != EMPTY) ;

      fnext = Sibling [bigf] ;

      AMD_DEBUG1 (("bigf "ID" maxfrsize "ID" bigfprev "ID" fnext "ID
    " fprev " ID"\n", bigf, maxfrsize, bigfprev, fnext, fprev)) ;

      if (fnext != EMPTY)
      {
    /* if fnext is EMPTY then bigf is already at the end of list */

    if (bigfprev == EMPTY)
    {
        /* delete bigf from the element of the list */
        Child [i] = fnext ;
    }
    else
    {
        /* delete bigf from the middle of the list */
        Sibling [bigfprev] = fnext ;
    }

    /* put bigf at the end of the list */
    Sibling [bigf] = EMPTY ;
    ASSERT (Child [i] != EMPTY) ;
    ASSERT (fprev != bigf) ;
    ASSERT (fprev != EMPTY) ;
    Sibling [fprev] = bigf ;
      }

#ifndef NDEBUG
      AMD_DEBUG1 (("After partial sort, element "ID"\n", i)) ;
      for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
      {
    ASSERT (f >= 0 && f < nn) ;
    AMD_DEBUG1 (("        "ID"  "ID"\n", f, Fsize [f])) ;
    ASSERT (Nv [f] > 0) ;
    nchild-- ;
      }
      ASSERT (nchild == 0) ;
#endif

  }
    }

    /* --------------------------------------------------------------------- */
    /* postorder the assembly tree */
    /* --------------------------------------------------------------------- */

    for (i = 0 ; i < nn ; i++)
    {
  Order [i] = EMPTY ;
    }

    k = 0 ;

    for (i = 0 ; i < nn ; i++)
    {
  if (Parent [i] == EMPTY && Nv [i] > 0)
  {
      AMD_DEBUG1 (("Root of assembly tree "ID"\n", i)) ;
      k = AMD_post_tree (i, k, Child, Sibling, Order, Stack
#ifndef NDEBUG
    , nn
#endif
    ) ;
  }
    }
}