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