1
/* Copyright 2004,2007 ENSEIRB, INRIA & CNRS
3
** This file is part of the Scotch software package for static mapping,
4
** graph partitioning and sparse matrix ordering.
6
** This software is governed by the CeCILL-C license under French law
7
** and abiding by the rules of distribution of free software. You can
8
** use, modify and/or redistribute the software under the terms of the
9
** CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
10
** URL: "http://www.cecill.info".
12
** As a counterpart to the access to the source code and rights to copy,
13
** modify and redistribute granted by the license, users are provided
14
** only with a limited warranty and the software's author, the holder of
15
** the economic rights, and the successive licensors have only limited
18
** In this respect, the user's attention is drawn to the risks associated
19
** with loading, using, modifying and/or developing or reproducing the
20
** software by the user in light of its specific status of free software,
21
** that may mean that it is complicated to manipulate, and that also
22
** therefore means that it is reserved for developers and experienced
23
** professionals having in-depth computer knowledge. Users are therefore
24
** encouraged to load and test the software's suitability as regards
25
** their requirements in conditions enabling the security of their
26
** systems and/or data to be ensured and, more generally, to use and
27
** operate it in the same conditions as regards security.
29
** The fact that you are presently reading this means that you have had
30
** knowledge of the CeCILL-C license and that you accept its terms.
32
/************************************************************/
34
/** NAME : graph_coarsen.c **/
36
/** AUTHOR : Francois PELLEGRINI **/
38
/** FUNCTION : This module contains the source graph **/
39
/** coarsening functions. **/
41
/** DATES : # Version 0.0 : from : 01 dec 1992 **/
42
/** to 18 may 1993 **/
43
/** # Version 1.3 : from : 30 apr 1994 **/
44
/** to 18 may 1994 **/
45
/** # Version 2.0 : from : 06 jun 1994 **/
46
/** to 31 oct 1994 **/
47
/** # Version 3.0 : from : 07 jul 1995 **/
48
/** to 28 sep 1995 **/
49
/** # Version 3.1 : from : 28 nov 1995 **/
50
/** to 08 jun 1996 **/
51
/** # Version 3.2 : from : 07 sep 1996 **/
52
/** to 17 sep 1998 **/
53
/** # Version 4.0 : from : 13 dec 2001 **/
54
/** to 31 aug 2005 **/
55
/** # Version 5.0 : from : 13 dec 2006 **/
56
/** to 10 sep 2007 **/
58
/************************************************************/
61
** The defines and includes.
69
#include "graph_coarsen.h"
72
** The static variables.
75
static Gnum (* graphCoarsenFuncTab[GRAPHCOARNBR]) () = { /* Tables of edge-matching routines */
79
graphCoarsenMatchCh };
81
/***************************/
83
/* The coarsening routine. */
85
/***************************/
87
/* This routine coarsens the given "finegraph" into
88
** "coargraph", as long as the coarsening ratio remains
89
** below some threshold value and the coarsened graph
92
** - 0 : if the graph has been coarsened.
93
** - 1 : if the graph could not be coarsened.
99
const Graph * restrict const finegrafptr, /*+ Graph to coarsen +*/
100
Graph * restrict const coargrafptr, /*+ Coarse graph to build +*/
101
GraphCoarsenMulti * restrict * const coarmultptr, /*+ Pointer to multinode table to build +*/
102
const Gnum coarnbr, /*+ Minimum number of coarse vertices +*/
103
const double coarrat, /*+ Maximum contraction ratio +*/
104
const GraphCoarsenType coartype) /*+ Edge matching type +*/
106
Gnum coarhashnbr; /* Size of the hash table */
107
Gnum coarhashmsk; /* Mask for access to hash table */
108
GraphCoarsenHash * restrict coarhashtab; /* Table of edges to other multinodes */
109
Gnum coarvertnbr; /* Number of coarse vertices */
110
Gnum coarvertnum; /* Number of current multinode vertex */
111
Gnum coarvertmax; /* Maximum number of multinode vertices */
112
Gnum coarvelomax; /* Maximum vertex weight allowed */
113
GraphCoarsenMulti * restrict coarmulttax; /* Multinode array */
114
Gnum * restrict finecoartax; /* Based access to finecoartab */
115
Gnum finevertnum; /* Number of currently selected fine vertex */
116
size_t coarmultoftval;
117
size_t coarvelooftval;
118
size_t coaredgeoftval;
119
size_t coaredlooftval;
121
#ifdef SCOTCH_DEBUG_GRAPH2
122
if (coartype >= GRAPHCOARNBR) {
123
errorPrint ("graphCoarsen: invalid parameter");
126
#endif /* SCOTCH_DEBUG_GRAPH2 */
127
#ifdef SCOTCH_DEBUG_GRAPH1
128
if (coarrat < 0.5L) /* If impossible coarsening ratio wanted */
129
return (1); /* We will never succeed */
130
#endif /* SCOTCH_DEBUG_GRAPH1 */
132
coarvertmax = (Gnum) ((double) finegrafptr->vertnbr * coarrat); /* Maximum number of coarse vertices */
133
if (coarvertmax < coarnbr) /* If there will be too few vertices in graph */
134
return (1); /* It is useless to go any further */
136
if ((finecoartax = (Gnum *) memAlloc (finegrafptr->vertnbr * sizeof (Gnum))) == NULL) {
137
errorPrint ("graphCoarsen: out of memory (1)"); /* Allocate coarse graph uncoarsening array */
140
memSet (finecoartax, ~0, finegrafptr->vertnbr * sizeof (Gnum));
141
finecoartax -= finegrafptr->baseval; /* Set based access to finecoartab */
143
coarvelomax = (3 * finegrafptr->velosum) / (2 * coarnbr) + 1;
145
coarvertnbr = graphCoarsenFuncTab[coartype] (finegrafptr, finecoartax, coarvertmax, coarvelomax); /* Call proper matching function */
147
if (coarvertnbr >= coarvertmax) { /* If coarsened graph too large */
148
memFree (finecoartax + finegrafptr->baseval); /* Do not proceed any further */
152
#ifdef SCOTCH_DEBUG_GRAPH2
153
for (finevertnum = finegrafptr->baseval; finevertnum < finegrafptr->vertnnd; finevertnum ++) {
154
if (finecoartax[finevertnum] <= ~0) { /* If coarsening not aborted, this should not happen */
155
errorPrint ("graphCoarsen: internal error (1)");
156
memFree (finecoartax + finegrafptr->baseval);
160
#endif /* SCOTCH_DEBUG_GRAPH2 */
162
memSet (coargrafptr, 0, sizeof (Graph)); /* Initialize coarse graph */
163
coargrafptr->flagval = GRAPHFREEVERT | GRAPHVERTGROUP | GRAPHEDGEGROUP;
164
coargrafptr->baseval = finegrafptr->baseval;
165
coargrafptr->vertnbr = coarvertnbr;
166
coargrafptr->vertnnd = coarvertnbr + coargrafptr->baseval;
167
coargrafptr->velosum = finegrafptr->velosum; /* Keep load of finer graph */
169
for (coarhashmsk = 31; coarhashmsk < finegrafptr->degrmax; coarhashmsk = coarhashmsk * 2 + 1) ;
170
coarhashmsk = coarhashmsk * 4 + 3;
171
coarhashnbr = coarhashmsk + 1;
173
if (memAllocGroup ((void **) (void *)
174
&coargrafptr->verttax, (size_t) ((coarvertnbr + 1) * sizeof (Gnum)),
175
&coargrafptr->velotax, (size_t) (coarvertnbr * sizeof (Gnum)),
176
&coarmulttax, (size_t) (coarvertnbr * sizeof (GraphCoarsenMulti)),
177
&coargrafptr->edgetax, (size_t) (finegrafptr->edgenbr * sizeof (Gnum)), /* Pre-allocate space for edge arrays */
178
&coargrafptr->edlotax, (size_t) (finegrafptr->edgenbr * sizeof (Gnum)),
179
&coarhashtab, (size_t) (coarhashnbr * sizeof (GraphCoarsenHash)), NULL) == NULL) {
180
errorPrint ("graphCoarsen: out of memory (2)"); /* Allocate coarser graph structure */
181
memFree (finecoartax + finegrafptr->baseval);
184
coargrafptr->verttax -= coargrafptr->baseval; /* Base coarse graph arrays */
185
coargrafptr->velotax -= coargrafptr->baseval;
186
coargrafptr->edgetax -= coargrafptr->baseval;
187
coargrafptr->edlotax -= coargrafptr->baseval;
188
coarmulttax -= coargrafptr->baseval;
190
for (finevertnum = finegrafptr->baseval, coarvertnum = coargrafptr->baseval; /* Finalize finecoartab array */
191
finevertnum < finegrafptr->vertnnd; finevertnum ++) {
192
Gnum finematenum; /* Number of current mate vertex */
194
finematenum = finecoartax[finevertnum]; /* Get mate number */
195
if (finematenum >= finevertnum) { /* If mate has larger number */
196
coarmulttax[coarvertnum].vertnum[0] = finevertnum; /* Build new multinode */
197
coarmulttax[coarvertnum].vertnum[1] = finematenum; /* Second index always biggest */
198
finecoartax[finematenum] = /* Point to coarse vertex */
199
finecoartax[finevertnum] = coarvertnum; /* Always valid since coarvertnum <= finevertnum */
200
coarvertnum ++; /* One more multinode created */
203
#ifdef SCOTCH_DEBUG_GRAPH2
204
if ((coarvertnum - coargrafptr->baseval) != coarvertnbr) {
205
errorPrint ("graphCoarsen: internal error (2)");
206
graphFree (coargrafptr);
207
memFree (finecoartax + finegrafptr->baseval);
210
#endif /* SCOTCH_DEBUG_GRAPH2 */
212
if (finegrafptr->velotax != NULL) { /* If fine graph is weighted */
213
for (coarvertnum = coargrafptr->baseval; coarvertnum < coargrafptr->vertnnd; coarvertnum ++) {
216
coarveloval = finegrafptr->velotax[coarmulttax[coarvertnum].vertnum[0]];
217
if (coarmulttax[coarvertnum].vertnum[0] != coarmulttax[coarvertnum].vertnum[1])
218
coarveloval += finegrafptr->velotax[coarmulttax[coarvertnum].vertnum[1]];
219
coargrafptr->velotax[coarvertnum] = coarveloval;
222
else { /* Fine graph is not weighted */
223
for (coarvertnum = coargrafptr->baseval; coarvertnum < coargrafptr->vertnnd; coarvertnum ++)
224
coargrafptr->velotax[coarvertnum] = (coarmulttax[coarvertnum].vertnum[0] != coarmulttax[coarvertnum].vertnum[1]) ? 2 : 1;
227
memSet (coarhashtab, ~0, coarhashnbr * sizeof (GraphCoarsenHash));
228
if (finegrafptr->edlotax != NULL) /* If edge loads available */
229
graphCoarsenEdgeLl (finegrafptr, finecoartax, coarmulttax, coargrafptr, coarhashtab, coarhashmsk);
230
else /* Fine edges not weighted */
231
graphCoarsenEdgeLu (finegrafptr, finecoartax, coarmulttax, coargrafptr, coarhashtab, coarhashmsk);
232
coargrafptr->edgenbr = coargrafptr->verttax[coargrafptr->vertnnd] - coargrafptr->baseval; /* Set exact number of edges */
234
memFree (finecoartax + finegrafptr->baseval);
236
coarvelooftval = coargrafptr->velotax - coargrafptr->verttax;
237
coarmultoftval = (Gnum *) coarmulttax - coargrafptr->verttax;
238
coaredgeoftval = coargrafptr->edgetax - coargrafptr->verttax;
239
coaredlooftval = coargrafptr->edlotax - coargrafptr->verttax;
240
memReallocGroup ((void *) (coargrafptr->verttax + coargrafptr->baseval), /* Re-allocate data, wiping temporary arrays */
241
&coargrafptr->verttax, (size_t) ((coarvertnbr + 1) * sizeof (Gnum)),
242
&coargrafptr->velotax, (size_t) (coarvertnbr * sizeof (Gnum)),
243
&coarmulttax, (size_t) (coarvertnbr * sizeof (GraphCoarsenMulti)),
244
&coargrafptr->edgetax, (size_t) (finegrafptr->edgenbr * sizeof (Gnum)),
245
&coargrafptr->edlotax, (size_t) (coargrafptr->edgenbr * sizeof (Gnum)), NULL);
246
coargrafptr->verttax -= coargrafptr->baseval;
247
coargrafptr->vendtax = coargrafptr->verttax + 1; /* Use compact representation of arrays */
248
coargrafptr->velotax = coargrafptr->verttax + coarvelooftval;
249
coargrafptr->edgetax = coargrafptr->verttax + coaredgeoftval;
250
coargrafptr->edlotax = coargrafptr->verttax + coaredlooftval;
251
coarmulttax = (GraphCoarsenMulti *) (coargrafptr->verttax + coarmultoftval);
252
*coarmultptr = coarmulttax; /* Return pointer to multinode array */
254
#ifdef SCOTCH_DEBUG_GRAPH2
255
if (graphCheck (coargrafptr) != 0) { /* Check graph consistency */
256
errorPrint ("graphCoarsen: inconsistent graph data");
257
graphFree (coargrafptr);
260
#endif /* SCOTCH_DEBUG_GRAPH2 */
265
/****************************************/
267
/* The edge array building subroutines. */
269
/****************************************/
271
#define GRAPHCOARSENEDGENAME graphCoarsenEdgeLl
272
#define GRAPHCOARSENEDGEEDLOINIT coargrafptr->edlotax[coaredgenum] = finegrafptr->edlotax[fineedgenum]
273
#define GRAPHCOARSENEDGEEDLOADD coargrafptr->edlotax[coarhashtab[h].edgenum] += finegrafptr->edlotax[fineedgenum]
274
#define GRAPHCOARSENEDGEEDLOSUB coaredlosum -= finegrafptr->edlotax[fineedgenum]
275
#include "graph_coarsen_edge.c"
276
#undef GRAPHCOARSENEDGENAME
277
#undef GRAPHCOARSENEDGEEDLOINIT
278
#undef GRAPHCOARSENEDGEEDLOADD
279
#undef GRAPHCOARSENEDGEEDLOSUB
281
#define GRAPHCOARSENEDGENAME graphCoarsenEdgeLu
282
#define GRAPHCOARSENEDGEEDLOINIT coargrafptr->edlotax[coaredgenum] = 1
283
#define GRAPHCOARSENEDGEEDLOADD coargrafptr->edlotax[coarhashtab[h].edgenum] ++
284
#define GRAPHCOARSENEDGEEDLOSUB coaredlosum --
285
#include "graph_coarsen_edge.c"
286
#undef GRAPHCOARSENEDGENAME
287
#undef GRAPHCOARSENEDGEEDLOINIT
288
#undef GRAPHCOARSENEDGEEDLOADD
289
#undef GRAPHCOARSENEDGEEDLOSUB
291
/*****************************/
293
/* The matching subroutines. */
295
/*****************************/
299
graphCoarsenMatchHy (
300
const Graph * restrict const finegrafptr, /* Fine graph to perform matching on */
301
Gnum * restrict finecoartax, /* Fine to coarse vertex index array */
302
const Gnum coarvertmax, /* Maximum number of vertices to get */
303
const Gnum coarvelomax) /* Maximum vertex weight allowed */
305
Gnum coarvertnum; /* Number of current multinode vertex */
306
Gnum finepertbas; /* Index of base of perturbation area */
307
Gnum finepertnbr; /* Size of perturbation area */
308
const Gnum * restrict fineverttax; /* Based access to vertex array */
309
const Gnum * restrict finevendtax; /* Based access to end vertex array */
310
const Gnum * restrict finevelotax; /* Based access to end vertex array */
311
const Gnum * restrict fineedgetax; /* Based access to end vertex array */
312
const Gnum * restrict fineedlotax; /* Based access to end vertex array */
313
Gnum finevertnnd; /* Current end of vertex array */
314
Gnum finevertnum; /* Number of currently selected fine vertex */
316
if (finegrafptr->edlotax == NULL) /* If no edge loads, perform scan matching instead */
317
return (graphCoarsenMatchSc (finegrafptr, finecoartax, coarvertmax, coarvelomax));
319
fineverttax = finegrafptr->verttax;
320
finevendtax = finegrafptr->vendtax;
321
finevelotax = finegrafptr->velotax;
322
fineedgetax = finegrafptr->edgetax;
323
fineedlotax = finegrafptr->edlotax;
324
finevertnnd = finegrafptr->vertnnd;
327
if (finegrafptr->velotax != NULL) {
328
Gnum finevelodlt; /* Minimum load of neighbor */
330
finevelodlt = (3 * finegrafptr->velosum) / (5 * (finevertnnd - finegrafptr->baseval));
332
for (finevertnum = finegrafptr->baseval; /* Pre-selection loop for isolated and lightest vertices */
333
finevertnum < finevertnnd; finevertnum ++) {
334
if (fineverttax[finevertnum] == finevendtax[finevertnum]) { /* If isolated vertex */
335
while (finecoartax[-- finevertnnd] != ~0) ; /* Search for first matchable "neighbor" */
337
finecoartax[finevertnum] = finevertnnd; /* At worst we will stop at finevertnum */
338
finecoartax[finevertnnd] = finevertnum;
339
coarvertnum ++; /* One more coarse vertex created */
341
else { /* Vertex has neighbors */
342
if ((finevelotax[finevertnum] < finevelodlt) &&
343
(finecoartax[finevertnum] == ~0)) { /* If vertex is too light on average */
344
Gnum finevertbst; /* Number of current best neighbor */
345
Gnum fineedlobst; /* Edge load of current best neighbor */
348
if (coarvertnum >= coarvertmax) /* If coarse graph is too large */
349
return (coarvertmax); /* Return that we cannot coarsen more */
351
finevertbst = finevertnum; /* No matching neighbor found yet */
353
for (fineedgenum = fineverttax[finevertnum]; /* For all adjacent vertices */
354
fineedgenum < finevendtax[finevertnum]; fineedgenum ++) {
355
if ((finecoartax[fineedgetax[fineedgenum]] == ~0) && /* If unmatched vertex */
356
(fineedlotax[fineedgenum] > fineedlobst)) { /* And is better candidate */
357
fineedlobst = fineedlotax[fineedgenum];
358
finevertbst = fineedgetax[fineedgenum];
362
finecoartax[finevertnum] = finevertbst;
363
finecoartax[finevertbst] = finevertnum;
364
coarvertnum ++; /* One more coarse vertex created */
370
finepertnbr = 2 + intRandVal (GRAPHCOARPERTPRIME - 2); /* Compute perturbation area size (avoid DIV0 in random) */
371
for (finepertbas = finegrafptr->baseval; finepertbas < finevertnnd; /* Run cache-friendly perturbation */
372
finepertbas += finepertnbr) {
373
Gnum finepertval; /* Current index in perturbation area */
375
if (finepertbas + finepertnbr > finevertnnd)
376
finepertnbr = finevertnnd - finepertbas;
378
finepertval = 0; /* Start from first perturbation vertex */
379
do { /* Loop on perturbation vertices */
380
finevertnum = finepertbas + finepertval; /* Compute corresponding vertex number */
382
if (finecoartax[finevertnum] == ~0) { /* If vertex has not been picked already */
383
Gnum finevertbst; /* Number of current best neighbor */
384
Gnum fineedlobst; /* Edge load of current best neighbor */
385
Gnum finevelodlt; /* Maximum load of neighbor */
388
if (coarvertnum >= coarvertmax) /* If coarse graph too large */
389
return (coarvertmax); /* Return that cannot coarsen more */
391
finevertbst = finevertnum; /* No matching vertex found yet */
393
finevelodlt = coarvelomax - ((finevelotax != NULL) ? finevelotax[finevertnum] : 1);
395
for (fineedgenum = fineverttax[finevertnum]; /* For all adjacent vertices */
396
fineedgenum < finevendtax[finevertnum]; fineedgenum ++) {
397
if ((finecoartax[fineedgetax[fineedgenum]] == ~0) && /* If unmatched vertex */
398
(fineedlotax[fineedgenum] > fineedlobst) && /* And better candidate */
399
((finevelotax == NULL) || /* And does not create overloads */
400
(finevelodlt >= finevelotax[fineedgetax[fineedgenum]]))) {
401
fineedlobst = fineedlotax[fineedgenum];
402
finevertbst = fineedgetax[fineedgenum];
406
finecoartax[finevertnum] = finevertbst;
407
finecoartax[finevertbst] = finevertnum;
408
coarvertnum ++; /* One more coarse vertex created */
411
finepertval = (finepertval + GRAPHCOARPERTPRIME) % finepertnbr; /* Compute next perturbation index */
412
} while (finepertval != 0);
415
return (coarvertnum); /* Return number of coarse vertices */
420
graphCoarsenMatchSc (
421
const Graph * restrict const finegrafptr, /* Fine graph to perform matching on */
422
Gnum * restrict finecoartax, /* Fine to coarse vertex index array */
423
const Gnum coarvertmax, /* Maximum number of vertices to get */
424
const Gnum coarvelomax) /* Maximum vertex weight allowed */
426
Gnum coarvertnum; /* Number of current multinode vertex */
427
Gnum finepertbas; /* Index of base of perturbation area */
428
const Gnum * restrict fineverttax; /* Based access to vertex array */
429
Gnum finepertnbr; /* Size of perturbation area */
430
Gnum finevertnnd; /* Current end of vertex array */
431
Gnum finevertnum; /* Number of currently selected fine vertex */
433
fineverttax = finegrafptr->verttax;
436
for (finepertbas = finegrafptr->baseval, finevertnnd = finegrafptr->vertnnd;
437
finepertbas < finevertnnd; finepertbas += finepertnbr) { /* Run cache-friendly perturbation */
438
Gnum finepertval; /* Current index in perturbation area */
440
finepertnbr = finegrafptr->degrmax * 2 + intRandVal (finegrafptr->degrmax + 1) + 1; /* Compute perturbation area size (avoid DIV0 in random) */
441
if (finepertnbr >= GRAPHCOARPERTPRIME)
442
finepertnbr = 32 + intRandVal (GRAPHCOARPERTPRIME - 34);
444
if (finepertbas + finepertnbr > finevertnnd)
445
finepertnbr = finevertnnd - finepertbas;
447
finepertval = 0; /* Start from first perturbation vertex */
448
do { /* Loop on perturbation vertices */
449
finevertnum = finepertbas + finepertval; /* Compute corresponding vertex number */
451
if (finecoartax[finevertnum] == ~0) { /* If vertex has not been picked already */
452
Gnum finevertbst; /* Number of current best matching vertex */
454
if (coarvertnum >= coarvertmax) /* If coarse graph is too large */
455
return (coarvertmax); /* Return that we cannot coarsen more */
457
if (fineverttax[finevertnum] == finegrafptr->vendtax[finevertnum]) { /* If isolated vertex */
458
while (finecoartax[-- finevertnnd] != ~0) ; /* Search for first matchable "neighbor" */
459
finevertbst = finevertnnd; /* Unmatched vertex will act as neighbor */
461
else { /* Vertex has neighbors */
462
Gnum finevelodlt; /* Overload limit */
463
Gnum fineedgenum; /* Current edge number */
465
finevertbst = finevertnum; /* No matching vertex found yet */
466
finevelodlt = coarvelomax - ((finegrafptr->velotax != NULL) ? finegrafptr->velotax[finevertnum] : 1);
468
for (fineedgenum = fineverttax[finevertnum]; /* For all adjacent vertices */
469
fineedgenum < finegrafptr->vendtax[finevertnum]; fineedgenum ++) {
470
if ((finecoartax[finegrafptr->edgetax[fineedgenum]] == ~0) && /* If unmatched vertex */
471
((finegrafptr->velotax == NULL) || /* And does not create overloads */
472
(finevelodlt >= finegrafptr->velotax[finegrafptr->edgetax[fineedgenum]]))) {
473
finevertbst = finegrafptr->edgetax[fineedgenum];
479
finecoartax[finevertnum] = finevertbst;
480
finecoartax[finevertbst] = finevertnum;
481
coarvertnum ++; /* One more coarse vertex created */
484
finepertval = (finepertval + GRAPHCOARPERTPRIME) % finepertnbr; /* Compute next perturbation index */
485
} while (finepertval != 0);
488
return (coarvertnum); /* Return number of coarse vertices */
493
graphCoarsenMatchCs ( /* Crystallographic scan */
494
const Graph * restrict const finegrafptr, /* Fine graph to perform matching on */
495
Gnum * restrict finecoartax, /* Fine to coarse vertex index array */
496
const Gnum coarvertmax, /* Maximum number of vertices to get */
497
const Gnum coarvelomax) /* Maximum vertex weight allowed */
499
Gnum coarvertnum; /* Number of current multinode vertex */
500
const Gnum * restrict fineverttax; /* Based access to vertex array */
501
const Gnum * restrict finevendtax; /* Based access to end vertex array */
502
const Gnum * restrict finevelotax; /* Based access to vertex load array */
503
const Gnum * restrict fineedgetax; /* Based access to edge array */
504
Gnum finevertnum; /* Number of currently selected fine vertex */
505
Gnum * restrict finequeutab;
506
Gnum finequeuheadval;
507
Gnum finequeutailval;
508
Gnum finepermnum; /* Permutation number for finding connected components */
510
fineverttax = finegrafptr->verttax;
511
finevendtax = finegrafptr->vendtax;
512
finevelotax = finegrafptr->velotax;
513
fineedgetax = finegrafptr->edgetax;
514
if ((finequeutab = memAlloc (finegrafptr->vertnbr * sizeof (Gnum))) == NULL) {
515
errorPrint ("graphCoarsenMatchCs: out of memory");
516
return (graphCoarsenMatchSc (finegrafptr, finecoartax, coarvertmax, coarvelomax)); /* Fallback strategy */
522
finequeutab[0] = finegrafptr->baseval + intRandVal (finegrafptr->vertnbr); /* Start from random vertex */
523
finecoartax[finequeutab[0]] = -2; /* Set vertex as enqueued */
525
for (finepermnum = finegrafptr->baseval; finequeutailval < finegrafptr->vertnbr; ) {
526
if (finequeutailval < finequeuheadval) { /* If vertices remain in queue */
527
Gnum finevertbst; /* Best vertex found till now */
528
Gnum finevelodlt; /* Overload limit */
529
Gnum fineedgenum; /* Current edge number */
531
finevertnum = finequeutab[finequeutailval ++]; /* Select a vertex from the queue */
533
if (finecoartax[finevertnum] >= 0) { /* If selected vertex already matched */
534
for (fineedgenum = fineverttax[finevertnum]; /* For all adjacent vertices */
535
fineedgenum < finevendtax[finevertnum]; fineedgenum ++) {
538
finevertend = fineedgetax[fineedgenum];
539
if (finecoartax[finevertend] == ~0) {
540
finequeutab[finequeuheadval ++] = finevertend;
541
finecoartax[finevertend] = -2;
544
continue; /* Skip to next vertex */
547
if (coarvertnum >= coarvertmax) /* If coarse graph is too large */
548
break; /* Return that we cannot coarsen more */
550
finevertbst = finevertnum; /* No matching vertex found yet */
551
finevelodlt = coarvelomax - ((finegrafptr->velotax != NULL) ? finegrafptr->velotax[finevertnum] : 1);
553
for (fineedgenum = fineverttax[finevertnum]; /* For all adjacent vertices */
554
fineedgenum < finevendtax[finevertnum]; fineedgenum ++) {
558
finevertend = fineedgetax[fineedgenum];
559
finecoarval = finecoartax[finevertend];
561
if (finecoarval < 0) { /* If vertex not matched */
562
if (finecoartax[finevertend] == ~0) { /* If vertex not enqueued */
563
finequeutab[finequeuheadval ++] = finevertend; /* Enqueue it */
564
finecoartax[finevertend] = -2;
566
if ((finevelotax == NULL) || /* And does not create overloads */
567
(finevelodlt >= finevelotax[finevertend])) {
568
finevertbst = finevertend; /* Get matching vertex */
570
while (++ fineedgenum < finevendtax[finevertnum]) { /* Scan and enqueue remaining neighbors */
571
finevertend = fineedgetax[fineedgenum];
572
if (finecoartax[finevertend] == ~0) {
573
finequeutab[finequeuheadval ++] = finevertend;
574
finecoartax[finevertend] = -2;
581
finecoartax[finevertnum] = finevertbst; /* Match both vertices */
582
finecoartax[finevertbst] = finevertnum;
583
coarvertnum ++; /* One more coarse vertex created */
585
else { /* Search for other connected component */
588
for ( ; finecoartax[finepermnum] >= 0; finepermnum ++) { /* Scan vertices in ascending order */
589
#ifdef SCOTCH_DEBUG_GRAPH2
590
if (finepermnum >= finegrafptr->vertnnd) {
591
errorPrint ("graphCoarsenMatchCs: internal error (1)");
592
memFree (finequeutab);
593
return (finegrafptr->vertnbr); /* Coarsening aborted */
595
#endif /* SCOTCH_DEBUG_GRAPH2 */
597
#ifdef SCOTCH_DEBUG_GRAPH2
598
if (finecoartax[finepermnum] != ~0) {
599
errorPrint ("graphCoarsenMatchCs: internal error (2)");
600
memFree (finequeutab);
601
return (finegrafptr->vertnbr); /* Coarsening aborted */
603
#endif /* SCOTCH_DEBUG_GRAPH2 */
604
finevertnum = finepermnum ++; /* Start from found vertex */
606
if (fineverttax[finevertnum] != finevendtax[finevertnum]) { /* If vertex not isolated */
607
finequeutab[finequeuheadval ++] = finevertnum; /* Enqueue it for normal processing */
608
continue; /* Skip to main loop to process it */
611
finequeuheadval = ++ finequeutailval; /* One more vertex enqueued-edqueued */
613
if (coarvertnum >= coarvertmax) /* If coarse graph is too large */
614
break; /* Return that we cannot coarsen more */
616
if (finequeutailval >= finegrafptr->vertnbr) /* If isolated vertex is last available vertex */
617
finevertbst = finevertnum;
619
for ( ; finecoartax[finepermnum] >= 0; finepermnum ++) {
620
#ifdef SCOTCH_DEBUG_GRAPH2
621
if (finepermnum >= finegrafptr->vertnnd) {
622
errorPrint ("graphCoarsenMatchCs: internal error (3)");
623
memFree (finequeutab);
624
return (finegrafptr->vertnbr); /* Coarsening aborted */
626
#endif /* SCOTCH_DEBUG_GRAPH2 */
628
#ifdef SCOTCH_DEBUG_GRAPH2
629
if (finecoartax[finepermnum] != ~0) {
630
errorPrint ("graphCoarsenMatchCs: internal error (4)");
631
memFree (finequeutab);
632
return (finegrafptr->vertnbr); /* Coarsening aborted */
634
#endif /* SCOTCH_DEBUG_GRAPH2 */
635
finevertbst = finepermnum ++; /* Get found vertex */
636
finequeuheadval = ++ finequeutailval; /* One more vertex enqueued-edqueued */
639
finecoartax[finevertnum] = finevertbst; /* Match both vertices */
640
finecoartax[finevertbst] = finevertnum;
641
coarvertnum ++; /* One more coarse vertex created */
645
memFree (finequeutab);
647
return (coarvertnum); /* Return number of coarse vertices */
652
graphCoarsenMatchCh ( /* Crystallographic heavy edge */
653
const Graph * restrict const finegrafptr, /* Fine graph to perform matching on */
654
Gnum * restrict finecoartax, /* Fine to coarse vertex index array */
655
const Gnum coarvertmax, /* Maximum number of vertices to get */
656
const Gnum coarvelomax) /* Maximum vertex weight allowed */
658
Gnum coarvertnum; /* Number of current multinode vertex */
659
const Gnum * restrict fineverttax; /* Based access to vertex array */
660
const Gnum * restrict finevendtax; /* Based access to end vertex array */
661
const Gnum * restrict finevelotax; /* Based access to vertex load array */
662
const Gnum * restrict fineedgetax; /* Based access to edge array */
663
const Gnum * restrict fineedlotax; /* Based access to edge load array */
664
Gnum finevertnum; /* Number of currently selected fine vertex */
665
Gnum * restrict finequeutab;
666
Gnum finequeuheadval;
667
Gnum finequeutailval;
668
Gnum finepermnum; /* Permutation number for finding connected components */
670
if (finegrafptr->edlotax == NULL) /* If no edge loads, perform scan matching instead */
671
return (graphCoarsenMatchCs (finegrafptr, finecoartax, coarvertmax, coarvelomax));
673
fineverttax = finegrafptr->verttax;
674
finevendtax = finegrafptr->vendtax;
675
finevelotax = finegrafptr->velotax;
676
fineedgetax = finegrafptr->edgetax;
677
fineedlotax = finegrafptr->edlotax;
678
if ((finequeutab = memAlloc (finegrafptr->vertnbr * sizeof (Gnum))) == NULL) {
679
errorPrint ("graphCoarsenMatchCh: out of memory");
680
return (graphCoarsenMatchSc (finegrafptr, finecoartax, coarvertmax, coarvelomax)); /* Fallback strategy */
686
finequeutab[0] = finegrafptr->baseval + intRandVal (finegrafptr->vertnbr); /* Start from random vertex */
687
finecoartax[finequeutab[0]] = -2; /* Set vertex as enqueued */
689
for (finepermnum = finegrafptr->baseval; finequeutailval < finegrafptr->vertnbr; ) {
690
if (finequeutailval < finequeuheadval) { /* If vertices remain in queue */
691
Gnum finevertbst; /* Best vertex found till now */
692
Gnum fineedlobst; /* Edge load of current best neighbor */
693
Gnum finevelodlt; /* Overload limit */
694
Gnum fineedgenum; /* Current edge number */
696
finevertnum = finequeutab[finequeutailval ++]; /* Select a vertex from the queue */
698
if (finecoartax[finevertnum] >= 0) { /* If selected vertex already matched */
699
for (fineedgenum = fineverttax[finevertnum]; /* For all adjacent vertices */
700
fineedgenum < finevendtax[finevertnum]; fineedgenum ++) {
703
finevertend = fineedgetax[fineedgenum];
704
if (finecoartax[finevertend] == ~0) {
705
finequeutab[finequeuheadval ++] = finevertend;
706
finecoartax[finevertend] = -2;
709
continue; /* Skip to next vertex */
712
if (coarvertnum >= coarvertmax) /* If coarse graph is too large */
713
break; /* Return that we cannot coarsen more */
715
finevertbst = finevertnum; /* No matching vertex found yet */
717
finevelodlt = coarvelomax - ((finegrafptr->velotax != NULL) ? finegrafptr->velotax[finevertnum] : 1);
719
for (fineedgenum = fineverttax[finevertnum]; /* For all adjacent vertices */
720
fineedgenum < finevendtax[finevertnum]; fineedgenum ++) {
724
finevertend = fineedgetax[fineedgenum];
725
finecoarval = finecoartax[finevertend];
727
if (finecoarval < 0) { /* If vertex not matched */
730
fineedloval = fineedlotax[fineedgenum];
731
if (finecoartax[finevertend] == ~0) { /* If vertex not enqueued */
732
finequeutab[finequeuheadval ++] = finevertend; /* Enqueue it */
733
finecoartax[finevertend] = -2;
735
if (((finevelotax == NULL) || /* And does not create overloads */
736
(finevelodlt >= finevelotax[finevertend])) &&
737
(fineedloval > fineedlobst)) {
738
finevertbst = finevertend; /* Get matching vertex */
739
fineedlobst = fineedloval;
744
finecoartax[finevertnum] = finevertbst; /* Match both vertices */
745
finecoartax[finevertbst] = finevertnum;
746
coarvertnum ++; /* One more coarse vertex created */
748
else { /* Search for other connected component */
751
for ( ; finecoartax[finepermnum] >= 0; finepermnum ++) { /* Scan vertices in ascending order */
752
#ifdef SCOTCH_DEBUG_GRAPH2
753
if (finepermnum >= finegrafptr->vertnnd) {
754
errorPrint ("graphCoarsenMatchCh: internal error (1)");
755
memFree (finequeutab);
756
return (finegrafptr->vertnbr); /* Coarsening aborted */
758
#endif /* SCOTCH_DEBUG_GRAPH2 */
760
#ifdef SCOTCH_DEBUG_GRAPH2
761
if (finecoartax[finepermnum] != ~0) {
762
errorPrint ("graphCoarsenMatchCh: internal error (2)");
763
memFree (finequeutab);
764
return (finegrafptr->vertnbr); /* Coarsening aborted */
766
#endif /* SCOTCH_DEBUG_GRAPH2 */
767
finevertnum = finepermnum ++; /* Start from found vertex */
769
if (fineverttax[finevertnum] != finevendtax[finevertnum]) { /* If vertex not isolated */
770
finequeutab[finequeuheadval ++] = finevertnum; /* Enqueue it for normal processing */
771
continue; /* Skip to main loop to process it */
774
finequeuheadval = ++ finequeutailval; /* One more vertex enqueued-edqueued */
776
if (coarvertnum >= coarvertmax) /* If coarse graph is too large */
777
break; /* Return that we cannot coarsen more */
779
if (finequeutailval >= finegrafptr->vertnbr) /* If isolated vertex is last available vertex */
780
finevertbst = finevertnum;
782
for ( ; finecoartax[finepermnum] >= 0; finepermnum ++) {
783
#ifdef SCOTCH_DEBUG_GRAPH2
784
if (finepermnum >= finegrafptr->vertnnd) {
785
errorPrint ("graphCoarsenMatchCh: internal error (3)");
786
memFree (finequeutab);
787
return (finegrafptr->vertnbr); /* Coarsening aborted */
789
#endif /* SCOTCH_DEBUG_GRAPH2 */
791
#ifdef SCOTCH_DEBUG_GRAPH2
792
if (finecoartax[finepermnum] != ~0) {
793
errorPrint ("graphCoarsenMatchCh: internal error (4)");
794
memFree (finequeutab);
795
return (finegrafptr->vertnbr); /* Coarsening aborted */
797
#endif /* SCOTCH_DEBUG_GRAPH2 */
798
finevertbst = finepermnum ++; /* Get found vertex */
799
finequeuheadval = ++ finequeutailval; /* One more vertex enqueued-edqueued */
802
finecoartax[finevertnum] = finevertbst; /* Match both vertices */
803
finecoartax[finevertbst] = finevertnum;
804
coarvertnum ++; /* One more coarse vertex created */
808
memFree (finequeutab);
810
return (coarvertnum); /* Return number of coarse vertices */
added
removed
src/libscotch/graph_coarsen.c
