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 : hmesh_induce.c **/
36
/** AUTHOR : Francois PELLEGRINI **/
38
/** FUNCTION : This module handles the halo source **/
39
/** mesh subgraph-making functions. **/
41
/** DATES : # Version 4.0 : from : 07 jan 2002 **/
42
/** to 11 may 2004 **/
43
/** # Version 5.0 : from : 22 dec 2006 **/
44
/** to 10 sep 2007 **/
46
/************************************************************/
49
** The defines and includes.
61
/*********************************************/
63
/* These routines handle halo source meshes. */
65
/*********************************************/
67
/* This routine builds the halo mesh induced
68
** by the original halo mesh and the array of
69
** selected node vertices. Elements which are
70
** adjacent to the selected nodes are themselves
71
** selected, as well as their adjacent node
72
** vertices, which comprise the new halo.
73
** In the induced halo mesh, elements are
74
** placed first, then non-halo nodes, then
75
** halo nodes. This order is quite important
76
** as it eases the building of vertex separation
77
** meshes from halo meshes, just by ignoring
79
** The induced vnumtab array is a baseval-based
80
** list of the selected node vertices if the
81
** original halo mesh does not have a vnumtab, or
82
** the proper subset of the original vnumtab else.
90
const Hmesh * restrict const orgmeshptr, /* Pointer to original graph */
91
const GraphPart * restrict const orgparttax, /* Array of vertex partition flags */
92
const GraphPart orgpartval, /* Partition value of vertices to keep (0 or 1) */
93
const Gnum orgvelmnbr, /* Number of (maybe isolated) element vertices in selected part */
94
const Gnum orgvnodnbr, /* Number of node vertices in selected part */
95
const Gnum orgvnspnbr, /* Number of node vertices in separator */
96
Hmesh * restrict const indmeshptr) /* Pointer to induced halo submesh */
98
Gnum orgvelmnum; /* Number of current element vertex in original halo mesh */
99
Gnum orgvnodnum; /* Number of current node vertex in original halo mesh */
100
Gnum * restrict orgindxtax; /* Original to induced vertex number translation array */
101
Gnum indvertnbr; /* Upper bound on the number of vertices in induced halo mesh */
102
Gnum indvertnum; /* Number of current vertex in induced mesh graph */
103
Gnum indvelmnbr; /* Number of element vertices in induced halo mesh */
104
Gnum indveihnbr; /* Number of newly created halo-isolated elements */
105
Gnum indvnodnbr; /* Upper bound on the number of node vertices in induced halo mesh */
106
Gnum indvnodnum; /* Number of current node vertex in induced halo mesh */
107
Gnum * restrict indedgetax; /* Based access to induced mesh graph edge arrays */
108
Gnum indedgenbr; /* (Approximate) number of edges in induced halo mesh */
109
Gnum indedgenum; /* Number of current edge in induced halo mesh */
110
Gnum * restrict indvnuhtax; /* Array of vertex numbers for halo nodes (aka vnumtab) */
117
indvelmnbr = orgvelmnbr - orgmeshptr->veihnbr; /* Remove known halo-isolated elements */
118
if (orgpartval == 0) /* If submesh is part zero */
119
indvelmnbr -= orgmeshptr->m.veisnbr; /* Also remove isolated elements, which belong to it */
121
indvnodnbr = orgvnodnbr + orgvnspnbr + orgmeshptr->m.vnodnnd - orgmeshptr->vnohnnd; /* Compute upper bound on number of node vertices */
122
indvertnbr = indvnodnbr + indvelmnbr;
124
indedgenbr = ((indvertnbr * orgmeshptr->m.degrmax) < orgmeshptr->m.edgenbr) /* Choose best upper bound on number of edges */
125
? (indvertnbr * orgmeshptr->m.degrmax) : orgmeshptr->m.edgenbr;
127
memSet (indmeshptr, 0, sizeof (Hmesh)); /* Initialize halo mesh fields */
128
indmeshptr->m.baseval = orgmeshptr->m.baseval; /* Inherit mesh properties */
129
indmeshptr->m.flagval = MESHFREETABS | MESHVERTGROUP;
130
indmeshptr->m.velmnbr = indvelmnbr;
131
indmeshptr->m.velmbas = indmeshptr->m.baseval; /* Elements are placed first */
132
indmeshptr->m.velmnnd =
133
indmeshptr->m.vnodbas = orgvelmnbr + indmeshptr->m.baseval; /* Node vertices are placed after elements */
134
indmeshptr->m.veisnbr = 0; /* All isolated elements will be removed in submesh */
136
indvelonbr = (orgmeshptr->m.velotax != NULL) ? indmeshptr->m.velmnbr : 0;
137
indvnlonbr = (orgmeshptr->m.vnlotax != NULL) ? indvnodnbr : 0;
139
if (memAllocGroup ((void **) (void *)
140
&indmeshptr->m.verttax, (size_t) ((indvertnbr + 1) * sizeof (Gnum)),
141
&indmeshptr->vehdtax, (size_t) ( orgvelmnbr * sizeof (Gnum)), /* vehdtab is limited to elements */
142
&indmeshptr->m.velotax, (size_t) ( indvelonbr * sizeof (Gnum)),
143
&indmeshptr->m.vnlotax, (size_t) ( indvnlonbr * sizeof (Gnum)),
144
&indmeshptr->m.vnumtax, (size_t) ( orgvnodnbr * sizeof (Gnum)), NULL) == NULL) { /* vnumtab is of size vnohnbr */
145
errorPrint ("hmeshInducePart: out of memory (1)"); /* Allocate induced mesh graph structure */
148
indmeshptr->m.verttax -= indmeshptr->m.baseval;
149
indmeshptr->m.vendtax = indmeshptr->m.verttax + 1; /* Compact array */
150
indmeshptr->m.velotax = (indvelonbr != 0) ? (indmeshptr->m.velotax - indmeshptr->m.velmbas) : NULL;
151
indmeshptr->m.vnlotax = (indvnlonbr != 0) ? (indmeshptr->m.vnlotax - indmeshptr->m.vnodbas) : NULL;
152
indmeshptr->m.vnumtax -= indmeshptr->m.vnodbas; /* Only for non-halo nodes */
153
indmeshptr->m.degrmax = orgmeshptr->m.degrmax;
154
indmeshptr->vnohnbr = orgvnodnbr;
155
indmeshptr->vnohnnd = indmeshptr->m.vnodbas + orgvnodnbr;
156
indmeshptr->vehdtax -= indmeshptr->m.velmbas;
157
indmeshptr->vnhlsum = orgvnodnbr; /* Assume no vertex loads */
159
if (memAllocGroup ((void **) (void *)
160
&indedgetax, (size_t) (indedgenbr * sizeof (Gnum)),
161
&orgindxtax, (size_t) ((orgmeshptr->m.velmnbr + orgmeshptr->m.vnodnbr) * sizeof (Gnum)),
162
&indvnuhtax, (size_t) ((orgvnspnbr + orgmeshptr->m.vnodnnd - orgmeshptr->vnohnnd) * sizeof (Gnum)), NULL) == NULL) {
163
errorPrint ("hmeshInducePart: out of memory (2)"); /* Allocate induced mesh graph structure */
164
hmeshExit (indmeshptr);
167
indedgetax -= indmeshptr->m.baseval;
168
orgindxtax -= orgmeshptr->m.baseval;
169
indvnuhtax -= indmeshptr->vnohnnd; /* Base array so as to catch halo nodes only */
172
for (orgvnodnum = orgmeshptr->m.vnodbas, /* For all original non-halo node vertices */
173
indvnodnum = indmeshptr->m.vnodbas; /* And assuming all elements will be kept */
174
orgvnodnum < orgmeshptr->vnohnnd; orgvnodnum ++) {
175
if (orgparttax[orgvnodnum] == orgpartval) { /* If in right part */
176
orgindxtax[orgvnodnum] = indvnodnum; /* Set new index of node */
177
indmeshptr->m.vnumtax[indvnodnum] = orgvnodnum - (orgmeshptr->m.vnodbas - orgmeshptr->m.baseval);
178
if (orgmeshptr->m.vnlotax != NULL)
179
indvnhlsum += (indmeshptr->m.vnlotax[indvnodnum] = orgmeshptr->m.vnlotax[orgvnodnum]);
182
else if (orgparttax[orgvnodnum] == 2) /* If node belongs to separator */
183
orgindxtax[orgvnodnum] = ~0; /* Pre-set array for separator nodes */
185
#ifdef SCOTCH_DEBUG_HMESH2
186
if ((indvnodnum - indmeshptr->m.vnodbas) != orgvnodnbr) {
187
errorPrint ("hmeshInducePart: internal error (1)");
188
memFree (indedgetax + indmeshptr->m.baseval);
189
hmeshExit (indmeshptr);
192
#endif /* SCOTCH_DEBUG_HMESH2 */
193
memSet (orgindxtax + orgmeshptr->vnohnnd, ~0, (orgmeshptr->m.vnodnnd - orgmeshptr->vnohnnd) * sizeof (Gnum)); /* Pre-set halo node vertices */
198
for (orgvelmnum = orgmeshptr->m.velmbas, /* For all elements of original graph */
199
indvertnum = indedgenum = indmeshptr->m.baseval; /* Elements are placed first in vertex array */
200
orgvelmnum < orgmeshptr->m.velmnnd; orgvelmnum ++) {
201
if (orgparttax[orgvelmnum] == orgpartval) { /* If element belongs to right part */
203
Gnum indedgennd; /* Index of after-last edge position in edge array */
204
Gnum indedhdnum; /* Index of after-last edge linking to non-halo vertices */
206
orgedgenum = orgmeshptr->m.verttax[orgvelmnum];
207
if (orgedgenum == orgmeshptr->vehdtax[orgvelmnum]) /* If (halo-)isolated element vertex */
208
continue; /* Discard element in induced submesh */
210
#ifdef SCOTCH_DEBUG_HMESH2
211
if (indvertnum >= indmeshptr->m.velmnnd) { /* If too many element vertices kept */
212
errorPrint ("hmeshInducePart: internal error (2)"); /* Maybe a problem with veisnbr or veihnbr */
213
memFree (indedgetax + indmeshptr->m.baseval);
214
hmeshExit (indmeshptr);
217
#endif /* SCOTCH_DEBUG_HMESH2 */
219
indmeshptr->m.verttax[indvertnum] = indedgenum;
220
indedhdnum = orgmeshptr->m.vendtax[orgvelmnum] - orgmeshptr->m.verttax[orgvelmnum] + indedgenum;
221
indedgennd = indedhdnum;
222
if (orgmeshptr->m.velotax != NULL) {
225
orgveloval = orgmeshptr->m.velotax[orgvelmnum];
226
indmeshptr->m.velotax[indvertnum] = orgveloval;
227
indvelosum += orgveloval;
230
for ( ; orgedgenum < orgmeshptr->m.vendtax[orgvelmnum]; orgedgenum ++) {
233
orgvertend = orgmeshptr->m.edgetax[orgedgenum];
235
if (orgindxtax[orgvertend] == ~0) { /* If found yet un-numbered halo node */
236
#ifdef SCOTCH_DEBUG_HMESH2
237
if ((orgvertend < orgmeshptr->vnohnnd) &&
238
(orgparttax[orgvertend] != 2)) {
239
errorPrint ("hmeshInducePart: internal error (3)");
240
memFree (indedgetax + indmeshptr->m.baseval);
241
hmeshExit (indmeshptr);
244
#endif /* SCOTCH_DEBUG_HMESH2 */
245
if (orgmeshptr->m.vnlotax != NULL) {
248
orgvnloval = orgmeshptr->m.vnlotax[orgvertend];
249
indmeshptr->m.vnlotax[indvnodnum] = orgvnloval;
250
indvnlosum += orgvnloval;
252
orgindxtax[orgvertend] = indvnodnum; /* Set number of halo node */
253
indvnuhtax[indvnodnum] = orgvertend; /* Keep number of halo node */
255
indedgetax[-- indedhdnum] = orgindxtax[orgvertend];
258
if (orgindxtax[orgvertend] < indmeshptr->vnohnnd) /* If non-halo vertex */
259
indedgetax[indedgenum ++] = orgindxtax[orgvertend];
260
else /* Else if halo vertex */
261
indedgetax[-- indedhdnum] = orgindxtax[orgvertend];
263
#ifdef SCOTCH_DEBUG_HMESH2
264
if (indedgenum != indedhdnum) {
265
errorPrint ("hmeshInducePart: internal error (4)");
266
memFree (indedgetax + indmeshptr->m.baseval);
267
hmeshExit (indmeshptr);
270
#endif /* SCOTCH_DEBUG_HMESH2 */
271
if (indedhdnum == indmeshptr->m.verttax[indvertnum]) /* If element has halo nodes only */
272
indveihnbr ++; /* One more halo-isolated element created */
274
indmeshptr->vehdtax[indvertnum] = indedhdnum;
275
indedgenum = indedgennd;
276
orgindxtax[orgvelmnum] = indvertnum;
277
indvertnum ++; /* One more element created */
280
orgindxtax[orgvelmnum] = ~0;
282
#ifdef SCOTCH_DEBUG_HMESH2
283
if (indvertnum != indmeshptr->m.velmnnd) {
284
errorPrint ("hmeshInducePart: internal error (5)"); /* Maybe a problem with veisnbr or veihnbr */
285
memFree (indedgetax + indmeshptr->m.baseval);
286
hmeshExit (indmeshptr);
289
#endif /* SCOTCH_DEBUG_HMESH2 */
291
indmeshptr->veihnbr = indveihnbr;
293
indmeshptr->m.vnodnbr = indvnodnum - indmeshptr->m.vnodbas;
294
indmeshptr->m.vnodnnd = indvertnum + indmeshptr->m.vnodnbr;
295
indmeshptr->m.velosum = (indmeshptr->m.velotax != NULL) ? indvelosum : indmeshptr->m.velmnbr;
296
if (indmeshptr->m.vnlotax != NULL) { /* If vertex loads wanted */
297
indmeshptr->m.vnlosum = indvnhlsum + indvnlosum;
298
indmeshptr->vnhlsum = indvnhlsum;
301
indmeshptr->m.vnlosum = indmeshptr->m.vnodnbr;
302
indmeshptr->vnhlsum = indmeshptr->vnohnbr;
305
indedgenbr = 2 * (indedgenum - indmeshptr->m.baseval); /* Twice as many arcs as element arcs */
306
for ( ; indvertnum < indmeshptr->vnohnnd; indvertnum ++) { /* For all non-halo induced node vertices */
310
orgvnodnum = indmeshptr->m.vnumtax[indvertnum] + (orgmeshptr->m.vnodbas - orgmeshptr->m.baseval); /* Get number of original node */
312
indmeshptr->m.verttax[indvertnum] = indedgenum;
314
for (orgedgenum = orgmeshptr->m.verttax[orgvnodnum];
315
orgedgenum < orgmeshptr->m.vendtax[orgvnodnum]; orgedgenum ++) {
318
orgvertend = orgmeshptr->m.edgetax[orgedgenum];
319
#ifdef SCOTCH_DEBUG_HMESH2
320
if (orgindxtax[orgvertend] == ~0) {
321
errorPrint ("hmeshInducePart: internal error (6)");
322
memFree (indedgetax + indmeshptr->m.baseval);
323
hmeshExit (indmeshptr);
326
#endif /* SCOTCH_DEBUG_HMESH2 */
327
indedgetax[indedgenum ++] = orgindxtax[orgvertend];
331
indmeshptr->enohnbr = indedgenum - indmeshptr->m.baseval;
333
for ( ; indvertnum < indmeshptr->m.vnodnnd; indvertnum ++) { /* For all halo induced node vertices */
337
orgvnodnum = indvnuhtax[indvertnum]; /* Get number of original node */
339
indmeshptr->m.verttax[indvertnum] = indedgenum;
341
for (orgedgenum = orgmeshptr->m.verttax[orgvnodnum];
342
orgedgenum < orgmeshptr->m.vendtax[orgvnodnum]; orgedgenum ++) {
345
orgvertend = orgmeshptr->m.edgetax[orgedgenum];
346
if (orgindxtax[orgvertend] != ~0) { /* If end element belongs to right part */
347
indedgetax[indedgenum ++] = orgindxtax[orgvertend];
351
indmeshptr->m.verttax[indvertnum] = indedgenum; /* Set end of edge array */
352
indmeshptr->m.edgenbr = indedgenum - indmeshptr->m.baseval;
353
indmeshptr->m.vnodnnd = indvertnum; /* Record number of induced non-element vertices */
354
indmeshptr->m.vnodnbr = indvertnum - indmeshptr->m.vnodbas;
356
if (orgmeshptr->m.vnumtax != NULL) { /* If source mesh is not original mesh */
357
for (indvnodnum = indmeshptr->m.vnodbas; indvnodnum < indmeshptr->vnohnnd; indvnodnum ++)
358
indmeshptr->m.vnumtax[indvnodnum] = orgmeshptr->m.vnumtax[indmeshptr->m.vnumtax[indvnodnum] + (orgmeshptr->m.vnodbas - orgmeshptr->m.baseval)];
361
indmeshptr->m.edgetax = memRealloc (indedgetax + indmeshptr->m.baseval, indedgenbr * sizeof (Gnum));
362
indmeshptr->m.edgetax -= indmeshptr->m.baseval;
364
#ifdef SCOTCH_DEBUG_HMESH2
365
if (hmeshCheck (indmeshptr) != 0) { /* Check halo mesh consistency */
366
errorPrint ("hmeshInducePart: inconsistent halo mesh data");
367
hmeshExit (indmeshptr);
370
#endif /* SCOTCH_DEBUG_HMESH2 */
added
removed
src/libscotch/hmesh_induce.c
