Amesos Package Browser (Single Doxygen Collection) Development
amesos_amd_l_post_tree.c
Go to the documentation of this file.
00001 /* ========================================================================= */
00002 /* === AMD_post_tree ======================================================= */
00003 /* ========================================================================= */
00004 
00005 /* ------------------------------------------------------------------------- */
00006 /* AMD, Copyright (c) Timothy A. Davis,              */
00007 /* Patrick R. Amestoy, and Iain S. Duff.  See ../README.txt for License.     */
00008 /* email: davis at cise.ufl.edu    CISE Department, Univ. of Florida.        */
00009 /* web: http://www.cise.ufl.edu/research/sparse/amd                          */
00010 /* ------------------------------------------------------------------------- */
00011 
00012 /* Post-ordering of a supernodal elimination tree.  */
00013 
00014 /* This file should make the long int version of AMD */
00015 #define DLONG 1
00016 
00017 #include "amesos_amd_internal.h"
00018 
00019 GLOBAL Int AMD_post_tree
00020 (
00021     Int root,     /* root of the tree */
00022     Int k,      /* start numbering at k */
00023     Int Child [ ],    /* input argument of size nn, undefined on
00024          * output.  Child [i] is the head of a link
00025          * list of all nodes that are children of node
00026          * i in the tree. */
00027     const Int Sibling [ ],  /* input argument of size nn, not modified.
00028          * If f is a node in the link list of the
00029          * children of node i, then Sibling [f] is the
00030          * next child of node i.
00031          */
00032     Int Order [ ],    /* output order, of size nn.  Order [i] = k
00033          * if node i is the kth node of the reordered
00034          * tree. */
00035     Int Stack [ ]   /* workspace of size nn */
00036 #ifndef NDEBUG
00037     , Int nn      /* nodes are in the range 0..nn-1. */
00038 #endif
00039 )
00040 {
00041     Int f, head, h, i ;
00042 
00043 #if 0
00044     /* --------------------------------------------------------------------- */
00045     /* recursive version (Stack [ ] is not used): */
00046     /* --------------------------------------------------------------------- */
00047 
00048     /* this is simple, but can caouse stack overflow if nn is large */
00049     i = root ;
00050     for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
00051     {
00052   k = AMD_post_tree (f, k, Child, Sibling, Order, Stack, nn) ;
00053     }
00054     Order [i] = k++ ;
00055     return (k) ;
00056 #endif
00057 
00058     /* --------------------------------------------------------------------- */
00059     /* non-recursive version, using an explicit stack */
00060     /* --------------------------------------------------------------------- */
00061 
00062     /* push root on the stack */
00063     head = 0 ;
00064     Stack [0] = root ;
00065 
00066     while (head >= 0)
00067     {
00068   /* get head of stack */
00069   ASSERT (head < nn) ;
00070   i = Stack [head] ;
00071   AMD_DEBUG1 (("head of stack "ID" \n", i)) ;
00072   ASSERT (i >= 0 && i < nn) ;
00073 
00074   if (Child [i] != EMPTY)
00075   {
00076       /* the children of i are not yet ordered */
00077       /* push each child onto the stack in reverse order */
00078       /* so that small ones at the head of the list get popped first */
00079       /* and the biggest one at the end of the list gets popped last */
00080       for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
00081       {
00082     head++ ;
00083     ASSERT (head < nn) ;
00084     ASSERT (f >= 0 && f < nn) ;
00085       }
00086       h = head ;
00087       ASSERT (head < nn) ;
00088       for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
00089       {
00090     ASSERT (h > 0) ;
00091     Stack [h--] = f ;
00092     AMD_DEBUG1 (("push "ID" on stack\n", f)) ;
00093     ASSERT (f >= 0 && f < nn) ;
00094       }
00095       ASSERT (Stack [h] == i) ;
00096 
00097       /* delete child list so that i gets ordered next time we see it */
00098       Child [i] = EMPTY ;
00099   }
00100   else
00101   {
00102       /* the children of i (if there were any) are already ordered */
00103       /* remove i from the stack and order it.  Front i is kth front */
00104       head-- ;
00105       AMD_DEBUG1 (("pop "ID" order "ID"\n", i, k)) ;
00106       Order [i] = k++ ;
00107       ASSERT (k <= nn) ;
00108   }
00109 
00110 #ifndef NDEBUG
00111   AMD_DEBUG1 (("\nStack:")) ;
00112   for (h = head ; h >= 0 ; h--)
00113   {
00114       Int j = Stack [h] ;
00115       AMD_DEBUG1 ((" "ID, j)) ;
00116       ASSERT (j >= 0 && j < nn) ;
00117   }
00118   AMD_DEBUG1 (("\n\n")) ;
00119   ASSERT (head < nn) ;
00120 #endif
00121 
00122     }
00123     return (k) ;
00124 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines