1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/amd/amd_postorder.c	Sun Nov 06 20:59:10 2011 +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 +}