COIN-OR::LEMON - Graph Library

source: glpk-cmake/src/amd/amd_postorder.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: 6.8 KB
Line 
1/* ========================================================================= */
2/* === AMD_postorder ======================================================= */
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/* Perform a postordering (via depth-first search) of an assembly tree. */
13
14#include "amd_internal.h"
15
16GLOBAL void AMD_postorder
17(
18    /* inputs, not modified on output: */
19    Int nn,             /* nodes are in the range 0..nn-1 */
20    Int Parent [ ],     /* Parent [j] is the parent of j, or EMPTY if root */
21    Int Nv [ ],         /* Nv [j] > 0 number of pivots represented by node j,
22                         * or zero if j is not a node. */
23    Int Fsize [ ],      /* Fsize [j]: size of node j */
24
25    /* output, not defined on input: */
26    Int Order [ ],      /* output post-order */
27
28    /* workspaces of size nn: */
29    Int Child [ ],
30    Int Sibling [ ],
31    Int Stack [ ]
32)
33{
34    Int i, j, k, parent, frsize, f, fprev, maxfrsize, bigfprev, bigf, fnext ;
35
36    for (j = 0 ; j < nn ; j++)
37    {
38        Child [j] = EMPTY ;
39        Sibling [j] = EMPTY ;
40    }
41
42    /* --------------------------------------------------------------------- */
43    /* place the children in link lists - bigger elements tend to be last */
44    /* --------------------------------------------------------------------- */
45
46    for (j = nn-1 ; j >= 0 ; j--)
47    {
48        if (Nv [j] > 0)
49        {
50            /* this is an element */
51            parent = Parent [j] ;
52            if (parent != EMPTY)
53            {
54                /* place the element in link list of the children its parent */
55                /* bigger elements will tend to be at the end of the list */
56                Sibling [j] = Child [parent] ;
57                Child [parent] = j ;
58            }
59        }
60    }
61
62#ifndef NDEBUG
63    {
64        Int nels, ff, nchild ;
65        AMD_DEBUG1 (("\n\n================================ AMD_postorder:\n"));
66        nels = 0 ;
67        for (j = 0 ; j < nn ; j++)
68        {
69            if (Nv [j] > 0)
70            {
71                AMD_DEBUG1 (( ""ID" :  nels "ID" npiv "ID" size "ID
72                    " parent "ID" maxfr "ID"\n", j, nels,
73                    Nv [j], Fsize [j], Parent [j], Fsize [j])) ;
74                /* this is an element */
75                /* dump the link list of children */
76                nchild = 0 ;
77                AMD_DEBUG1 (("    Children: ")) ;
78                for (ff = Child [j] ; ff != EMPTY ; ff = Sibling [ff])
79                {
80                    AMD_DEBUG1 ((ID" ", ff)) ;
81                    ASSERT (Parent [ff] == j) ;
82                    nchild++ ;
83                    ASSERT (nchild < nn) ;
84                }
85                AMD_DEBUG1 (("\n")) ;
86                parent = Parent [j] ;
87                if (parent != EMPTY)
88                {
89                    ASSERT (Nv [parent] > 0) ;
90                }
91                nels++ ;
92            }
93        }
94    }
95    AMD_DEBUG1 (("\n\nGo through the children of each node, and put\n"
96                 "the biggest child last in each list:\n")) ;
97#endif
98
99    /* --------------------------------------------------------------------- */
100    /* place the largest child last in the list of children for each node */
101    /* --------------------------------------------------------------------- */
102
103    for (i = 0 ; i < nn ; i++)
104    {
105        if (Nv [i] > 0 && Child [i] != EMPTY)
106        {
107
108#ifndef NDEBUG
109            Int nchild ;
110            AMD_DEBUG1 (("Before partial sort, element "ID"\n", i)) ;
111            nchild = 0 ;
112            for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
113            {
114                ASSERT (f >= 0 && f < nn) ;
115                AMD_DEBUG1 (("      f: "ID"  size: "ID"\n", f, Fsize [f])) ;
116                nchild++ ;
117                ASSERT (nchild <= nn) ;
118            }
119#endif
120
121            /* find the biggest element in the child list */
122            fprev = EMPTY ;
123            maxfrsize = EMPTY ;
124            bigfprev = EMPTY ;
125            bigf = EMPTY ;
126            for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
127            {
128                ASSERT (f >= 0 && f < nn) ;
129                frsize = Fsize [f] ;
130                if (frsize >= maxfrsize)
131                {
132                    /* this is the biggest seen so far */
133                    maxfrsize = frsize ;
134                    bigfprev = fprev ;
135                    bigf = f ;
136                }
137                fprev = f ;
138            }
139            ASSERT (bigf != EMPTY) ;
140
141            fnext = Sibling [bigf] ;
142
143            AMD_DEBUG1 (("bigf "ID" maxfrsize "ID" bigfprev "ID" fnext "ID
144                " fprev " ID"\n", bigf, maxfrsize, bigfprev, fnext, fprev)) ;
145
146            if (fnext != EMPTY)
147            {
148                /* if fnext is EMPTY then bigf is already at the end of list */
149
150                if (bigfprev == EMPTY)
151                {
152                    /* delete bigf from the element of the list */
153                    Child [i] = fnext ;
154                }
155                else
156                {
157                    /* delete bigf from the middle of the list */
158                    Sibling [bigfprev] = fnext ;
159                }
160
161                /* put bigf at the end of the list */
162                Sibling [bigf] = EMPTY ;
163                ASSERT (Child [i] != EMPTY) ;
164                ASSERT (fprev != bigf) ;
165                ASSERT (fprev != EMPTY) ;
166                Sibling [fprev] = bigf ;
167            }
168
169#ifndef NDEBUG
170            AMD_DEBUG1 (("After partial sort, element "ID"\n", i)) ;
171            for (f = Child [i] ; f != EMPTY ; f = Sibling [f])
172            {
173                ASSERT (f >= 0 && f < nn) ;
174                AMD_DEBUG1 (("        "ID"  "ID"\n", f, Fsize [f])) ;
175                ASSERT (Nv [f] > 0) ;
176                nchild-- ;
177            }
178            ASSERT (nchild == 0) ;
179#endif
180
181        }
182    }
183
184    /* --------------------------------------------------------------------- */
185    /* postorder the assembly tree */
186    /* --------------------------------------------------------------------- */
187
188    for (i = 0 ; i < nn ; i++)
189    {
190        Order [i] = EMPTY ;
191    }
192
193    k = 0 ;
194
195    for (i = 0 ; i < nn ; i++)
196    {
197        if (Parent [i] == EMPTY && Nv [i] > 0)
198        {
199            AMD_DEBUG1 (("Root of assembly tree "ID"\n", i)) ;
200            k = AMD_post_tree (i, k, Child, Sibling, Order, Stack
201#ifndef NDEBUG
202                , nn
203#endif
204                ) ;
205        }
206    }
207}
Note: See TracBrowser for help on using the repository browser.