1 /* util.c */
2
3 #include "../Tree.h"
4
5 /*--------------------------------------------------------------------*/
6 /*
7 -------------------------------------------------
8 return the first vertex in a post-order traversal
9
10 created -- 95nov15, cca
11 -------------------------------------------------
12 */
13 int
Tree_postOTfirst(Tree * tree)14 Tree_postOTfirst (
15 Tree *tree
16 ) {
17 int v ;
18 /*
19 ---------------
20 check the input
21 ---------------
22 */
23 if ( tree == NULL || tree->n < 1 ) {
24 fprintf(stderr, "\n fatal error in Tree_postOTfirst(%p)"
25 "\n bad input\n", tree) ;
26 exit(-1) ;
27 }
28 /*
29 ----------------------
30 find the leftmost leaf
31 ----------------------
32 */
33 if ( (v = tree->root) != -1 ) {
34 while ( tree->fch[v] != -1 ) {
35 v = tree->fch[v] ;
36 }
37 }
38 return(v) ; }
39
40 /*--------------------------------------------------------------------*/
41 /*
42 ----------------------------------------------------------
43 return the vertex that follows v in a post-order traversal
44 ----------------------------------------------------------
45 */
46 int
Tree_postOTnext(Tree * tree,int v)47 Tree_postOTnext (
48 Tree *tree,
49 int v
50 ) {
51 /*
52 ---------------
53 check the input
54 ---------------
55 */
56 if ( tree == NULL || tree->n < 1 || v < 0 || v >= tree->n ) {
57 fprintf(stderr, "\n fatal error in Tree_postOTnext(%p,%d)"
58 "\n bad input\n", tree, v) ;
59 exit(-1) ;
60 }
61 /*
62 ---------------------------------------------------
63 find leftmost leaf of sibling (if exists) or parent
64 ---------------------------------------------------
65 */
66 if ( tree->sib[v] != -1 ) {
67 v = tree->sib[v] ;
68 while ( tree->fch[v] != -1 ) {
69 v = tree->fch[v] ;
70 }
71 } else {
72 v = tree->par[v] ;
73 }
74 return(v) ; }
75
76 /*--------------------------------------------------------------------*/
77 /*
78 ------------------------------------------------
79 return the first vertex in a pre-order traversal
80
81 created -- 95nov15, cca
82 ------------------------------------------------
83 */
84 int
Tree_preOTfirst(Tree * tree)85 Tree_preOTfirst (
86 Tree *tree
87 ) {
88 /*
89 ---------------
90 check the input
91 ---------------
92 */
93 if ( tree == NULL || tree->n < 1 ) {
94 fprintf(stderr, "\n fatal error in Tree_preOTfirst(%p)"
95 "\n bad input\n", tree) ;
96 exit(-1) ;
97 }
98 return(tree->root) ; }
99
100 /*--------------------------------------------------------------------*/
101 /*
102 ---------------------------------------------------------
103 return the vertex that follows v in a pre-order traversal
104
105 created -- 95nov15, cca
106 ---------------------------------------------------------
107 */
108 int
Tree_preOTnext(Tree * tree,int v)109 Tree_preOTnext (
110 Tree *tree,
111 int v
112 ) {
113 /*
114 ---------------
115 check the input
116 ---------------
117 */
118 if ( tree == NULL || tree->n < 1 || v < 0 || v >= tree->n ) {
119 fprintf(stderr, "\n fatal error in Tree_preOTnext(%p,%d)"
120 "\n bad input\n", tree, v) ;
121 exit(-1) ;
122 }
123 /*
124 -------------------------------------
125 find the next vertex in the traversal
126 -------------------------------------
127 */
128 if ( tree->fch[v] != -1 ) {
129 v = tree->fch[v] ;
130 } else {
131 while ( tree->sib[v] == -1 && tree->par[v] != -1 ) {
132 v = tree->par[v] ;
133 }
134 v = tree->sib[v] ;
135 }
136 return(v) ; }
137
138 /*--------------------------------------------------------------------*/
139 /*
140 ---------------------------------------
141 return the number of leaves in the tree
142
143 created -- 95nov15, cca
144 ---------------------------------------
145 */
146 int
Tree_nleaves(Tree * tree)147 Tree_nleaves (
148 Tree *tree
149 ) {
150 int nleaf, v ;
151 /*
152 ---------------
153 check the input
154 ---------------
155 */
156 if ( tree == NULL || tree->n < 1 ) {
157 fprintf(stderr, "\n fatal error in Tree_nleaves(%p)"
158 "\n bad input\n", tree) ;
159 exit(-1) ;
160 }
161
162 nleaf = 0 ;
163 for ( v = 0 ; v < tree->n ; v++ ) {
164 if ( tree->fch[v] == -1 ) {
165 nleaf++ ;
166 }
167 }
168 return(nleaf) ; }
169
170 /*--------------------------------------------------------------------*/
171 /*
172 -----------------------------------------------
173 return the number of roots of the tree (forest)
174
175 created -- 95nov15, cca
176 -----------------------------------------------
177 */
178 int
Tree_nroots(Tree * tree)179 Tree_nroots (
180 Tree *tree
181 ) {
182 int nroot, v ;
183 /*
184 ---------------
185 check the input
186 ---------------
187 */
188 if ( tree == NULL || tree->n < 1 ) {
189 fprintf(stderr, "\n fatal error in Tree_nroots(%p)"
190 "\n bad input\n", tree) ;
191 exit(-1) ;
192 }
193
194 nroot = 0 ;
195 for ( v = 0 ; v < tree->n ;v++ ) {
196 if ( tree->par[v] == -1 ) {
197 nroot++ ;
198 }
199 }
200 return(nroot) ; }
201
202 /*--------------------------------------------------------------------*/
203 /*
204 -----------------------------------------
205 return the number of children of a vertex
206
207 created -- 95nov15, cca
208 modified -- 96jan07, cca
209 v checked to be valid
210 -----------------------------------------
211 */
212 int
Tree_nchild(Tree * tree,int v)213 Tree_nchild (
214 Tree *tree,
215 int v
216 ) {
217 int nchild, w ;
218 /*
219 ---------------
220 check the input
221 ---------------
222 */
223 if ( tree == NULL || tree->n < 1 ) {
224 fprintf(stderr, "\n fatal error in Tree_nchild(%p,%d)"
225 "\n bad input\n", tree, v) ;
226 exit(-1) ;
227 }
228 if ( v < 0 || v >= tree->n ) {
229 fprintf(stderr, "\n fatal error in Tree_nchild(%p,%d)"
230 "\n v = %d, size = %d\n", tree, v, v, tree->n) ;
231 exit(-1) ;
232 }
233 nchild = 0 ;
234 for ( w = tree->fch[v] ; w != -1 ; w = tree->sib[w] ) {
235 nchild++ ;
236 }
237 return(nchild) ; }
238
239 /*--------------------------------------------------------------------*/
240 /*
241 -------------------------------------------
242 this method returns an IV object that holds
243 the number of children for the tree nodes.
244
245 created -- 96dec18, cca
246 -------------------------------------------
247 */
248 IV *
Tree_nchildIV(Tree * tree)249 Tree_nchildIV (
250 Tree *tree
251 ) {
252 int n, v, w ;
253 int *nchild, *par ;
254 IV *nchildIV ;
255 /*
256 ---------------
257 check the input
258 ---------------
259 */
260 if ( tree == NULL || (n = tree->n) < 1 ) {
261 fprintf(stderr, "\n fatal error in Tree_nchildIV(%p)"
262 "\n bad input\n", tree) ;
263 exit(-1) ;
264 }
265 nchildIV = IV_new() ;
266 IV_init(nchildIV, n, NULL) ;
267 IV_fill(nchildIV, 0) ;
268 par = tree->par ;
269 nchild = IV_entries(nchildIV) ;
270 for ( v = 0 ; v < n ; v++ ) {
271 if ( (w = par[v]) != -1 ) {
272 nchild[w]++ ;
273 }
274 }
275
276 return(nchildIV) ; }
277
278 /*--------------------------------------------------------------------*/
279 /*
280 -----------------------------
281 return the height of the tree
282
283 created -- 96aug23, cca
284 -----------------------------
285 */
286 int
Tree_height(Tree * tree)287 Tree_height (
288 Tree *tree
289 ) {
290 int u, v, vheight ;
291 int *heights ;
292 /*
293 ---------------
294 check the input
295 ---------------
296 */
297 if ( tree == NULL || tree->n < 1 ) {
298 fprintf(stderr, "\n fatal error in Tree_height(%p)"
299 "\n bad input\n", tree) ;
300 exit(-1) ;
301 }
302 heights = IVinit(tree->n, 1) ;
303 for ( v = Tree_postOTfirst(tree) ;
304 v != -1 ;
305 v = Tree_postOTnext(tree, v) ) {
306 if ( (u = tree->fch[v]) == -1 ) {
307 vheight = 1 ;
308 } else {
309 vheight = heights[u] ;
310 for ( u = tree->sib[u] ; u != -1 ; u = tree->sib[u] ) {
311 if ( vheight < heights[u] ) {
312 vheight = heights[u] ;
313 }
314 }
315 vheight++ ;
316 }
317 heights[v] = vheight ;
318 }
319 v = tree->root ;
320 vheight = heights[v] ;
321 for ( v = tree->sib[v] ; v != -1 ; v = tree->sib[v] ) {
322 if ( vheight < heights[v] ) {
323 vheight = heights[v] ;
324 }
325 }
326 IVfree(heights) ;
327
328 return(vheight) ; }
329
330 /*--------------------------------------------------------------------*/
331 /*
332 -------------------------------------------------------------
333 return the maximum number of children of any node in the tree
334
335 created -- 96sep05, cca
336 -------------------------------------------------------------
337 */
338 int
Tree_maxNchild(Tree * tree)339 Tree_maxNchild (
340 Tree *tree
341 ) {
342 int maxnchild, n, nchild, u, v ;
343 int *fch, *sib ;
344 /*
345 ---------------
346 check the input
347 ---------------
348 */
349 if ( tree == NULL ) {
350 fprintf(stderr, "\n fatal error in Tree_maxNchild(%p)"
351 "\n bad input\n", tree) ;
352 exit(-1) ;
353 }
354 n = tree->n ;
355 fch = tree->fch ;
356 sib = tree->sib ;
357 maxnchild = 0 ;
358 for ( v = 0 ; v < n ; v++ ) {
359 for ( u = fch[v], nchild = 0 ; u != -1 ; u = sib[u] ) {
360 nchild++ ;
361 }
362 if ( maxnchild < nchild ) {
363 maxnchild = nchild ;
364 }
365 }
366 return(maxnchild) ; }
367
368 /*--------------------------------------------------------------------*/
369 /*
370 ---------------------------------------------
371 return the number of bytes used by the object
372 ---------------------------------------------
373 */
374 int
Tree_sizeOf(Tree * tree)375 Tree_sizeOf (
376 Tree *tree
377 ) {
378 int nbytes ;
379 /*
380 ---------------
381 check the input
382 ---------------
383 */
384 if ( tree == NULL ) {
385 fprintf(stderr, "\n fatal error in Tree_sizeOf(%p)"
386 "\n bad input\n", tree) ;
387 exit(-1) ;
388 }
389
390 nbytes = sizeof(struct _Tree) + 3*tree->n*sizeof(int) ;
391
392 return(nbytes) ; }
393
394 /*--------------------------------------------------------------------*/
395