diff options
Diffstat (limited to 'test/monniaux/glpk-4.65/src/amd/amd_post_tree.c')
| -rw-r--r-- | test/monniaux/glpk-4.65/src/amd/amd_post_tree.c | 121 |
1 files changed, 121 insertions, 0 deletions
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) ; +} |