1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/amd/amd_postorder.c Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,207 @@
1.4 +/* ========================================================================= */
1.5 +/* === AMD_postorder ======================================================= */
1.6 +/* ========================================================================= */
1.7 +
1.8 +/* ------------------------------------------------------------------------- */
1.9 +/* AMD, Copyright (c) Timothy A. Davis, */
1.10 +/* Patrick R. Amestoy, and Iain S. Duff. See ../README.txt for License. */
1.11 +/* email: davis at cise.ufl.edu CISE Department, Univ. of Florida. */
1.12 +/* web: http://www.cise.ufl.edu/research/sparse/amd */
1.13 +/* ------------------------------------------------------------------------- */
1.14 +
1.15 +/* Perform a postordering (via depth-first search) of an assembly tree. */
1.16 +
1.17 +#include "amd_internal.h"
1.18 +
1.19 +GLOBAL void AMD_postorder
1.20 +(
1.21 + /* inputs, not modified on output: */
1.22 + Int nn, /* nodes are in the range 0..nn-1 */
1.23 + Int Parent [ ], /* Parent [j] is the parent of j, or EMPTY if root */
1.24 + Int Nv [ ], /* Nv [j] > 0 number of pivots represented by node j,
1.25 + * or zero if j is not a node. */
1.26 + Int Fsize [ ], /* Fsize [j]: size of node j */
1.27 +
1.28 + /* output, not defined on input: */
1.29 + Int Order [ ], /* output post-order */
1.30 +
1.31 + /* workspaces of size nn: */
1.32 + Int Child [ ],
1.33 + Int Sibling [ ],
1.34 + Int Stack [ ]
1.35 +)
1.36 +{
1.37 + Int i, j, k, parent, frsize, f, fprev, maxfrsize, bigfprev, bigf, fnext ;
1.38 +
1.39 + for (j = 0 ; j < nn ; j++)
1.40 + {
1.41 + Child [j] = EMPTY ;
1.42 + Sibling [j] = EMPTY ;
1.43 + }
1.44 +
1.45 + /* --------------------------------------------------------------------- */
1.46 + /* place the children in link lists - bigger elements tend to be last */
1.47 + /* --------------------------------------------------------------------- */
1.48 +
1.49 + for (j = nn-1 ; j >= 0 ; j--)
1.50 + {
1.51 + if (Nv [j] > 0)
1.52 + {
1.53 + /* this is an element */
1.54 + parent = Parent [j] ;
1.55 + if (parent != EMPTY)
1.56 + {
1.57 + /* place the element in link list of the children its parent */
1.58 + /* bigger elements will tend to be at the end of the list */
1.59 + Sibling [j] = Child [parent] ;
1.60 + Child [parent] = j ;
1.61 + }
1.62 + }
1.63 + }
1.64 +
1.65 +#ifndef NDEBUG
1.66 + {
1.67 + Int nels, ff, nchild ;
1.68 + AMD_DEBUG1 (("\n\n================================ AMD_postorder:\n"));
1.69 + nels = 0 ;
1.70 + for (j = 0 ; j < nn ; j++)
1.71 + {
1.72 + if (Nv [j] > 0)
1.73 + {
1.74 + AMD_DEBUG1 (( ""ID" : nels "ID" npiv "ID" size "ID
1.75 + " parent "ID" maxfr "ID"\n", j, nels,
1.76 + Nv [j], Fsize [j], Parent [j], Fsize [j])) ;
1.77 + /* this is an element */
1.78 + /* dump the link list of children */
1.79 + nchild = 0 ;
1.80 + AMD_DEBUG1 ((" Children: ")) ;
1.81 + for (ff = Child [j] ; ff != EMPTY ; ff = Sibling [ff])
1.82 + {
1.83 + AMD_DEBUG1 ((ID" ", ff)) ;
1.84 + ASSERT (Parent [ff] == j) ;
1.85 + nchild++ ;
1.86 + ASSERT (nchild < nn) ;
1.87 + }
1.88 + AMD_DEBUG1 (("\n")) ;
1.89 + parent = Parent [j] ;
1.90 + if (parent != EMPTY)
1.91 + {
1.92 + ASSERT (Nv [parent] > 0) ;
1.93 + }
1.94 + nels++ ;
1.95 + }
1.96 + }
1.97 + }
1.98 + AMD_DEBUG1 (("\n\nGo through the children of each node, and put\n"
1.99 + "the biggest child last in each list:\n")) ;
1.100 +#endif
1.101 +
1.102 + /* --------------------------------------------------------------------- */
1.103 + /* place the largest child last in the list of children for each node */
1.104 + /* --------------------------------------------------------------------- */
1.105 +
1.106 + for (i = 0 ; i < nn ; i++)
1.107 + {
1.108 + if (Nv [i] > 0 && Child [i] != EMPTY)
1.109 + {
1.110 +
1.111 +#ifndef NDEBUG
1.112 + Int nchild ;
1.113 + AMD_DEBUG1 (("Before partial sort, element "ID"\n", i)) ;
1.114 + nchild = 0 ;
1.115 + for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
1.116 + {
1.117 + ASSERT (f >= 0 && f < nn) ;
1.118 + AMD_DEBUG1 ((" f: "ID" size: "ID"\n", f, Fsize [f])) ;
1.119 + nchild++ ;
1.120 + ASSERT (nchild <= nn) ;
1.121 + }
1.122 +#endif
1.123 +
1.124 + /* find the biggest element in the child list */
1.125 + fprev = EMPTY ;
1.126 + maxfrsize = EMPTY ;
1.127 + bigfprev = EMPTY ;
1.128 + bigf = EMPTY ;
1.129 + for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
1.130 + {
1.131 + ASSERT (f >= 0 && f < nn) ;
1.132 + frsize = Fsize [f] ;
1.133 + if (frsize >= maxfrsize)
1.134 + {
1.135 + /* this is the biggest seen so far */
1.136 + maxfrsize = frsize ;
1.137 + bigfprev = fprev ;
1.138 + bigf = f ;
1.139 + }
1.140 + fprev = f ;
1.141 + }
1.142 + ASSERT (bigf != EMPTY) ;
1.143 +
1.144 + fnext = Sibling [bigf] ;
1.145 +
1.146 + AMD_DEBUG1 (("bigf "ID" maxfrsize "ID" bigfprev "ID" fnext "ID
1.147 + " fprev " ID"\n", bigf, maxfrsize, bigfprev, fnext, fprev)) ;
1.148 +
1.149 + if (fnext != EMPTY)
1.150 + {
1.151 + /* if fnext is EMPTY then bigf is already at the end of list */
1.152 +
1.153 + if (bigfprev == EMPTY)
1.154 + {
1.155 + /* delete bigf from the element of the list */
1.156 + Child [i] = fnext ;
1.157 + }
1.158 + else
1.159 + {
1.160 + /* delete bigf from the middle of the list */
1.161 + Sibling [bigfprev] = fnext ;
1.162 + }
1.163 +
1.164 + /* put bigf at the end of the list */
1.165 + Sibling [bigf] = EMPTY ;
1.166 + ASSERT (Child [i] != EMPTY) ;
1.167 + ASSERT (fprev != bigf) ;
1.168 + ASSERT (fprev != EMPTY) ;
1.169 + Sibling [fprev] = bigf ;
1.170 + }
1.171 +
1.172 +#ifndef NDEBUG
1.173 + AMD_DEBUG1 (("After partial sort, element "ID"\n", i)) ;
1.174 + for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
1.175 + {
1.176 + ASSERT (f >= 0 && f < nn) ;
1.177 + AMD_DEBUG1 ((" "ID" "ID"\n", f, Fsize [f])) ;
1.178 + ASSERT (Nv [f] > 0) ;
1.179 + nchild-- ;
1.180 + }
1.181 + ASSERT (nchild == 0) ;
1.182 +#endif
1.183 +
1.184 + }
1.185 + }
1.186 +
1.187 + /* --------------------------------------------------------------------- */
1.188 + /* postorder the assembly tree */
1.189 + /* --------------------------------------------------------------------- */
1.190 +
1.191 + for (i = 0 ; i < nn ; i++)
1.192 + {
1.193 + Order [i] = EMPTY ;
1.194 + }
1.195 +
1.196 + k = 0 ;
1.197 +
1.198 + for (i = 0 ; i < nn ; i++)
1.199 + {
1.200 + if (Parent [i] == EMPTY && Nv [i] > 0)
1.201 + {
1.202 + AMD_DEBUG1 (("Root of assembly tree "ID"\n", i)) ;
1.203 + k = AMD_post_tree (i, k, Child, Sibling, Order, Stack
1.204 +#ifndef NDEBUG
1.205 + , nn
1.206 +#endif
1.207 + ) ;
1.208 + }
1.209 + }
1.210 +}