Amesos Package Browser (Single Doxygen Collection) Development
amesos_amd_l_postorder.c
Go to the documentation of this file.
00001 /* ========================================================================= */
00002 /* === AMD_postorder ======================================================= */
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 /* Perform a postordering (via depth-first search) of an assembly 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 void AMD_postorder
00020 (
00021     /* inputs, not modified on output: */
00022     Int nn,   /* nodes are in the range 0..nn-1 */
00023     Int Parent [ ], /* Parent [j] is the parent of j, or EMPTY if root */
00024     Int Nv [ ],   /* Nv [j] > 0 number of pivots represented by node j,
00025        * or zero if j is not a node. */
00026     Int Fsize [ ],  /* Fsize [j]: size of node j */
00027 
00028     /* output, not defined on input: */
00029     Int Order [ ],  /* output post-order */
00030 
00031     /* workspaces of size nn: */
00032     Int Child [ ],
00033     Int Sibling [ ],
00034     Int Stack [ ]
00035 )
00036 {
00037     Int i, j, k, parent, frsize, f, fprev, maxfrsize, bigfprev, bigf, fnext ;
00038 
00039     for (j = 0 ; j < nn ; j++)
00040     {
00041   Child [j] = EMPTY ;
00042   Sibling [j] = EMPTY ;
00043     }
00044 
00045     /* --------------------------------------------------------------------- */
00046     /* place the children in link lists - bigger elements tend to be last */
00047     /* --------------------------------------------------------------------- */
00048 
00049     for (j = nn-1 ; j >= 0 ; j--)
00050     {
00051   if (Nv [j] > 0)
00052   {
00053       /* this is an element */
00054       parent = Parent [j] ;
00055       if (parent != EMPTY)
00056       {
00057     /* place the element in link list of the children its parent */
00058     /* bigger elements will tend to be at the end of the list */
00059     Sibling [j] = Child [parent] ;
00060     Child [parent] = j ;
00061       }
00062   }
00063     }
00064 
00065 #ifndef NDEBUG
00066     {
00067   Int nels, ff, nchild ;
00068   AMD_DEBUG1 (("\n\n================================ AMD_postorder:\n"));
00069   nels = 0 ;
00070   for (j = 0 ; j < nn ; j++)
00071   {
00072       if (Nv [j] > 0)
00073       {
00074     AMD_DEBUG1 (( ""ID" :  nels "ID" npiv "ID" size "ID
00075         " parent "ID" maxfr "ID"\n", j, nels,
00076         Nv [j], Fsize [j], Parent [j], Fsize [j])) ;
00077     /* this is an element */
00078     /* dump the link list of children */
00079     nchild = 0 ;
00080     AMD_DEBUG1 (("    Children: ")) ;
00081     for (ff = Child [j] ; ff != EMPTY ; ff = Sibling [ff])
00082     {
00083         AMD_DEBUG1 ((ID" ", ff)) ;
00084         ASSERT (Parent [ff] == j) ;
00085         nchild++ ;
00086         ASSERT (nchild < nn) ;
00087     }
00088     AMD_DEBUG1 (("\n")) ;
00089     parent = Parent [j] ;
00090     if (parent != EMPTY)
00091     {
00092         ASSERT (Nv [parent] > 0) ;
00093     }
00094     nels++ ;
00095       }
00096   }
00097     }
00098     AMD_DEBUG1 (("\n\nGo through the children of each node, and put\n"
00099      "the biggest child last in each list:\n")) ;
00100 #endif
00101 
00102     /* --------------------------------------------------------------------- */
00103     /* place the largest child last in the list of children for each node */
00104     /* --------------------------------------------------------------------- */
00105 
00106     for (i = 0 ; i < nn ; i++)
00107     {
00108   if (Nv [i] > 0 && Child [i] != EMPTY)
00109   {
00110 
00111 #ifndef NDEBUG
00112       Int nchild ;
00113       AMD_DEBUG1 (("Before partial sort, element "ID"\n", i)) ;
00114       nchild = 0 ;
00115       for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
00116       {
00117     ASSERT (f >= 0 && f < nn) ;
00118     AMD_DEBUG1 (("      f: "ID"  size: "ID"\n", f, Fsize [f])) ;
00119     nchild++ ;
00120     ASSERT (nchild <= nn) ;
00121       }
00122 #endif
00123 
00124       /* find the biggest element in the child list */
00125       fprev = EMPTY ;
00126       maxfrsize = EMPTY ;
00127       bigfprev = EMPTY ;
00128       bigf = EMPTY ;
00129       for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
00130       {
00131     ASSERT (f >= 0 && f < nn) ;
00132     frsize = Fsize [f] ;
00133     if (frsize >= maxfrsize)
00134     {
00135         /* this is the biggest seen so far */
00136         maxfrsize = frsize ;
00137         bigfprev = fprev ;
00138         bigf = f ;
00139     }
00140     fprev = f ;
00141       }
00142       ASSERT (bigf != EMPTY) ;
00143 
00144       fnext = Sibling [bigf] ;
00145 
00146       AMD_DEBUG1 (("bigf "ID" maxfrsize "ID" bigfprev "ID" fnext "ID
00147     " fprev " ID"\n", bigf, maxfrsize, bigfprev, fnext, fprev)) ;
00148 
00149       if (fnext != EMPTY)
00150       {
00151     /* if fnext is EMPTY then bigf is already at the end of list */
00152 
00153     if (bigfprev == EMPTY)
00154     {
00155         /* delete bigf from the element of the list */
00156         Child [i] = fnext ;
00157     }
00158     else
00159     {
00160         /* delete bigf from the middle of the list */
00161         Sibling [bigfprev] = fnext ;
00162     }
00163 
00164     /* put bigf at the end of the list */
00165     Sibling [bigf] = EMPTY ;
00166     ASSERT (Child [i] != EMPTY) ;
00167     ASSERT (fprev != bigf) ;
00168     ASSERT (fprev != EMPTY) ;
00169     Sibling [fprev] = bigf ;
00170       }
00171 
00172 #ifndef NDEBUG
00173       AMD_DEBUG1 (("After partial sort, element "ID"\n", i)) ;
00174       for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
00175       {
00176     ASSERT (f >= 0 && f < nn) ;
00177     AMD_DEBUG1 (("        "ID"  "ID"\n", f, Fsize [f])) ;
00178     ASSERT (Nv [f] > 0) ;
00179     nchild-- ;
00180       }
00181       ASSERT (nchild == 0) ;
00182 #endif
00183 
00184   }
00185     }
00186 
00187     /* --------------------------------------------------------------------- */
00188     /* postorder the assembly tree */
00189     /* --------------------------------------------------------------------- */
00190 
00191     for (i = 0 ; i < nn ; i++)
00192     {
00193   Order [i] = EMPTY ;
00194     }
00195 
00196     k = 0 ;
00197 
00198     for (i = 0 ; i < nn ; i++)
00199     {
00200   if (Parent [i] == EMPTY && Nv [i] > 0)
00201   {
00202       AMD_DEBUG1 (("Root of assembly tree "ID"\n", i)) ;
00203       k = AMD_post_tree (i, k, Child, Sibling, Order, Stack
00204 #ifndef NDEBUG
00205     , nn
00206 #endif
00207     ) ;
00208   }
00209     }
00210 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines