1 /* Copyright 2007,2008,2010 ENSEIRB, INRIA & CNRS
2 **
3 ** This file is part of the Scotch software package for static mapping,
4 ** graph partitioning and sparse matrix ordering.
5 **
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".
11 **
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
16 ** liability.
17 **
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.
28 **
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.
31 */
32 /************************************************************/
33 /** **/
34 /** NAME : hdgraph_induce.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module handles the halo source **/
39 /** graph subgraph-making functions. **/
40 /** **/
41 /** DATES : # Version 5.0 : from : 19 apr 2006 **/
42 /** to : 10 sep 2007 **/
43 /** # Version 5.1 : from : 27 jun 2008 **/
44 /** to : 22 oct 2010 **/
45 /** **/
46 /************************************************************/
47
48 /*
49 ** The defines and includes.
50 */
51
52 #define HDGRAPH
53
54 #include "module.h"
55 #include "common.h"
56 #include "dgraph.h"
57 #include "hdgraph.h"
58
59 /******************************/
60 /* */
61 /* These routines handle halo */
62 /* distributed source graphs. */
63 /* */
64 /******************************/
65
66 /* This routine builds the graph induced
67 ** by the original graph and the list of
68 ** selected vertices.
69 ** The induced vnumtab array is the global
70 ** translation of the list array if the
71 ** original graph does not have a vnumtab,
72 ** or the proper subset of the original
73 ** vnumtab else.
74 ** It returns:
75 ** - 0 : on success.
76 ** - !0 : on error.
77 */
78
79 int
hdgraphInduceList(Hdgraph * restrict const orggrafptr,const Gnum indlistnbr,const Gnum * restrict const indlisttab,Hdgraph * restrict const indgrafptr)80 hdgraphInduceList (
81 Hdgraph * restrict const orggrafptr,
82 const Gnum indlistnbr,
83 const Gnum * restrict const indlisttab, /* Local list of kept vertices */
84 Hdgraph * restrict const indgrafptr)
85 {
86 const Gnum * restrict orgvertloctax;
87 const Gnum * restrict orgvendloctax;
88 const Gnum * restrict orgveloloctax;
89 const Gnum * restrict orgedgegsttax;
90 const Gnum * restrict orgedgeloctax;
91 Gnum * restrict orgindxgsttax; /* Based access to vertex translation array */
92 Gnum * restrict orgindxhaltax; /* Based access to halo vertex translation array */
93 Gnum * restrict indvertloctax;
94 Gnum * restrict indveloloctax;
95 Gnum indvertlocnnd; /* Based index of end of local vertex array */
96 Gnum indvertlocnum; /* Number of current vertex in induced graph */
97 Gnum indvertglbnum; /* Number of current vertex in global ordering */
98 Gnum * restrict indvendloctax;
99 Gnum indvelolocnbr; /* Size of local vertex load array */
100 Gnum indvelolocsum; /* Sum of vertex loads */
101 Gnum indvhallocnum; /* Number of halo vertex to be declared */
102 Gnum * restrict indedgeloctax;
103 Gnum indedgelocmax; /* (Approximate) number of edges in induced graph */
104 Gnum indedgelocsiz; /* Real size of edge array, including halo */
105 Gnum indedgelocnbr; /* Real number of edges in induced graph */
106 Gnum indedgelocnum;
107 Gnum inddegrlocmax; /* Local maximum degree over non-halo vertices */
108 const Gnum * restrict indlisttax; /* Based access to list of kept vertices */
109 int cheklocval;
110 int chekglbval;
111
112 if (dgraphGhst (&orggrafptr->s) != 0) { /* Compute ghost edge array if not already present */
113 errorPrint ("hdgraphInduceList: cannot compute ghost edge array");
114 return (1);
115 }
116
117 memSet (indgrafptr, 0, sizeof (Hdgraph)); /* Pre-initialize graph fields */
118
119 indgrafptr->s.proccomm = orggrafptr->s.proccomm;
120 indgrafptr->s.procglbnbr = orggrafptr->s.procglbnbr;
121 indgrafptr->s.proclocnum = orggrafptr->s.proclocnum;
122 indgrafptr->s.flagval = (DGRAPHFREEALL ^ DGRAPHFREECOMM) | DGRAPHVERTGROUP | DGRAPHEDGEGROUP; /* For premature freeing on error; do not free vhndloctab as it is grouped with vertloctab */
123
124 if (orggrafptr->s.veloloctax != NULL) {
125 indvelolocnbr = indlistnbr;
126 indvelolocsum = 0;
127 }
128 else {
129 indvelolocnbr = 0;
130 indvelolocsum = indlistnbr;
131 }
132 indedgelocmax = orggrafptr->s.edgelocnbr; /* Choose best upper bound on number of edges (avoid multiply overflow) */
133 if ((orggrafptr->s.degrglbmax > 0) && (indlistnbr < (indedgelocmax / orggrafptr->s.degrglbmax)))
134 indedgelocmax = indlistnbr * orggrafptr->s.degrglbmax;
135 indedgelocmax += orggrafptr->ehallocnbr;
136
137 cheklocval =
138 chekglbval = 0;
139 if (memAllocGroup ((void **) (void *) /* Allocate distributed graph private data */
140 &indgrafptr->s.procdsptab, (size_t) ((orggrafptr->s.procglbnbr + 1) * sizeof (Gnum)),
141 &indgrafptr->s.proccnttab, (size_t) (orggrafptr->s.procglbnbr * sizeof (Gnum)),
142 &indgrafptr->s.procngbtab, (size_t) (orggrafptr->s.procglbnbr * sizeof (int)),
143 &indgrafptr->s.procrcvtab, (size_t) (orggrafptr->s.procglbnbr * sizeof (int)),
144 &indgrafptr->s.procsndtab, (size_t) (orggrafptr->s.procglbnbr * sizeof (int)), NULL) == NULL) {
145 errorPrint ("hdgraphInduceList: out of memory (1)");
146 cheklocval = 1;
147 }
148 else if (memAllocGroup ((void **) (void *) /* Allocate distributed graph public data */
149 &indgrafptr->s.vertloctax, (size_t) ((indlistnbr + 1) * sizeof (Gnum)), /* Compact vertex arrays */
150 &indgrafptr->s.vendloctax, (size_t) (indlistnbr * sizeof (Gnum)), /* Vertex end array for non-halo vertices */
151 &indgrafptr->s.vnumloctax, (size_t) (indlistnbr * sizeof (Gnum)),
152 &indgrafptr->s.veloloctax, (size_t) (indvelolocnbr * sizeof (Gnum)), NULL) == NULL) {
153 errorPrint ("hdgraphInduceList: out of memory (2)");
154 cheklocval = 1;
155 }
156 else if (indgrafptr->s.vertloctax -= orggrafptr->s.baseval,
157 indgrafptr->s.vendloctax -= orggrafptr->s.baseval,
158 indgrafptr->s.vnumloctax -= orggrafptr->s.baseval,
159 indgrafptr->s.veloloctax = ((orggrafptr->s.veloloctax != NULL) ? indgrafptr->s.veloloctax - orggrafptr->s.baseval : NULL),
160 memAllocGroup ((void **) (void *)
161 &indgrafptr->s.edgeloctax, (size_t) (indedgelocmax * sizeof (Gnum)), /* Pre-allocate space for edgeloctab */
162 &orgindxgsttax, (size_t) (orggrafptr->s.vertgstnbr * sizeof (Gnum)), /* orgindxgsttab and orgindxhaltab are at the end */
163 &orgindxhaltax, (size_t) (orggrafptr->vhallocnbr * sizeof (Gnum)), NULL) == NULL) {
164 errorPrint ("hdgraphInduceList: out of memory (3)");
165 cheklocval = 1;
166 }
167 else
168 indgrafptr->s.edgeloctax -= orggrafptr->s.baseval;
169
170 if (cheklocval != 0) { /* In case of memory error */
171 Gnum procngbnum;
172 int dummyval;
173
174 dummyval = -1;
175 chekglbval = 1;
176 if (MPI_Allgather (&dummyval, 1, GNUM_MPI, /* Use proccnttab of orggraf as dummy receive array (will be regenerated) */
177 orggrafptr->s.proccnttab, 1, GNUM_MPI, indgrafptr->s.proccomm) != MPI_SUCCESS)
178 errorPrint ("hdgraphInduceList: communication error (1)");
179
180 for (procngbnum = 1; procngbnum <= orggrafptr->s.procglbnbr; procngbnum ++) /* Rebuild proccnttab of orggraf */
181 orggrafptr->s.proccnttab[procngbnum - 1] = orggrafptr->s.procdsptab[procngbnum] - orggrafptr->s.procdsptab[procngbnum - 1];
182 }
183 else {
184 indgrafptr->s.procvrttab = indgrafptr->s.procdsptab; /* Graph does not have holes */
185 indgrafptr->s.procdsptab[0] = indlistnbr;
186 if (MPI_Allgather (&indgrafptr->s.procdsptab[0], 1, GNUM_MPI,
187 &indgrafptr->s.proccnttab[0], 1, GNUM_MPI, indgrafptr->s.proccomm) != MPI_SUCCESS) {
188 errorPrint ("hdgraphInduceList: communication error (2)");
189 chekglbval = 1;
190 }
191 else {
192 Gnum procngbnum;
193
194 indgrafptr->s.procdsptab[0] = orggrafptr->s.baseval; /* Build vertex-to-process array */
195 for (procngbnum = 0; procngbnum < indgrafptr->s.procglbnbr; procngbnum ++) { /* Process potential error flags from other processes */
196 if (indgrafptr->s.proccnttab[procngbnum] < 0) { /* If error notified by another process */
197 chekglbval = 1;
198 break;
199 }
200 indgrafptr->s.procdsptab[procngbnum + 1] = indgrafptr->s.procdsptab[procngbnum] + indgrafptr->s.proccnttab[procngbnum];
201 }
202 }
203 }
204 if (chekglbval != 0) { /* If something went wrong in all of the above */
205 hdgraphExit (indgrafptr);
206 return (1);
207 }
208
209 memSet (orgindxgsttax, ~0, orggrafptr->s.vertgstnbr * sizeof (Gnum)); /* Preset index arrays */
210 orgindxgsttax -= orggrafptr->s.baseval;
211 memSet (orgindxhaltax, ~0, orggrafptr->vhallocnbr * sizeof (Gnum));
212 orgindxhaltax -= orggrafptr->s.baseval;
213
214 indlisttax = indlisttab - orggrafptr->s.baseval;
215 indvertlocnnd = indlistnbr + orggrafptr->s.baseval;
216 for (indvertlocnum = orggrafptr->s.baseval, indvertglbnum = indgrafptr->s.procdsptab[indgrafptr->s.proclocnum]; /* Set adjustment for global ordering */
217 indvertlocnum < indvertlocnnd; indvertlocnum ++, indvertglbnum ++)
218 orgindxgsttax[indlisttax[indvertlocnum]] = indvertglbnum; /* Mark selected vertices */
219
220 if (dgraphHaloSync (&orggrafptr->s, (byte *) (orgindxgsttax + orggrafptr->s.baseval), GNUM_MPI) != 0) { /* Share global indexing of subgraph vertices */
221 errorPrint ("hdgraphInduceList: cannot perform halo exchange");
222 hdgraphExit (indgrafptr);
223 return (1);
224 }
225
226 orgvertloctax = orggrafptr->s.vertloctax;
227 orgvendloctax = orggrafptr->s.vendloctax;
228 orgveloloctax = orggrafptr->s.veloloctax;
229 orgedgegsttax = orggrafptr->s.edgegsttax;
230 orgedgeloctax = orggrafptr->s.edgeloctax;
231 indvertloctax = indgrafptr->s.vertloctax;
232 indvendloctax = indgrafptr->s.vendloctax;
233 indveloloctax = indgrafptr->s.veloloctax;
234 indedgeloctax = indgrafptr->s.edgeloctax;
235 inddegrlocmax = 0;
236 for (indvertlocnum = indedgelocnum = indvhallocnum = orggrafptr->s.baseval, indedgelocnbr = 0;
237 indvertlocnum < indvertlocnnd; indvertlocnum ++) {
238 Gnum orgvertlocnum;
239 Gnum orgedgelocnum;
240 Gnum orgdegrlocval;
241 Gnum inddegrlocval;
242 Gnum indedgelocnnd;
243
244 orgvertlocnum = indlisttax[indvertlocnum];
245 orgdegrlocval = orgvendloctax[orgvertlocnum] - orgvertloctax[orgvertlocnum];
246
247 indvertloctax[indvertlocnum] = indedgelocnum;
248 if (orgveloloctax != NULL) { /* If graph has vertex weights */
249 indvelolocsum += /* Accumulate vertex loads */
250 indveloloctax[indvertlocnum] = orgveloloctax[orgvertlocnum];
251 }
252 indedgelocnnd = indedgelocnum + orgdegrlocval;
253 #ifdef SCOTCH_DEBUG_HDGRAPH2
254 if (indedgelocnnd > (indedgelocmax + orggrafptr->s.baseval)) {
255 errorPrint ("hdgraphInduceList: internal error (1)");
256 return (1);
257 }
258 #endif /* SCOTCH_DEBUG_HDGRAPH2 */
259 for (orgedgelocnum = orgvertloctax[orgvertlocnum]; /* Process local and ghost non-halo vertices */
260 orgedgelocnum < orgvendloctax[orgvertlocnum]; orgedgelocnum ++) {
261 Gnum orgvertlocend;
262 Gnum indvertgstend;
263
264 orgvertlocend = orgedgegsttax[orgedgelocnum];
265 #ifdef SCOTCH_DEBUG_HDGRAPH2
266 if ((orgvertlocend < orggrafptr->s.baseval) || (orgvertlocend > orggrafptr->s.vertgstnnd)) {
267 errorPrint ("hdgraphInduceList: internal error (2)");
268 return (1);
269 }
270 #endif /* SCOTCH_DEBUG_HDGRAPH2 */
271 indvertgstend = orgindxgsttax[orgvertlocend];
272 if (indvertgstend >= 0) /* If edge is local or halo */
273 indedgeloctax[indedgelocnum ++] = indvertgstend; /* Keep it as regular edge */
274 else { /* If edge is halo edge */
275 if (indvertgstend == ~0) /* If halo vertex not assigned yet */
276 orgindxgsttax[orgvertlocend] = indvertgstend = -2 - indvhallocnum ++; /* Set new halo number */
277 indedgeloctax[-- indedgelocnnd] = -2 - indvertgstend;
278 }
279 }
280 #ifdef SCOTCH_DEBUG_HDGRAPH2
281 if (indedgelocnnd != indedgelocnum) {
282 errorPrint ("hdgraphInduceList: internal error (3)");
283 return (1);
284 }
285 #endif /* SCOTCH_DEBUG_HDGRAPH2 */
286 indvendloctax[indvertlocnum] = indedgelocnum;
287 inddegrlocval = indedgelocnum - indvertloctax[indvertlocnum];
288 indedgelocnbr += inddegrlocval;
289 if (inddegrlocmax < inddegrlocval)
290 inddegrlocmax = inddegrlocval;
291
292 for (indedgelocnum = indvertloctax[indvertlocnum] + orgdegrlocval; /* Process local halo vertices */
293 orgedgelocnum < orggrafptr->vhndloctax[orgvertlocnum]; orgedgelocnum ++) {
294 Gnum orgvhallocend;
295 Gnum indvhallocend;
296
297 orgvhallocend = orgedgeloctax[orgedgelocnum]; /* Halo vertices only exist in the edgeloctab array */
298 #ifdef SCOTCH_DEBUG_HDGRAPH2
299 if ((orgvhallocend < orggrafptr->s.baseval) || (orgvhallocend >= (orggrafptr->vhallocnbr + orggrafptr->s.baseval))) {
300 errorPrint ("hdgraphInduceList: inconsistent halo vertex numbers");
301 hdgraphExit (indgrafptr);
302 return (1);
303 }
304 if (indedgelocnum >= (indedgelocmax + orggrafptr->s.baseval)) {
305 errorPrint ("hdgraphInduceList: internal error (4)");
306 return (1);
307 }
308 #endif /* SCOTCH_DEBUG_HDGRAPH2 */
309 indvhallocend = orgindxhaltax[orgvhallocend];
310 if (indvhallocend == ~0) /* If halo vertex not assigned yet */
311 orgindxhaltax[orgvhallocend] = indvhallocend = indvhallocnum ++; /* Set new halo number */
312 indgrafptr->s.edgeloctax[indedgelocnum ++] = indvhallocend;
313 }
314 }
315 indvertloctax[indvertlocnum] = indedgelocnum; /* Mark end of edge array for vhndloctax */
316 indedgelocsiz = indedgelocnum - orggrafptr->s.baseval; /* Global number of edges, both non-halo and halo */
317
318 indgrafptr->s.edgeloctax = memRealloc (indgrafptr->s.edgeloctax + orggrafptr->s.baseval,
319 (size_t) (indedgelocsiz * sizeof (Gnum)));
320 indgrafptr->s.edgeloctax -= orggrafptr->s.baseval;
321
322 if (orggrafptr->s.vnumloctax != NULL) { /* Adjust vnumloctax */
323 for (indvertlocnum = orggrafptr->s.baseval; indvertlocnum < indvertlocnnd; indvertlocnum ++)
324 indgrafptr->s.vnumloctax[indvertlocnum] = orggrafptr->s.vnumloctax[indlisttax[indvertlocnum]];
325 }
326 else {
327 Gnum orgvertglbadj;
328
329 orgvertglbadj = orggrafptr->s.procvrttab[orggrafptr->s.proclocnum] - orggrafptr->s.baseval; /* Set adjustement for global ordering */
330 for (indvertlocnum = orggrafptr->s.baseval; indvertlocnum < indvertlocnnd; indvertlocnum ++)
331 indgrafptr->s.vnumloctax[indvertlocnum] = indlisttax[indvertlocnum] + orgvertglbadj;
332 }
333 indgrafptr->vhallocnbr = indvhallocnum - orggrafptr->s.baseval;
334 indgrafptr->vhndloctax = indgrafptr->s.vertloctax + 1; /* Compact edge array with halo vertices */
335 indgrafptr->ehallocnbr = indedgelocsiz - indedgelocnbr; /* Get number of halo edges by difference */
336 indgrafptr->levlnum = orggrafptr->levlnum + 1; /* Induced subgraph is one level below */
337
338 indgrafptr->s.baseval = orggrafptr->s.baseval;
339 indgrafptr->s.vertlocnbr = indlistnbr;
340 indgrafptr->s.vertlocnnd = indlistnbr + orggrafptr->s.baseval;
341 indgrafptr->s.velolocsum = indvelolocsum;
342 indgrafptr->s.edgelocnbr = indedgelocnbr;
343 indgrafptr->s.edgelocsiz = indedgelocsiz;
344 indgrafptr->s.degrglbmax = orggrafptr->s.degrglbmax;
345 if (dgraphBuild4 (&indgrafptr->s) != 0) {
346 errorPrint ("hdgraphInduceList: cannot build induced graph");
347 return (1);
348 }
349 #ifdef SCOTCH_DEBUG_HDGRAPH2
350 if (hdgraphCheck (indgrafptr) != 0) { /* Check graph consistency */
351 errorPrint ("hdgraphInduceList: internal error (5)");
352 hdgraphExit (indgrafptr);
353 return (1);
354 }
355 #endif /* SCOTCH_DEBUG_HDGRAPH2 */
356
357 return (0);
358 }
359