alpar@1: /* ========================================================================= */
alpar@1: /* === AMD_postorder ======================================================= */
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: /* Perform a postordering (via depth-first search) of an assembly tree. */
alpar@1: 
alpar@1: #include "amd_internal.h"
alpar@1: 
alpar@1: GLOBAL void AMD_postorder
alpar@1: (
alpar@1:     /* inputs, not modified on output: */
alpar@1:     Int nn,             /* nodes are in the range 0..nn-1 */
alpar@1:     Int Parent [ ],     /* Parent [j] is the parent of j, or EMPTY if root */
alpar@1:     Int Nv [ ],         /* Nv [j] > 0 number of pivots represented by node j,
alpar@1:                          * or zero if j is not a node. */
alpar@1:     Int Fsize [ ],      /* Fsize [j]: size of node j */
alpar@1: 
alpar@1:     /* output, not defined on input: */
alpar@1:     Int Order [ ],      /* output post-order */
alpar@1: 
alpar@1:     /* workspaces of size nn: */
alpar@1:     Int Child [ ],
alpar@1:     Int Sibling [ ],
alpar@1:     Int Stack [ ]
alpar@1: )
alpar@1: {
alpar@1:     Int i, j, k, parent, frsize, f, fprev, maxfrsize, bigfprev, bigf, fnext ;
alpar@1: 
alpar@1:     for (j = 0 ; j < nn ; j++)
alpar@1:     {
alpar@1:         Child [j] = EMPTY ;
alpar@1:         Sibling [j] = EMPTY ;
alpar@1:     }
alpar@1: 
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1:     /* place the children in link lists - bigger elements tend to be last */
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1: 
alpar@1:     for (j = nn-1 ; j >= 0 ; j--)
alpar@1:     {
alpar@1:         if (Nv [j] > 0)
alpar@1:         {
alpar@1:             /* this is an element */
alpar@1:             parent = Parent [j] ;
alpar@1:             if (parent != EMPTY)
alpar@1:             {
alpar@1:                 /* place the element in link list of the children its parent */
alpar@1:                 /* bigger elements will tend to be at the end of the list */
alpar@1:                 Sibling [j] = Child [parent] ;
alpar@1:                 Child [parent] = j ;
alpar@1:             }
alpar@1:         }
alpar@1:     }
alpar@1: 
alpar@1: #ifndef NDEBUG
alpar@1:     {
alpar@1:         Int nels, ff, nchild ;
alpar@1:         AMD_DEBUG1 (("\n\n================================ AMD_postorder:\n"));
alpar@1:         nels = 0 ;
alpar@1:         for (j = 0 ; j < nn ; j++)
alpar@1:         {
alpar@1:             if (Nv [j] > 0)
alpar@1:             {
alpar@1:                 AMD_DEBUG1 (( ""ID" :  nels "ID" npiv "ID" size "ID
alpar@1:                     " parent "ID" maxfr "ID"\n", j, nels,
alpar@1:                     Nv [j], Fsize [j], Parent [j], Fsize [j])) ;
alpar@1:                 /* this is an element */
alpar@1:                 /* dump the link list of children */
alpar@1:                 nchild = 0 ;
alpar@1:                 AMD_DEBUG1 (("    Children: ")) ;
alpar@1:                 for (ff = Child [j] ; ff != EMPTY ; ff = Sibling [ff])
alpar@1:                 {
alpar@1:                     AMD_DEBUG1 ((ID" ", ff)) ;
alpar@1:                     ASSERT (Parent [ff] == j) ;
alpar@1:                     nchild++ ;
alpar@1:                     ASSERT (nchild < nn) ;
alpar@1:                 }
alpar@1:                 AMD_DEBUG1 (("\n")) ;
alpar@1:                 parent = Parent [j] ;
alpar@1:                 if (parent != EMPTY)
alpar@1:                 {
alpar@1:                     ASSERT (Nv [parent] > 0) ;
alpar@1:                 }
alpar@1:                 nels++ ;
alpar@1:             }
alpar@1:         }
alpar@1:     }
alpar@1:     AMD_DEBUG1 (("\n\nGo through the children of each node, and put\n"
alpar@1:                  "the biggest child last in each list:\n")) ;
alpar@1: #endif
alpar@1: 
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1:     /* place the largest child last in the list of children for each node */
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1: 
alpar@1:     for (i = 0 ; i < nn ; i++)
alpar@1:     {
alpar@1:         if (Nv [i] > 0 && Child [i] != EMPTY)
alpar@1:         {
alpar@1: 
alpar@1: #ifndef NDEBUG
alpar@1:             Int nchild ;
alpar@1:             AMD_DEBUG1 (("Before partial sort, element "ID"\n", i)) ;
alpar@1:             nchild = 0 ;
alpar@1:             for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
alpar@1:             {
alpar@1:                 ASSERT (f >= 0 && f < nn) ;
alpar@1:                 AMD_DEBUG1 (("      f: "ID"  size: "ID"\n", f, Fsize [f])) ;
alpar@1:                 nchild++ ;
alpar@1:                 ASSERT (nchild <= nn) ;
alpar@1:             }
alpar@1: #endif
alpar@1: 
alpar@1:             /* find the biggest element in the child list */
alpar@1:             fprev = EMPTY ;
alpar@1:             maxfrsize = EMPTY ;
alpar@1:             bigfprev = EMPTY ;
alpar@1:             bigf = EMPTY ;
alpar@1:             for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
alpar@1:             {
alpar@1:                 ASSERT (f >= 0 && f < nn) ;
alpar@1:                 frsize = Fsize [f] ;
alpar@1:                 if (frsize >= maxfrsize)
alpar@1:                 {
alpar@1:                     /* this is the biggest seen so far */
alpar@1:                     maxfrsize = frsize ;
alpar@1:                     bigfprev = fprev ;
alpar@1:                     bigf = f ;
alpar@1:                 }
alpar@1:                 fprev = f ;
alpar@1:             }
alpar@1:             ASSERT (bigf != EMPTY) ;
alpar@1: 
alpar@1:             fnext = Sibling [bigf] ;
alpar@1: 
alpar@1:             AMD_DEBUG1 (("bigf "ID" maxfrsize "ID" bigfprev "ID" fnext "ID
alpar@1:                 " fprev " ID"\n", bigf, maxfrsize, bigfprev, fnext, fprev)) ;
alpar@1: 
alpar@1:             if (fnext != EMPTY)
alpar@1:             {
alpar@1:                 /* if fnext is EMPTY then bigf is already at the end of list */
alpar@1: 
alpar@1:                 if (bigfprev == EMPTY)
alpar@1:                 {
alpar@1:                     /* delete bigf from the element of the list */
alpar@1:                     Child [i] = fnext ;
alpar@1:                 }
alpar@1:                 else
alpar@1:                 {
alpar@1:                     /* delete bigf from the middle of the list */
alpar@1:                     Sibling [bigfprev] = fnext ;
alpar@1:                 }
alpar@1: 
alpar@1:                 /* put bigf at the end of the list */
alpar@1:                 Sibling [bigf] = EMPTY ;
alpar@1:                 ASSERT (Child [i] != EMPTY) ;
alpar@1:                 ASSERT (fprev != bigf) ;
alpar@1:                 ASSERT (fprev != EMPTY) ;
alpar@1:                 Sibling [fprev] = bigf ;
alpar@1:             }
alpar@1: 
alpar@1: #ifndef NDEBUG
alpar@1:             AMD_DEBUG1 (("After partial sort, element "ID"\n", i)) ;
alpar@1:             for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
alpar@1:             {
alpar@1:                 ASSERT (f >= 0 && f < nn) ;
alpar@1:                 AMD_DEBUG1 (("        "ID"  "ID"\n", f, Fsize [f])) ;
alpar@1:                 ASSERT (Nv [f] > 0) ;
alpar@1:                 nchild-- ;
alpar@1:             }
alpar@1:             ASSERT (nchild == 0) ;
alpar@1: #endif
alpar@1: 
alpar@1:         }
alpar@1:     }
alpar@1: 
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1:     /* postorder the assembly tree */
alpar@1:     /* --------------------------------------------------------------------- */
alpar@1: 
alpar@1:     for (i = 0 ; i < nn ; i++)
alpar@1:     {
alpar@1:         Order [i] = EMPTY ;
alpar@1:     }
alpar@1: 
alpar@1:     k = 0 ;
alpar@1: 
alpar@1:     for (i = 0 ; i < nn ; i++)
alpar@1:     {
alpar@1:         if (Parent [i] == EMPTY && Nv [i] > 0)
alpar@1:         {
alpar@1:             AMD_DEBUG1 (("Root of assembly tree "ID"\n", i)) ;
alpar@1:             k = AMD_post_tree (i, k, Child, Sibling, Order, Stack
alpar@1: #ifndef NDEBUG
alpar@1:                 , nn
alpar@1: #endif
alpar@1:                 ) ;
alpar@1:         }
alpar@1:     }
alpar@1: }