1 /* compress.c */
2
3 #include "../Tree.h"
4
5 /*--------------------------------------------------------------------*/
6 /*
7 --------------------------------------------
8 create and return an IV object that contains
9 the map from vertices to fundamental chains.
10
11 return value -- # of fundamental chains
12
13 created -- 96jun23, cca
14 -------------------------------------------
15 */
16 IV *
Tree_fundChainMap(Tree * tree)17 Tree_fundChainMap (
18 Tree *tree
19 ) {
20 int nfc, u, v ;
21 int *map ;
22 IV *mapIV ;
23 /*
24 ---------------
25 check the input
26 ---------------
27 */
28 if ( tree == NULL || tree->n <= 0 ) {
29 fprintf(stderr, "\n fatal error in Tree_fundChainMap(%p)"
30 "\n bad input\n", tree) ;
31 exit(-1) ;
32 }
33 mapIV = IV_new() ;
34 IV_init(mapIV, tree->n, NULL) ;
35 map = IV_entries(mapIV) ;
36 for ( v = Tree_postOTfirst(tree), nfc = 0 ;
37 v != -1 ;
38 v = Tree_postOTnext(tree, v) ) {
39 if ( (u = tree->fch[v]) == -1 || tree->sib[u] != -1 ) {
40 /*
41 --------------------
42 v starts a new chain
43 --------------------
44 */
45 map[v] = nfc++ ;
46 } else {
47 /*
48 -----------------------------------------------
49 v belongs in the same chain as its only child u
50 -----------------------------------------------
51 */
52 map[v] = map[u] ;
53 }
54 }
55 return(mapIV) ; }
56
57 /*--------------------------------------------------------------------*/
58 /*
59 -----------------------------------------------------------------
60 compress a tree based on a map from old vertices to new vertices.
61 the restriction on the map is that the set {u | map[u] = U} must
62 be connected for all U.
63
64 created -- 95nov15, cca
65 modified -- 96jan04, cca
66 bug fixed, N computed incorrectly
67 modified -- 96jun23, cca
68 in calling sequence, int map[] converted to IV *mapIV
69 -----------------------------------------------------------------
70 */
71 Tree *
Tree_compress(Tree * tree,IV * mapIV)72 Tree_compress (
73 Tree *tree,
74 IV *mapIV
75 ) {
76 int n, N, u, U, v, V ;
77 int *head, *link, *map ;
78 Tree *tree2 ;
79 /*
80 ---------------
81 check the input
82 ---------------
83 */
84 if ( tree == NULL
85 || (n = tree->n) <= 0
86 || mapIV == NULL
87 || n != IV_size(mapIV)
88 || (map = IV_entries(mapIV)) == NULL ) {
89 fprintf(stderr, "\n fatal error in Tree_compress(%p,%p)"
90 "\n bad input\n", tree, mapIV) ;
91 exit(-1) ;
92 }
93 /*
94 -----------------------
95 initialize the new tree
96 -----------------------
97 */
98 N = 1 + IV_max(mapIV) ;
99 tree2 = Tree_new() ;
100 Tree_init1(tree2, N) ;
101 /*
102 -----------------------------------------------------------
103 get the head/link construct to map old nodes into new nodes
104 -----------------------------------------------------------
105 */
106 head = IVinit(N, -1) ;
107 link = IVinit(n, -1) ;
108 for ( v = 0 ; v < n ; v++ ) {
109 if ( (V = map[v]) < 0 || V >= N ) {
110 fprintf(stderr, "\n fatal error in Tree_compress(%p,%p)"
111 "\n map[%d] = %d, N = %d\n", tree, map, v, V, N) ;
112 exit(-1) ;
113 }
114 link[v] = head[V] ;
115 head[V] = v ;
116 }
117 /*
118 ---------------------
119 fill the tree vectors
120 ---------------------
121 */
122 for ( U = 0 ; U < N ; U++ ) {
123 for ( u = head[U] ; u != -1 ; u = link[u] ) {
124 if ( (v = tree->par[u]) == -1 ) {
125 tree2->par[U] = -1 ;
126 break ;
127 } else if ( (V = map[v]) != U ) {
128 tree2->par[U] = V ;
129 break ;
130 }
131 }
132 }
133 Tree_setFchSibRoot(tree2) ;
134 /*
135 ------------------------
136 free the working storage
137 ------------------------
138 */
139 IVfree(head) ;
140 IVfree(link) ;
141
142 return(tree2) ; }
143
144 /*--------------------------------------------------------------------*/
145