1 /* compress.c */
2
3 #include "../Perm.h"
4
5 /*--------------------------------------------------------------------*/
6 /*
7 ------------------------------------------------
8 given a permutation and a vector to map vertices
9 into compressed vertices, create and return a
10 permutation object for the compressed vertices.
11
12 created -- 96may02, cca
13 ------------------------------------------------
14 */
15 Perm *
Perm_compress(Perm * perm,IV * eqmapIV)16 Perm_compress (
17 Perm *perm,
18 IV *eqmapIV
19 ) {
20 int n, N, v, vcomp, vnew ;
21 int *eqmap, *head, *link, *newToOld, *oldToNew, *vals ;
22 Perm *perm2 ;
23 /*
24 ---------------
25 check the input
26 ---------------
27 */
28 if ( perm == NULL
29 || (n = perm->size) <= 0
30 || eqmapIV == NULL
31 || n != IV_size(eqmapIV)
32 || (eqmap = IV_entries(eqmapIV)) == NULL ) {
33 fprintf(stderr, "\n fatal error in Perm_compress(%p,%p)"
34 "\n bad input\n", perm, eqmapIV) ;
35 if ( perm != NULL ) {
36 Perm_writeStats(perm, stderr) ;
37 }
38 if ( eqmapIV != NULL ) {
39 IV_writeStats(eqmapIV, stderr) ;
40 }
41 exit(-1) ;
42 }
43 n = perm->size ;
44 if ( (oldToNew = perm->oldToNew) == NULL ) {
45 Perm_fillOldToNew(perm) ;
46 oldToNew = perm->oldToNew ;
47 }
48 if ( (newToOld = perm->newToOld) == NULL ) {
49 Perm_fillNewToOld(perm) ;
50 newToOld = perm->newToOld ;
51 }
52 /*
53 ---------------------------------
54 create the new permutation object
55 ---------------------------------
56 */
57 N = 1 + IVmax(n, eqmap, &v) ;
58 perm2 = Perm_new() ;
59 Perm_initWithTypeAndSize(perm2, 3, N) ;
60 /*
61 --------------------------------------------
62 get the head/link structure for the vertices
63 --------------------------------------------
64 */
65 head = IVinit(N, -1) ;
66 link = IVinit(n, -1) ;
67 for ( v = 0 ; v < n ; v++ ) {
68 vcomp = eqmap[v] ;
69 link[v] = head[vcomp] ;
70 head[vcomp] = v ;
71 }
72 /*
73 ---------------------------
74 get the two vectors to sort
75 ---------------------------
76 */
77 IVramp(N, perm2->newToOld, 0, 1) ;
78 vals = IVinit(N, -1) ;
79 for ( vcomp = 0 ; vcomp < N ; vcomp++ ) {
80 v = head[vcomp] ;
81 vnew = perm->oldToNew[v] ;
82 for ( v = link[v] ; v != -1 ; v = link[v] ) {
83 if ( vnew > perm->oldToNew[v] ) {
84 vnew = perm->oldToNew[v] ;
85 }
86 }
87 vals[vcomp] = vnew ;
88 }
89 IV2qsortUp(N, vals, perm2->newToOld) ;
90 for ( vcomp = 0 ; vcomp < N ; vcomp++ ) {
91 perm2->oldToNew[perm2->newToOld[vcomp]] = vcomp ;
92 }
93 /*
94 ---------------------
95 free the working data
96 ---------------------
97 */
98 IVfree(head) ;
99 IVfree(link) ;
100 IVfree(vals) ;
101
102 return(perm2) ; }
103
104 /*--------------------------------------------------------------------*/
105