diff -r d59bea55db9b -r c445c931472f src/amd/amd_postorder.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/amd/amd_postorder.c	Mon Dec 06 13:09:21 2010 +0100
@@ -0,0 +1,207 @@
+/* ========================================================================= */
+/* === AMD_postorder ======================================================= */
+/* ========================================================================= */
+
+/* ------------------------------------------------------------------------- */
+/* AMD, Copyright (c) Timothy A. Davis,                                      */
+/* Patrick R. Amestoy, and Iain S. Duff.  See ../README.txt for License.     */
+/* email: davis at cise.ufl.edu    CISE Department, Univ. of Florida.        */
+/* web: http://www.cise.ufl.edu/research/sparse/amd                          */
+/* ------------------------------------------------------------------------- */
+
+/* Perform a postordering (via depth-first search) of an assembly tree. */
+
+#include "amd_internal.h"
+
+GLOBAL void AMD_postorder
+(
+    /* inputs, not modified on output: */
+    Int nn,             /* nodes are in the range 0..nn-1 */
+    Int Parent [ ],     /* Parent [j] is the parent of j, or EMPTY if root */
+    Int Nv [ ],         /* Nv [j] > 0 number of pivots represented by node j,
+                         * or zero if j is not a node. */
+    Int Fsize [ ],      /* Fsize [j]: size of node j */
+
+    /* output, not defined on input: */
+    Int Order [ ],      /* output post-order */
+
+    /* workspaces of size nn: */
+    Int Child [ ],
+    Int Sibling [ ],
+    Int Stack [ ]
+)
+{
+    Int i, j, k, parent, frsize, f, fprev, maxfrsize, bigfprev, bigf, fnext ;
+
+    for (j = 0 ; j < nn ; j++)
+    {
+        Child [j] = EMPTY ;
+        Sibling [j] = EMPTY ;
+    }
+
+    /* --------------------------------------------------------------------- */
+    /* place the children in link lists - bigger elements tend to be last */
+    /* --------------------------------------------------------------------- */
+
+    for (j = nn-1 ; j >= 0 ; j--)
+    {
+        if (Nv [j] > 0)
+        {
+            /* this is an element */
+            parent = Parent [j] ;
+            if (parent != EMPTY)
+            {
+                /* place the element in link list of the children its parent */
+                /* bigger elements will tend to be at the end of the list */
+                Sibling [j] = Child [parent] ;
+                Child [parent] = j ;
+            }
+        }
+    }
+
+#ifndef NDEBUG
+    {
+        Int nels, ff, nchild ;
+        AMD_DEBUG1 (("\n\n================================ AMD_postorder:\n"));
+        nels = 0 ;
+        for (j = 0 ; j < nn ; j++)
+        {
+            if (Nv [j] > 0)
+            {
+                AMD_DEBUG1 (( ""ID" :  nels "ID" npiv "ID" size "ID
+                    " parent "ID" maxfr "ID"\n", j, nels,
+                    Nv [j], Fsize [j], Parent [j], Fsize [j])) ;
+                /* this is an element */
+                /* dump the link list of children */
+                nchild = 0 ;
+                AMD_DEBUG1 (("    Children: ")) ;
+                for (ff = Child [j] ; ff != EMPTY ; ff = Sibling [ff])
+                {
+                    AMD_DEBUG1 ((ID" ", ff)) ;
+                    ASSERT (Parent [ff] == j) ;
+                    nchild++ ;
+                    ASSERT (nchild < nn) ;
+                }
+                AMD_DEBUG1 (("\n")) ;
+                parent = Parent [j] ;
+                if (parent != EMPTY)
+                {
+                    ASSERT (Nv [parent] > 0) ;
+                }
+                nels++ ;
+            }
+        }
+    }
+    AMD_DEBUG1 (("\n\nGo through the children of each node, and put\n"
+                 "the biggest child last in each list:\n")) ;
+#endif
+
+    /* --------------------------------------------------------------------- */
+    /* place the largest child last in the list of children for each node */
+    /* --------------------------------------------------------------------- */
+
+    for (i = 0 ; i < nn ; i++)
+    {
+        if (Nv [i] > 0 && Child [i] != EMPTY)
+        {
+
+#ifndef NDEBUG
+            Int nchild ;
+            AMD_DEBUG1 (("Before partial sort, element "ID"\n", i)) ;
+            nchild = 0 ;
+            for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
+            {
+                ASSERT (f >= 0 && f < nn) ;
+                AMD_DEBUG1 (("      f: "ID"  size: "ID"\n", f, Fsize [f])) ;
+                nchild++ ;
+                ASSERT (nchild <= nn) ;
+            }
+#endif
+
+            /* find the biggest element in the child list */
+            fprev = EMPTY ;
+            maxfrsize = EMPTY ;
+            bigfprev = EMPTY ;
+            bigf = EMPTY ;
+            for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
+            {
+                ASSERT (f >= 0 && f < nn) ;
+                frsize = Fsize [f] ;
+                if (frsize >= maxfrsize)
+                {
+                    /* this is the biggest seen so far */
+                    maxfrsize = frsize ;
+                    bigfprev = fprev ;
+                    bigf = f ;
+                }
+                fprev = f ;
+            }
+            ASSERT (bigf != EMPTY) ;
+
+            fnext = Sibling [bigf] ;
+
+            AMD_DEBUG1 (("bigf "ID" maxfrsize "ID" bigfprev "ID" fnext "ID
+                " fprev " ID"\n", bigf, maxfrsize, bigfprev, fnext, fprev)) ;
+
+            if (fnext != EMPTY)
+            {
+                /* if fnext is EMPTY then bigf is already at the end of list */
+
+                if (bigfprev == EMPTY)
+                {
+                    /* delete bigf from the element of the list */
+                    Child [i] = fnext ;
+                }
+                else
+                {
+                    /* delete bigf from the middle of the list */
+                    Sibling [bigfprev] = fnext ;
+                }
+
+                /* put bigf at the end of the list */
+                Sibling [bigf] = EMPTY ;
+                ASSERT (Child [i] != EMPTY) ;
+                ASSERT (fprev != bigf) ;
+                ASSERT (fprev != EMPTY) ;
+                Sibling [fprev] = bigf ;
+            }
+
+#ifndef NDEBUG
+            AMD_DEBUG1 (("After partial sort, element "ID"\n", i)) ;
+            for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
+            {
+                ASSERT (f >= 0 && f < nn) ;
+                AMD_DEBUG1 (("        "ID"  "ID"\n", f, Fsize [f])) ;
+                ASSERT (Nv [f] > 0) ;
+                nchild-- ;
+            }
+            ASSERT (nchild == 0) ;
+#endif
+
+        }
+    }
+
+    /* --------------------------------------------------------------------- */
+    /* postorder the assembly tree */
+    /* --------------------------------------------------------------------- */
+
+    for (i = 0 ; i < nn ; i++)
+    {
+        Order [i] = EMPTY ;
+    }
+
+    k = 0 ;
+
+    for (i = 0 ; i < nn ; i++)
+    {
+        if (Parent [i] == EMPTY && Nv [i] > 0)
+        {
+            AMD_DEBUG1 (("Root of assembly tree "ID"\n", i)) ;
+            k = AMD_post_tree (i, k, Child, Sibling, Order, Stack
+#ifndef NDEBUG
+                , nn
+#endif
+                ) ;
+        }
+    }
+}