From feb8ebaeb76fa1c94de2dd7c4e5a0999b313f8c6 Mon Sep 17 00:00:00 2001
From: David Monniaux <david.monniaux@univ-grenoble-alpes.fr>
Date: Thu, 6 Jun 2019 20:09:32 +0200
Subject: GLPK 4.65

---
 test/monniaux/glpk-4.65/src/amd/amd_post_tree.c | 121 ++++++++++++++++++++++++
 1 file changed, 121 insertions(+)
 create mode 100644 test/monniaux/glpk-4.65/src/amd/amd_post_tree.c

(limited to 'test/monniaux/glpk-4.65/src/amd/amd_post_tree.c')

diff --git a/test/monniaux/glpk-4.65/src/amd/amd_post_tree.c b/test/monniaux/glpk-4.65/src/amd/amd_post_tree.c
new file mode 100644
index 00000000..bff0e263
--- /dev/null
+++ b/test/monniaux/glpk-4.65/src/amd/amd_post_tree.c
@@ -0,0 +1,121 @@
+/* ========================================================================= */
+/* === AMD_post_tree ======================================================= */
+/* ========================================================================= */
+
+/* ------------------------------------------------------------------------- */
+/* 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                          */
+/* ------------------------------------------------------------------------- */
+
+/* Post-ordering of a supernodal elimination tree.  */
+
+#include "amd_internal.h"
+
+GLOBAL Int AMD_post_tree
+(
+    Int root,                   /* root of the tree */
+    Int k,                      /* start numbering at k */
+    Int Child [ ],              /* input argument of size nn, undefined on
+                                 * output.  Child [i] is the head of a link
+                                 * list of all nodes that are children of node
+                                 * i in the tree. */
+    const Int Sibling [ ],      /* input argument of size nn, not modified.
+                                 * If f is a node in the link list of the
+                                 * children of node i, then Sibling [f] is the
+                                 * next child of node i.
+                                 */
+    Int Order [ ],              /* output order, of size nn.  Order [i] = k
+                                 * if node i is the kth node of the reordered
+                                 * tree. */
+    Int Stack [ ]               /* workspace of size nn */
+#ifndef NDEBUG
+    , Int nn                    /* nodes are in the range 0..nn-1. */
+#endif
+)
+{
+    Int f, head, h, i ;
+
+#if 0
+    /* --------------------------------------------------------------------- */
+    /* recursive version (Stack [ ] is not used): */
+    /* --------------------------------------------------------------------- */
+
+    /* this is simple, but can caouse stack overflow if nn is large */
+    i = root ;
+    for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
+    {
+        k = AMD_post_tree (f, k, Child, Sibling, Order, Stack, nn) ;
+    }
+    Order [i] = k++ ;
+    return (k) ;
+#endif
+
+    /* --------------------------------------------------------------------- */
+    /* non-recursive version, using an explicit stack */
+    /* --------------------------------------------------------------------- */
+
+    /* push root on the stack */
+    head = 0 ;
+    Stack [0] = root ;
+
+    while (head >= 0)
+    {
+        /* get head of stack */
+        ASSERT (head < nn) ;
+        i = Stack [head] ;
+        AMD_DEBUG1 (("head of stack "ID" \n", i)) ;
+        ASSERT (i >= 0 && i < nn) ;
+
+        if (Child [i] != EMPTY)
+        {
+            /* the children of i are not yet ordered */
+            /* push each child onto the stack in reverse order */
+            /* so that small ones at the head of the list get popped first */
+            /* and the biggest one at the end of the list gets popped last */
+            for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
+            {
+                head++ ;
+                ASSERT (head < nn) ;
+                ASSERT (f >= 0 && f < nn) ;
+            }
+            h = head ;
+            ASSERT (head < nn) ;
+            for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
+            {
+                ASSERT (h > 0) ;
+                Stack [h--] = f ;
+                AMD_DEBUG1 (("push "ID" on stack\n", f)) ;
+                ASSERT (f >= 0 && f < nn) ;
+            }
+            ASSERT (Stack [h] == i) ;
+
+            /* delete child list so that i gets ordered next time we see it */
+            Child [i] = EMPTY ;
+        }
+        else
+        {
+            /* the children of i (if there were any) are already ordered */
+            /* remove i from the stack and order it.  Front i is kth front */
+            head-- ;
+            AMD_DEBUG1 (("pop "ID" order "ID"\n", i, k)) ;
+            Order [i] = k++ ;
+            ASSERT (k <= nn) ;
+        }
+
+#ifndef NDEBUG
+        AMD_DEBUG1 (("\nStack:")) ;
+        for (h = head ; h >= 0 ; h--)
+        {
+            Int j = Stack [h] ;
+            AMD_DEBUG1 ((" "ID, j)) ;
+            ASSERT (j >= 0 && j < nn) ;
+        }
+        AMD_DEBUG1 (("\n\n")) ;
+        ASSERT (head < nn) ;
+#endif
+
+    }
+    return (k) ;
+}
-- 
cgit