1 /* domSegMap.c */
2
3 #include "../GPart.h"
4 #include "../../timings.h"
5 #define NTIMES 12
6 static int icputimes ;
7 static double cputimes[NTIMES] ;
8
9 /*--------------------------------------------------------------------*/
10 /*
11 --------------------------------------------------------------------
12 fill *pndom with ndom, the number of domains.
13 fill *pnseg with nseg, the number of segments.
14 domains are numbered in [0, ndom), segments in [ndom,ndom+nseg).
15
16 return -- an IV object that contains the map
17 from vertices to segments
18
19 created -- 99feb29, cca
20 --------------------------------------------------------------------
21 */
22 IV *
GPart_domSegMap(GPart * gpart,int * pndom,int * pnseg)23 GPart_domSegMap (
24 GPart *gpart,
25 int *pndom,
26 int *pnseg
27 ) {
28 FILE *msgFile ;
29 Graph *g ;
30 int adjdom, count, d, first, ierr, ii, jj1, jj2, last, ndom,
31 msglvl, nextphi, nPhi, nPsi, nV, phi, phi0, phi1, phi2, phi3,
32 psi, sigma, size, size0, size1, size2, v, vsize, w ;
33 int *adj, *adj0, *adj1, *adj2, *compids, *dmark, *dsmap, *head,
34 *link, *list, *offsets, *PhiToPsi, *PhiToV, *PsiToSigma,
35 *vadj, *VtoPhi ;
36 IV *dsmapIV ;
37 IVL *PhiByPhi, *PhiByPowD, *PsiByPowD ;
38 /*
39 --------------------
40 set the initial time
41 --------------------
42 */
43 icputimes = 0 ;
44 MARKTIME(cputimes[icputimes]) ;
45 /*
46 ---------------
47 check the input
48 ---------------
49 */
50 if ( gpart == NULL
51 || (g = gpart->g) == NULL
52 || pndom == NULL
53 || pnseg == NULL ) {
54 fprintf(stderr, "\n fatal error in GPart_domSegMap(%p,%p,%p)"
55 "\n bad input\n", gpart, pndom, pnseg) ;
56 exit(-1) ;
57 }
58 compids = IV_entries(&gpart->compidsIV) ;
59 msglvl = gpart->msglvl ;
60 msgFile = gpart->msgFile ;
61 /*
62 ------------------------
63 create the map IV object
64 ------------------------
65 */
66 nV = g->nvtx ;
67 dsmapIV = IV_new() ;
68 IV_init(dsmapIV, nV, NULL) ;
69 dsmap = IV_entries(dsmapIV) ;
70 /*
71 ----------------------------------
72 check compids[] and get the number
73 of domains and interface vertices
74 ----------------------------------
75 */
76 icputimes++ ;
77 MARKTIME(cputimes[icputimes]) ;
78 ndom = nPhi = 0 ;
79 for ( v = 0 ; v < nV ; v++ ) {
80 if ( (d = compids[v]) < 0 ) {
81 fprintf(stderr,
82 "\n fatal error in GPart_domSegMap(%p,%p,%p)"
83 "\n compids[%d] = %d\n", gpart, pndom, pnseg,
84 v, compids[v]) ;
85 exit(-1) ;
86 } else if ( d == 0 ) {
87 nPhi++ ;
88 } else if ( ndom < d ) {
89 ndom = d ;
90 }
91 }
92 *pndom = ndom ;
93 if ( msglvl > 1 ) {
94 fprintf(msgFile, "\n\n Inside GPart_domSegMap") ;
95 fprintf(msgFile, "\n %d domains, %d Phi vertices", ndom, nPhi) ;
96 }
97 if ( ndom == 1 ) {
98 IVfill(nV, dsmap, 0) ;
99 *pndom = 1 ;
100 *pnseg = 0 ;
101 return(dsmapIV) ;
102 }
103 /*
104 --------------------------------
105 get the maps
106 PhiToV : [0,nPhi) |---> [0,nV)
107 VtoPhi : [0,nV) |---> [0,nPhi)
108 --------------------------------
109 */
110 icputimes++ ;
111 MARKTIME(cputimes[icputimes]) ;
112 PhiToV = IVinit(nPhi, -1) ;
113 VtoPhi = IVinit(nV, -1) ;
114 for ( v = 0, phi = 0 ; v < nV ; v++ ) {
115 if ( (d = compids[v]) == 0 ) {
116 PhiToV[phi] = v ;
117 VtoPhi[v] = phi++ ;
118 }
119 }
120 if ( phi != nPhi ) {
121 fprintf(stderr,
122 "\n fatal error in GPart_domSegMap(%p,%p,%p)"
123 "\n phi = %d != %d = nPhi\n",
124 gpart, pndom, pnseg, phi, nPhi) ;
125 exit(-1) ;
126 }
127 if ( msglvl > 2 ) {
128 fprintf(msgFile, "\n PhiToV(%d) :", nPhi) ;
129 IVfp80(msgFile, nPhi, PhiToV, 15, &ierr) ;
130 fflush(msgFile) ;
131 }
132 if ( msglvl > 3 ) {
133 fprintf(msgFile, "\n VtoPhi(%d) :", nV) ;
134 IVfp80(msgFile, nV, VtoPhi, 15, &ierr) ;
135 fflush(msgFile) ;
136 }
137 /*
138 ---------------------------------------------------
139 create an IVL object, PhiByPowD, to hold lists from
140 the interface vertices to their adjacent domains
141 ---------------------------------------------------
142 */
143 icputimes++ ;
144 MARKTIME(cputimes[icputimes]) ;
145 dmark = IVinit(ndom+1, -1) ;
146 if ( nPhi >= ndom ) {
147 list = IVinit(nPhi, -1) ;
148 } else {
149 list = IVinit(ndom, -1) ;
150 }
151 PhiByPowD = IVL_new() ;
152 IVL_init1(PhiByPowD, IVL_CHUNKED, nPhi) ;
153 for ( phi = 0 ; phi < nPhi ; phi++ ) {
154 v = PhiToV[phi] ;
155 Graph_adjAndSize(g, v, &vsize, &vadj) ;
156 /*
157 if ( phi == 0 ) {
158 int ierr ;
159 fprintf(msgFile, "\n adj(%d,%d) = ", v, phi) ;
160 IVfp80(msgFile, vsize, vadj, 15, &ierr) ;
161 fflush(msgFile) ;
162 }
163 */
164 count = 0 ;
165 for ( ii = 0 ; ii < vsize ; ii++ ) {
166 if ( (w = vadj[ii]) < nV
167 && (d = compids[w]) > 0
168 && dmark[d] != phi ) {
169 dmark[d] = phi ;
170 list[count++] = d ;
171 }
172 }
173 if ( count > 0 ) {
174 IVqsortUp(count, list) ;
175 IVL_setList(PhiByPowD, phi, count, list) ;
176 }
177 }
178 if ( msglvl > 2 ) {
179 fprintf(msgFile, "\n PhiByPowD : interface x adjacent domains") ;
180 IVL_writeForHumanEye(PhiByPowD, msgFile) ;
181 fflush(msgFile) ;
182 }
183 /*
184 -------------------------------------------------------
185 create an IVL object, PhiByPhi to hold lists
186 from the interface vertices to interface vertices.
187 (s,t) are in the list if (s,t) is an edge in the graph
188 and s and t do not share an adjacent domain
189 -------------------------------------------------------
190 */
191 icputimes++ ;
192 MARKTIME(cputimes[icputimes]) ;
193 PhiByPhi = IVL_new() ;
194 IVL_init1(PhiByPhi, IVL_CHUNKED, nPhi) ;
195 offsets = IVinit(nPhi, 0) ;
196 head = IVinit(nPhi, -1) ;
197 link = IVinit(nPhi, -1) ;
198 for ( phi1 = 0 ; phi1 < nPhi ; phi1++ ) {
199 count = 0 ;
200 if ( msglvl > 2 ) {
201 v = PhiToV[phi1] ;
202 Graph_adjAndSize(g, v, &vsize, &vadj) ;
203 fprintf(msgFile, "\n checking out phi = %d, v = %d", phi1, v) ;
204 fprintf(msgFile, "\n adj(%d) : ", v) ;
205 IVfp80(msgFile, vsize, vadj, 10, &ierr) ;
206 }
207 /*
208 -------------------------------------------------------------
209 get (phi1, phi0) edges that were previously put into the list
210 -------------------------------------------------------------
211 */
212 if ( msglvl > 3 ) {
213 if ( head[phi1] == -1 ) {
214 fprintf(msgFile, "\n no previous edges") ;
215 } else {
216 fprintf(msgFile, "\n previous edges :") ;
217 }
218 }
219 for ( phi0 = head[phi1] ; phi0 != -1 ; phi0 = nextphi ) {
220 if ( msglvl > 3 ) {
221 fprintf(msgFile, " %d", phi0) ;
222 }
223 nextphi = link[phi0] ;
224 list[count++] = phi0 ;
225 IVL_listAndSize(PhiByPhi, phi0, &size0, &adj0) ;
226 if ( (ii = ++offsets[phi0]) < size0 ) {
227 /*
228 ----------------------------
229 link phi0 into the next list
230 ----------------------------
231 */
232 phi2 = adj0[ii] ;
233 link[phi0] = head[phi2] ;
234 head[phi2] = phi0 ;
235 }
236 }
237 /*
238 --------------------------
239 get new edges (phi1, phi2)
240 --------------------------
241 */
242 IVL_listAndSize(PhiByPowD, phi1, &size1, &adj1) ;
243 v = PhiToV[phi1] ;
244 Graph_adjAndSize(g, v, &vsize, &vadj) ;
245 for ( ii = 0 ; ii < vsize ; ii++ ) {
246 if ( (w = vadj[ii]) < nV
247 && compids[w] == 0
248 && (phi2 = VtoPhi[w]) > phi1 ) {
249 if ( msglvl > 3 ) {
250 fprintf(msgFile, "\n checking out phi2 = %d", phi2) ;
251 }
252 /*
253 --------------------------------------------------
254 see if phi1 and phi2 have a common adjacent domain
255 --------------------------------------------------
256 */
257 IVL_listAndSize(PhiByPowD, phi2, &size2, &adj2) ;
258 adjdom = 0 ;
259 jj1 = jj2 = 0 ;
260 while ( jj1 < size1 && jj2 < size2 ) {
261 if ( adj1[jj1] < adj2[jj2] ) {
262 jj1++ ;
263 } else if ( adj1[jj1] > adj2[jj2] ) {
264 jj2++ ;
265 } else {
266 if ( msglvl > 3 ) {
267 fprintf(msgFile, ", common adj domain %d", adj1[jj1]) ;
268 }
269 adjdom = 1 ;
270 break ;
271 }
272 }
273 if ( adjdom == 0 ) {
274 if ( msglvl > 3 ) {
275 fprintf(msgFile, ", no adjacent domain") ;
276 }
277 list[count++] = phi2 ;
278 }
279 }
280 }
281 if ( count > 0 ) {
282 /*
283 ---------------------
284 set the list for phi1
285 ---------------------
286 */
287 IVqsortUp(count, list) ;
288 IVL_setList(PhiByPhi, phi1, count, list) ;
289 if ( msglvl > 2 ) {
290 fprintf(msgFile, "\n edge list for %d :", phi1) ;
291 IVfp80(msgFile, count, list, 15, &ierr) ;
292 }
293 for ( ii = 0, phi2 = -1 ; ii < count ; ii++ ) {
294 if ( list[ii] > phi1 ) {
295 offsets[phi1] = ii ;
296 phi2 = list[ii] ;
297 break ;
298 }
299 }
300 if ( phi2 != -1 ) {
301 if ( msglvl > 2 ) {
302 fprintf(msgFile,
303 "\n linking %d into list for %d", phi1, phi2) ;
304 }
305 link[phi1] = head[phi2] ;
306 head[phi2] = phi1 ;
307 }
308 /*
309 phi2 = list[0] ;
310 link[phi1] = head[phi2] ;
311 head[phi2] = phi1 ;
312 */
313 }
314 }
315 if ( msglvl > 2 ) {
316 fprintf(msgFile, "\n PhiByPhi : interface x interface") ;
317 IVL_writeForHumanEye(PhiByPhi, msgFile) ;
318 fflush(msgFile) ;
319 }
320 /*
321 --------------------
322 get the PhiToPsi map
323 --------------------
324 */
325 icputimes++ ;
326 MARKTIME(cputimes[icputimes]) ;
327 PhiToPsi = IVinit(nPhi, -1) ;
328 nPsi = 0 ;
329 for ( phi = 0 ; phi < nPhi ; phi++ ) {
330 if ( PhiToPsi[phi] == -1 ) {
331 /*
332 ---------------------------
333 phi not yet mapped to a psi
334 ---------------------------
335 */
336 first = last = 0 ;
337 list[0] = phi ;
338 PhiToPsi[phi] = nPsi ;
339 while ( first <= last ) {
340 phi2 = list[first++] ;
341 IVL_listAndSize(PhiByPhi, phi2, &size, &adj) ;
342 for ( ii = 0 ; ii < size ; ii++ ) {
343 phi3 = adj[ii] ;
344 if ( PhiToPsi[phi3] == -1 ) {
345 PhiToPsi[phi3] = nPsi ;
346 list[++last] = phi3 ;
347 }
348 }
349 }
350 nPsi++ ;
351 }
352 }
353 if ( msglvl > 1 ) {
354 fprintf(msgFile, "\n nPsi = %d", nPsi) ;
355 fflush(msgFile) ;
356 }
357 if ( msglvl > 2 ) {
358 fprintf(msgFile, "\n PhiToPsi(%d) :", nPhi) ;
359 IVfp80(msgFile, nPhi, PhiToPsi, 15, &ierr) ;
360 fflush(msgFile) ;
361 }
362 /*
363 ---------------------------------
364 create an IVL object, Psi --> 2^D
365 ---------------------------------
366 */
367 icputimes++ ;
368 MARKTIME(cputimes[icputimes]) ;
369 IVfill(nPsi, head, -1) ;
370 IVfill(nPhi, link, -1) ;
371 for ( phi = 0 ; phi < nPhi ; phi++ ) {
372 psi = PhiToPsi[phi] ;
373 link[phi] = head[psi] ;
374 head[psi] = phi ;
375 }
376 PsiByPowD = IVL_new() ;
377 IVL_init1(PsiByPowD, IVL_CHUNKED, nPsi) ;
378 IVfill(ndom+1, dmark, -1) ;
379 for ( psi = 0 ; psi < nPsi ; psi++ ) {
380 count = 0 ;
381 for ( phi = head[psi] ; phi != -1 ; phi = link[phi] ) {
382 v = PhiToV[phi] ;
383 Graph_adjAndSize(g, v, &size, &adj) ;
384 for ( ii = 0 ; ii < size ; ii++ ) {
385 if ( (w = adj[ii]) < nV
386 && (d = compids[w]) > 0
387 && dmark[d] != psi ) {
388 dmark[d] = psi ;
389 list[count++] = d ;
390 }
391 }
392 }
393 if ( count > 0 ) {
394 IVqsortUp(count, list) ;
395 IVL_setList(PsiByPowD, psi, count, list) ;
396 }
397 }
398 if ( msglvl > 2 ) {
399 fprintf(msgFile, "\n PsiByPowD(%d) :", nPhi) ;
400 IVL_writeForHumanEye(PsiByPowD, msgFile) ;
401 fflush(msgFile) ;
402 }
403 icputimes++ ;
404 MARKTIME(cputimes[icputimes]) ;
405 /*
406 -------------------------------------
407 now get the map Psi |---> Sigma that
408 is the equivalence map over PhiByPowD
409 -------------------------------------
410 */
411 icputimes++ ;
412 MARKTIME(cputimes[icputimes]) ;
413 PsiToSigma = IVL_equivMap1(PsiByPowD) ;
414 *pnseg = 1 + IVmax(nPsi, PsiToSigma, &ii) ;
415 if ( msglvl > 2 ) {
416 fprintf(msgFile, "\n nSigma = %d", *pnseg) ;
417 fprintf(msgFile, "\n PsiToSigma(%d) :", nPhi) ;
418 IVfp80(msgFile, nPsi, PsiToSigma, 15, &ierr) ;
419 fflush(msgFile) ;
420 }
421 /*
422 --------------------------------------------------------------
423 now fill the map from the vertices to the domains and segments
424 --------------------------------------------------------------
425 */
426 icputimes++ ;
427 MARKTIME(cputimes[icputimes]) ;
428 for ( v = 0 ; v < nV ; v++ ) {
429 if ( (d = compids[v]) > 0 ) {
430 dsmap[v] = d - 1 ;
431 } else {
432 phi = VtoPhi[v] ;
433 psi = PhiToPsi[phi] ;
434 sigma = PsiToSigma[psi] ;
435 dsmap[v] = ndom + sigma ;
436 }
437 }
438 /*
439 ------------------------
440 free the working storage
441 ------------------------
442 */
443 icputimes++ ;
444 MARKTIME(cputimes[icputimes]) ;
445 IVL_free(PhiByPhi) ;
446 IVL_free(PhiByPowD) ;
447 IVL_free(PsiByPowD) ;
448 IVfree(PhiToV) ;
449 IVfree(VtoPhi) ;
450 IVfree(dmark) ;
451 IVfree(list) ;
452 IVfree(PhiToPsi) ;
453 IVfree(head) ;
454 IVfree(link) ;
455 IVfree(offsets) ;
456 IVfree(PsiToSigma) ;
457 icputimes++ ;
458 MARKTIME(cputimes[icputimes]) ;
459 if ( msglvl > 1 ) {
460 fprintf(msgFile, "\n domain/segment map timings split") ;
461 fprintf(msgFile,
462 "\n %9.5f : create the DSmap object"
463 "\n %9.5f : get numbers of domain and interface vertices"
464 "\n %9.5f : generate PhiToV and VtoPhi"
465 "\n %9.5f : generate PhiByPowD"
466 "\n %9.5f : generate PhiByPhi"
467 "\n %9.5f : generate PhiToPsi"
468 "\n %9.5f : generate PsiByPowD"
469 "\n %9.5f : generate PsiToSigma"
470 "\n %9.5f : generate dsmap"
471 "\n %9.5f : free working storage"
472 "\n %9.5f : total time",
473 cputimes[1] - cputimes[0],
474 cputimes[2] - cputimes[1],
475 cputimes[3] - cputimes[2],
476 cputimes[4] - cputimes[3],
477 cputimes[5] - cputimes[4],
478 cputimes[6] - cputimes[5],
479 cputimes[7] - cputimes[6],
480 cputimes[8] - cputimes[7],
481 cputimes[9] - cputimes[8],
482 cputimes[10] - cputimes[9],
483 cputimes[11] - cputimes[0]) ;
484 }
485
486 return(dsmapIV) ; }
487
488 /*--------------------------------------------------------------------*/
489