glpk-cmake: src/amd/amd_post_tree.c@4c8956a7bdf4

     1 /* ========================================================================= */

     2 /* === AMD_post_tree ======================================================= */

     3 /* ========================================================================= */

     5 /* ------------------------------------------------------------------------- */

     6 /* AMD, Copyright (c) Timothy A. Davis,                                      */

     7 /* Patrick R. Amestoy, and Iain S. Duff.  See ../README.txt for License.     */

     8 /* email: davis at cise.ufl.edu    CISE Department, Univ. of Florida.        */

     9 /* web: http://www.cise.ufl.edu/research/sparse/amd                          */

    10 /* ------------------------------------------------------------------------- */

    12 /* Post-ordering of a supernodal elimination tree.  */

    14 #include "amd_internal.h"

    16 GLOBAL Int AMD_post_tree

    17 (

    18     Int root,                   /* root of the tree */

    19     Int k,                      /* start numbering at k */

    20     Int Child [ ],              /* input argument of size nn, undefined on

    21                                  * output.  Child [i] is the head of a link

    22                                  * list of all nodes that are children of node

    23                                  * i in the tree. */

    24     const Int Sibling [ ],      /* input argument of size nn, not modified.

    25                                  * If f is a node in the link list of the

    26                                  * children of node i, then Sibling [f] is the

    27                                  * next child of node i.

    28                                  */

    29     Int Order [ ],              /* output order, of size nn.  Order [i] = k

    30                                  * if node i is the kth node of the reordered

    31                                  * tree. */

    32     Int Stack [ ]               /* workspace of size nn */

    33 #ifndef NDEBUG

    34     , Int nn                    /* nodes are in the range 0..nn-1. */

    35 #endif

    36 )

    37 {

    38     Int f, head, h, i ;

    40 #if 0

    41     /* --------------------------------------------------------------------- */

    42     /* recursive version (Stack [ ] is not used): */

    43     /* --------------------------------------------------------------------- */

    45     /* this is simple, but can caouse stack overflow if nn is large */

    46     i = root ;

    47     for (f = Child [i] ; f != EMPTY ; f = Sibling [f])

    48     {

    49         k = AMD_post_tree (f, k, Child, Sibling, Order, Stack, nn) ;

    50     }

    51     Order [i] = k++ ;

    52     return (k) ;

    53 #endif

    55     /* --------------------------------------------------------------------- */

    56     /* non-recursive version, using an explicit stack */

    57     /* --------------------------------------------------------------------- */

    59     /* push root on the stack */

    60     head = 0 ;

    61     Stack [0] = root ;

    63     while (head >= 0)

    64     {

    65         /* get head of stack */

    66         ASSERT (head < nn) ;

    67         i = Stack [head] ;

    68         AMD_DEBUG1 (("head of stack "ID" \n", i)) ;

    69         ASSERT (i >= 0 && i < nn) ;

    71         if (Child [i] != EMPTY)

    72         {

    73             /* the children of i are not yet ordered */

    74             /* push each child onto the stack in reverse order */

    75             /* so that small ones at the head of the list get popped first */

    76             /* and the biggest one at the end of the list gets popped last */

    77             for (f = Child [i] ; f != EMPTY ; f = Sibling [f])

    78             {

    79                 head++ ;

    80                 ASSERT (head < nn) ;

    81                 ASSERT (f >= 0 && f < nn) ;

    82             }

    83             h = head ;

    84             ASSERT (head < nn) ;

    85             for (f = Child [i] ; f != EMPTY ; f = Sibling [f])

    86             {

    87                 ASSERT (h > 0) ;

    88                 Stack [h--] = f ;

    89                 AMD_DEBUG1 (("push "ID" on stack\n", f)) ;

    90                 ASSERT (f >= 0 && f < nn) ;

    91             }

    92             ASSERT (Stack [h] == i) ;

    94             /* delete child list so that i gets ordered next time we see it */

    95             Child [i] = EMPTY ;

    96         }

    97         else

    98         {

    99             /* the children of i (if there were any) are already ordered */

   100             /* remove i from the stack and order it.  Front i is kth front */

   101             head-- ;

   102             AMD_DEBUG1 (("pop "ID" order "ID"\n", i, k)) ;

   103             Order [i] = k++ ;

   104             ASSERT (k <= nn) ;

   105         }

   107 #ifndef NDEBUG

   108         AMD_DEBUG1 (("\nStack:")) ;

   109         for (h = head ; h >= 0 ; h--)

   110         {

   111             Int j = Stack [h] ;

   112             AMD_DEBUG1 ((" "ID, j)) ;

   113             ASSERT (j >= 0 && j < nn) ;

   114         }

   115         AMD_DEBUG1 (("\n\n")) ;

   116         ASSERT (head < nn) ;

   117 #endif

   119     }

   120     return (k) ;

   121 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Sun, 05 Dec 2010 17:35:23 +0100
changeset 2	4c8956a7bdf4
permissions	-rw-r--r--