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