Amesos Package Browser (Single Doxygen Collection) Development
amesos_cholmod_postorder.c
Go to the documentation of this file.
00001 /* ========================================================================== */
00002 /* === Cholesky/cholmod_postorder =========================================== */
00003 /* ========================================================================== */
00004 
00005 /* -----------------------------------------------------------------------------
00006  * CHOLMOD/Cholesky Module.  Copyright (C) 2005-2006, Timothy A. Davis
00007  * The CHOLMOD/Cholesky Module is licensed under Version 2.1 of the GNU
00008  * Lesser General Public License.  See lesser.txt for a text of the license.
00009  * CHOLMOD is also available under other licenses; contact authors for details.
00010  * http://www.cise.ufl.edu/research/sparse
00011  * -------------------------------------------------------------------------- */
00012 
00013 /* Compute the postorder of a tree. */
00014 
00015 #ifndef NCHOLESKY
00016 
00017 #include "amesos_cholmod_internal.h"
00018 #include "amesos_cholmod_cholesky.h"
00019 
00020 
00021 /* ========================================================================== */
00022 /* === dfs ================================================================== */
00023 /* ========================================================================== */
00024 
00025 /* The code below includes both a recursive and non-recursive depth-first-search
00026  * of a tree.  The recursive code is simpler, but can lead to stack overflow.
00027  * It is left here for reference, to understand what the non-recursive code
00028  * is computing.  To try the recursive version, uncomment the following
00029  * #define, or compile the code with -DRECURSIVE.  Be aware that stack
00030  * overflow may occur.
00031 #define RECURSIVE
00032  */
00033 
00034 #ifdef RECURSIVE
00035 
00036 /* recursive version: a working code for reference only, not actual use */
00037 
00038 static Int amesos_dfs     /* return the new value of k */
00039 (
00040     Int p,    /* start a DFS at node p */
00041     Int k,    /* start the node numbering at k */
00042     Int Post [ ], /* Post ordering, modified on output */
00043     Int Head [ ], /* Head [p] = youngest child of p; EMPTY on output */
00044     Int Next [ ], /* Next [j] = sibling of j; unmodified */
00045     Int Pstack [ ]  /* unused */
00046 )
00047 {
00048     Int j ;
00049     /* start a DFS at each child of node p */
00050     for (j = Head [p] ; j != EMPTY ; j = Next [j])
00051     {
00052   /* start a DFS at child node j */
00053   k = amesos_dfs (j, k, Post, Head, Next, Pstack) ;
00054     }
00055     Post [k++] = p ;  /* order node p as the kth node */
00056     Head [p] = EMPTY ;  /* link list p no longer needed */
00057     return (k) ;  /* the next node will be numbered k */
00058 }
00059 
00060 #else
00061 
00062 /* non-recursive version for actual use */
00063 
00064 static Int amesos_dfs   /* return the new value of k */
00065 (
00066     Int p,    /* start the DFS at a root node p */
00067     Int k,    /* start the node numbering at k */
00068     Int Post [ ], /* Post ordering, modified on output */
00069     Int Head [ ], /* Head [p] = youngest child of p; EMPTY on output */
00070     Int Next [ ], /* Next [j] = sibling of j; unmodified */
00071     Int Pstack [ ]  /* workspace of size n, undefined on input or output */
00072 )
00073 {
00074     Int j, phead ;
00075 
00076     /* put the root node on the stack */
00077     Pstack [0] = p ;
00078     phead = 0 ;
00079 
00080     /* while the stack is not empty, do: */
00081     while (phead >= 0)
00082     {
00083   /* grab the node p from top of the stack and get its youngest child j */
00084   p = Pstack [phead] ;
00085   j = Head [p] ;
00086   if (j == EMPTY)
00087   {
00088       /* all children of p ordered.  remove p from stack and order it */
00089       phead-- ;
00090       Post [k++] = p ;  /* order node p as the kth node */
00091   }
00092   else
00093   {
00094       /* leave p on the stack.  Start a DFS at child node j by putting
00095        * j on the stack and removing j from the list of children of p. */
00096       Head [p] = Next [j] ;
00097       Pstack [++phead] = j ;
00098   }
00099     }
00100     return (k) ;  /* the next node will be numbered k */
00101 }
00102 
00103 #endif
00104 
00105 /* ========================================================================== */
00106 /* === cholmod_postorder ==================================================== */
00107 /* ========================================================================== */
00108 
00109 /* Postorder a tree.  The tree is either an elimination tree (the output from
00110  * from cholmod_etree) or a component tree (from cholmod_nested_dissection).
00111  *
00112  * An elimination tree is a complete tree of n nodes with Parent [j] > j or
00113  * Parent [j] = EMPTY if j is a root.  On output Post [0..n-1] is a complete
00114  * permutation vector.
00115  *
00116  * A component tree is a subset of 0..n-1.  Parent [j] = -2 if node j is not
00117  * in the component tree.  Parent [j] = EMPTY if j is a root of the component
00118  * tree, and Parent [j] is in the range 0 to n-1 if j is in the component
00119  * tree but not a root.  On output, Post [k] is defined only for nodes in
00120  * the component tree.  Post [k] = j if node j is the kth node in the
00121  * postordered component tree, where k is in the range 0 to the number of
00122  * components minus 1.
00123  *
00124  * Node j is ignored and not included in the postorder if Parent [j] < EMPTY.
00125  *
00126  * As a result, check_parent (Parent, n,...) may fail on input, since
00127  * cholmod_check_parent assumes Parent is an elimination tree.  Similarly,
00128  * cholmod_check_perm (Post, ...) may fail on output, since Post is a partial
00129  * permutation if Parent is a component tree.
00130  *
00131  * An optional node weight can be given.  When starting a postorder at node j,
00132  * the children of j are ordered in decreasing order of their weight.
00133  * If no weights are given (Weight is NULL) then children are ordered in
00134  * decreasing order of their node number.  The weight of a node must be in the
00135  * range 0 to n-1.  Weights outside that range are silently converted to that
00136  * range (weights < 0 are treated as zero, and weights >= n are treated as n-1).
00137  *
00138  *
00139  * workspace: Head (n), Iwork (2*n)
00140  */
00141 
00142 UF_long CHOLMOD(postorder)  /* return # of nodes postordered */
00143 (
00144     /* ---- input ---- */
00145     Int *Parent,  /* size n. Parent [j] = p if p is the parent of j */
00146     size_t n,
00147     Int *Weight,  /* size n, optional. Weight [j] is weight of node j */
00148     /* ---- output --- */
00149     Int *Post,    /* size n. Post [k] = j is kth in postordered tree */
00150     /* --------------- */
00151     cholmod_common *Common
00152 )
00153 {
00154     Int *Head, *Next, *Pstack, *Iwork ;
00155     Int j, p, k, w, nextj ;
00156     size_t s ;
00157     int ok = TRUE ;
00158 
00159     /* ---------------------------------------------------------------------- */
00160     /* check inputs */
00161     /* ---------------------------------------------------------------------- */
00162 
00163     RETURN_IF_NULL_COMMON (EMPTY) ;
00164     RETURN_IF_NULL (Parent, EMPTY) ;
00165     RETURN_IF_NULL (Post, EMPTY) ;
00166     Common->status = CHOLMOD_OK ;
00167 
00168     /* ---------------------------------------------------------------------- */
00169     /* allocate workspace */
00170     /* ---------------------------------------------------------------------- */
00171 
00172     /* s = 2*n */
00173     s = CHOLMOD(mult_size_t) (n, 2, &ok) ;
00174     if (!ok)
00175     {
00176   ERROR (CHOLMOD_TOO_LARGE, "problem too large") ;
00177   return (EMPTY) ;
00178     }
00179 
00180     CHOLMOD(allocate_work) (n, s, 0, Common) ;
00181     if (Common->status < CHOLMOD_OK)
00182     {
00183   return (EMPTY) ;
00184     }
00185     ASSERT (CHOLMOD(dump_work) (TRUE, TRUE, 0, Common)) ;
00186 
00187     /* ---------------------------------------------------------------------- */
00188     /* get inputs */
00189     /* ---------------------------------------------------------------------- */
00190 
00191     Head  = Common->Head ;  /* size n+1, initially all EMPTY */
00192     Iwork = Common->Iwork ;
00193     Next  = Iwork ;   /* size n (i/i/l) */
00194     Pstack = Iwork + n ;  /* size n (i/i/l) */
00195 
00196     /* ---------------------------------------------------------------------- */
00197     /* construct a link list of children for each node */
00198     /* ---------------------------------------------------------------------- */
00199 
00200     if (Weight == NULL)
00201     {
00202 
00203   /* in reverse order so children are in ascending order in each list */
00204   for (j = n-1 ; j >= 0 ; j--)
00205   {
00206       p = Parent [j] ;
00207       if (p >= 0 && p < ((Int) n))
00208       {
00209     /* add j to the list of children for node p */
00210     Next [j] = Head [p] ;
00211     Head [p] = j ;
00212       }
00213   }
00214 
00215   /* Head [p] = j if j is the youngest (least-numbered) child of p */
00216   /* Next [j1] = j2 if j2 is the next-oldest sibling of j1 */
00217 
00218     }
00219     else
00220     {
00221 
00222   /* First, construct a set of link lists according to Weight.
00223    *
00224    * Whead [w] = j if node j is the first node in bucket w.
00225    * Next [j1] = j2 if node j2 follows j1 in a link list.
00226    */
00227 
00228   Int *Whead = Pstack ;     /* use Pstack as workspace for Whead [ */
00229 
00230   for (w = 0 ; w < ((Int) n) ; w++)
00231   {
00232       Whead [w] = EMPTY ;
00233   }
00234   /* do in forward order, so nodes that ties are ordered by node index */
00235   for (j = 0 ; j < ((Int) n) ; j++)
00236   {
00237       p = Parent [j] ;
00238       if (p >= 0 && p < ((Int) n))
00239       {
00240     w = Weight [j] ;
00241     w = MAX (0, w) ;
00242     w = MIN (w, ((Int) n) - 1) ;
00243     /* place node j at the head of link list for weight w */
00244     Next [j] = Whead [w] ;
00245     Whead [w] = j ;
00246       }
00247   }
00248 
00249   /* traverse weight buckets, placing each node in its parent's list */
00250   for (w = n-1 ; w >= 0 ; w--)
00251   {
00252       for (j = Whead [w] ; j != EMPTY ; j = nextj)
00253       {
00254     nextj = Next [j] ;
00255     /* put node j in the link list of its parent */
00256     p = Parent [j] ;
00257     ASSERT (p >= 0 && p < ((Int) n)) ;
00258     Next [j] = Head [p] ;
00259     Head [p] = j ;
00260       }
00261   }
00262 
00263   /* Whead no longer needed ] */
00264   /* Head [p] = j if j is the lightest child of p */
00265   /* Next [j1] = j2 if j2 is the next-heaviest sibling of j1 */
00266     }
00267 
00268     /* ---------------------------------------------------------------------- */
00269     /* start a DFS at each root node of the etree */
00270     /* ---------------------------------------------------------------------- */
00271 
00272     k = 0 ;
00273     for (j = 0 ; j < ((Int) n) ; j++)
00274     {
00275   if (Parent [j] == EMPTY)
00276   {
00277       /* j is the root of a tree; start a DFS here */
00278       k = amesos_dfs (j, k, Post, Head, Next, Pstack) ;
00279   }
00280     }
00281 
00282     /* this would normally be EMPTY already, unless Parent is invalid */
00283     for (j = 0 ; j < ((Int) n) ; j++)
00284     {
00285   Head [j] = EMPTY ;
00286     }
00287 
00288     PRINT1 (("postordered "ID" nodes\n", k)) ;
00289     ASSERT (CHOLMOD(dump_work) (TRUE, TRUE, 0, Common)) ;
00290     return (k) ;
00291 }
00292 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines