/* ========================================================================= */

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

                ) ;

        }

    }

}