COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/amd/amd_post_tree.c @ 1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 4.4 KB
Line 
1/* ========================================================================= */
2/* === AMD_post_tree ======================================================= */
3/* ========================================================================= */
4
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/* ------------------------------------------------------------------------- */
11
12/* Post-ordering of a supernodal elimination tree.  */
13
14#include "amd_internal.h"
15
16GLOBAL 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 ;
39
40#if 0
41    /* --------------------------------------------------------------------- */
42    /* recursive version (Stack [ ] is not used): */
43    /* --------------------------------------------------------------------- */
44
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
54
55    /* --------------------------------------------------------------------- */
56    /* non-recursive version, using an explicit stack */
57    /* --------------------------------------------------------------------- */
58
59    /* push root on the stack */
60    head = 0 ;
61    Stack [0] = root ;
62
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) ;
70
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) ;
93
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        }
106
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
118
119    }
120    return (k) ;
121}
Note: See TracBrowser for help on using the repository browser.