1 /* Copyright 2004,2007,2008,2010,2012,2014 IPB, Universite de Bordeaux, 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 : hgraph_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 4.0 : from : 02 jan 2002 **/
42 /** to 25 feb 2004 **/
43 /** # Version 5.0 : from : 19 dec 2006 **/
44 /** to 11 jun 2008 **/
45 /** # Version 5.1 : from : 24 oct 2010 **/
46 /** to 24 oct 2010 **/
47 /** # Version 6.0 : from : 27 mar 2012 **/
48 /** to 07 nov 2014 **/
49 /** **/
50 /************************************************************/
51
52 /*
53 ** The defines and includes.
54 */
55
56 #define HGRAPH
57 #define HGRAPH_INDUCE
58
59 #include "module.h"
60 #include "common.h"
61 #include "graph.h"
62 #include "hgraph.h"
63 #include "hgraph_induce.h"
64
65 /*********************************************/
66 /* */
67 /* These routines handle halo source graphs. */
68 /* */
69 /*********************************************/
70
71 /* This routine builds the graph induced
72 ** by the original graph and the list of
73 ** selected vertices.
74 ** The induced vnumtab array is the list
75 ** array if the original graph does not have
76 ** a vnumtab, or the proper subset of the
77 ** original vnumtab else.
78 ** It returns:
79 ** - 0 : on success.
80 ** - !0 : on error.
81 */
82
83 int
hgraphInduceList(const Hgraph * restrict const orggrafptr,const VertList * restrict const orglistptr,const Gnum orghalonbr,Hgraph * restrict const indgrafptr)84 hgraphInduceList (
85 const Hgraph * restrict const orggrafptr, /* Pointer to original graph */
86 const VertList * restrict const orglistptr, /* Pointer to vertex list */
87 const Gnum orghalonbr, /* Upper bound of number of vertices in halo */
88 Hgraph * restrict const indgrafptr) /* Pointer to induced subgraph */
89 {
90 Gnum * restrict orgindxtax; /* Original to induced vertex number translation */
91 Gnum * restrict indedgetab; /* Origin of induced graph edge arrays */
92 Gnum indvertnbr; /* Number of vertices in induced graph */
93 Gnum indvertnum; /* Number of current vertex in induced graph */
94 Gnum indvelosiz;
95 Gnum indedgenbr; /* (Approximate) number of edges in induced graph */
96 Gnum indedgesiz; /* (Approximate) size of edge and edge load arrays */
97
98 memSet (indgrafptr, 0, sizeof (Hgraph)); /* Pre-initialize graph fields */
99
100 indgrafptr->s.flagval = GRAPHFREETABS | GRAPHVERTGROUP | GRAPHEDGEGROUP;
101 indgrafptr->s.baseval = orggrafptr->s.baseval;
102
103 indvertnbr = orglistptr->vnumnbr + orghalonbr; /* Compute upper bound on number of vertices */
104 indvelosiz = (orggrafptr->s.velotax != NULL) ? indvertnbr : 0;
105 if (memAllocGroup ((void **) (void *)
106 &indgrafptr->s.verttax, (size_t) ((indvertnbr + 1) * sizeof (Gnum)),
107 &indgrafptr->vnhdtax, (size_t) ( orglistptr->vnumnbr * sizeof (Gnum)), /* Put closest to beginning of array because no padding after */
108 &indgrafptr->s.velotax, (size_t) ( indvertnbr * sizeof (Gnum)),
109 &indgrafptr->s.vnumtax, (size_t) ( indvertnbr * sizeof (Gnum)), NULL) == NULL) {
110 errorPrint ("hgraphInduceList: out of memory (1)"); /* Allocate induced graph structure */
111 return (1);
112 }
113 memCpy (indgrafptr->s.vnumtax, orglistptr->vnumtab, orglistptr->vnumnbr * sizeof (Gnum)); /* Copy vertex number array from list */
114 indgrafptr->s.velotax = (orggrafptr->s.velotax != NULL) ? (indgrafptr->s.velotax - indgrafptr->s.baseval) : NULL;
115 indgrafptr->s.verttax -= indgrafptr->s.baseval;
116 indgrafptr->s.vnumtax -= indgrafptr->s.baseval;
117 indgrafptr->vnhdtax -= indgrafptr->s.baseval;
118 indgrafptr->vnohnbr = orglistptr->vnumnbr;
119 indgrafptr->vnohnnd = orglistptr->vnumnbr + indgrafptr->s.baseval;
120
121 indedgenbr = ((orggrafptr->s.degrmax > 0) && (indvertnbr < (orggrafptr->s.edgenbr / orggrafptr->s.degrmax))) /* Choose best upper bound on number of edges (avoid multiply overflow) */
122 ? (indvertnbr * orggrafptr->s.degrmax) : orggrafptr->s.edgenbr;
123 indedgesiz = (orggrafptr->s.edlotax != NULL) ? indedgenbr * 2 : indedgenbr; /* Account for edge load array size if graph has edge weights */
124
125 if (memAllocGroup ((void **) (void *) /* If cannot allocate edge arrays with approximation */
126 &indedgetab, (size_t) (indedgesiz * sizeof (Gnum)),
127 &orgindxtax, (size_t) (orggrafptr->s.vertnbr * sizeof (Gnum)), NULL) == NULL) {
128 indedgenbr = hgraphInduce3 (orggrafptr, orglistptr); /* Count real number of edges */
129
130 indedgesiz = (orggrafptr->s.edlotax != NULL) ? indedgenbr * 2 : indedgenbr; /* Account for edge load array size if graph has edge weights */
131
132 if ((indedgenbr < 0) || /* If cannot compute real number of edges */
133 (memAllocGroup ((void **) (void *) /* Or cannot allocate edge arrays with real values */
134 &indedgetab, (size_t) (indedgesiz * sizeof (Gnum)),
135 &orgindxtax, (size_t) (orggrafptr->s.vertnbr * sizeof (Gnum)), NULL) == NULL)) {
136 errorPrint ("hgraphInduceList: out of memory (2)");
137 hgraphExit (indgrafptr);
138 return (1);
139 }
140 }
141 memSet (orgindxtax, ~0, orggrafptr->s.vertnbr * sizeof (Gnum)); /* Preset index array */
142 orgindxtax -= orggrafptr->s.baseval; /* Base access to orgindxtab */
143
144 for (indvertnum = indgrafptr->s.baseval; indvertnum < indgrafptr->vnohnnd; indvertnum ++) /* For all non-halo vertices */
145 orgindxtax[indgrafptr->s.vnumtax[indvertnum]] = indvertnum; /* Mark selected vertices */
146
147 return (hgraphInduce2 (orggrafptr, orgindxtax, indgrafptr, indedgenbr, indedgetab));
148 }
149
150 /* This routine finalizes the building of the
151 ** halo graph induced by the original halo graph.
152 ** Vertices belonging to the old halo remain to
153 ** be numbered.
154 ** It returns:
155 ** - 0 : on success.
156 ** - !0 : on error.
157 */
158
159 static
160 int
hgraphInduce2(const Hgraph * restrict const orggrafptr,Gnum * restrict const orgindxtax,Hgraph * restrict const indgrafptr,const Gnum indedgenbr,Gnum * restrict const indedgetab)161 hgraphInduce2 (
162 const Hgraph * restrict const orggrafptr, /* Pointer to original graph */
163 Gnum * restrict const orgindxtax, /* Array of numbers of selected vertices */
164 Hgraph * restrict const indgrafptr, /* Pointer to induced graph */
165 const Gnum indedgenbr, /* (Approximate) number of edges in induced graph */
166 Gnum * restrict const indedgetab) /* Pointer to pre-allocated space for edge arrays */
167 {
168 void * restrict indedgetnd; /* End of compacted edge array */
169 Gnum indvertnum; /* Current vertex number in induced halo graph */
170
171 indedgetnd = memOffset (indedgetab, &indgrafptr->s.edgetax, (size_t) (indedgenbr * sizeof (Gnum)), NULL);
172 indgrafptr->s.edgetax = indedgetab - indgrafptr->s.baseval;
173 #ifdef SCOTCH_DEBUG_HGRAPH2
174 if (indedgetnd > (void *) (orgindxtax + orggrafptr->s.baseval)) {
175 errorPrint ("hgraphInduce2: invalid edge array size (1)");
176 hgraphExit (indgrafptr);
177 return (1);
178 }
179 #endif /* SCOTCH_DEBUG_HGRAPH2 */
180 if (orggrafptr->s.edlotax != NULL) {
181 size_t indedlooftval; /* Offset of edge load array with respect to edge array */
182
183 indedgetnd = memOffset (indedgetnd, &indgrafptr->s.edlotax, (size_t) (indedgenbr * sizeof (Gnum)), NULL);
184 indgrafptr->s.edlotax -= indgrafptr->s.baseval;
185 #ifdef SCOTCH_DEBUG_HGRAPH2
186 if (indedgetnd > (void *) (orgindxtax + orggrafptr->s.baseval)) {
187 errorPrint ("hgraphInduce2: invalid edge array size (2)");
188 hgraphExit (indgrafptr); /* Indedgetab is now freed as part of indgrafptr */
189 return (1);
190 }
191 #endif /* SCOTCH_DEBUG_HGRAPH2 */
192 hgraphInduce2L (orggrafptr, orgindxtax, indgrafptr);
193
194 indedlooftval = indgrafptr->s.edlotax - indgrafptr->s.edgetax;
195 memReallocGroup ((void *) indedgetab, /* Implicitely free orgindxtab */
196 &indgrafptr->s.edgetax, (size_t) (indedgenbr * sizeof (Gnum)), /* Keep first offset as estimated number of edges */
197 &indgrafptr->s.edlotax, (size_t) (indgrafptr->s.edgenbr * sizeof (Gnum)), /* Use real number of edges for second array */
198 NULL);
199 indgrafptr->s.edgetax -= indgrafptr->s.baseval;
200 indgrafptr->s.edlotax = indgrafptr->s.edgetax + indedlooftval; /* Use old index into old array as new index */
201 }
202 else {
203 hgraphInduce2U (orggrafptr, orgindxtax, indgrafptr);
204
205 indgrafptr->s.edgetax = memRealloc ((void *) indedgetab, indgrafptr->s.edgenbr * sizeof (Gnum)); /* Use real number of edges, implicitely free orgindxtab */
206 indgrafptr->s.edgetax -= indgrafptr->s.baseval;
207 }
208 indgrafptr->s.vendtax = indgrafptr->s.verttax + 1; /* Use compact representation of arrays */
209 indgrafptr->levlnum = orggrafptr->levlnum + 1; /* Induced subgraph is one level below */
210
211 if (orggrafptr->s.vnumtax != NULL) { /* Adjust vnumtax */
212 const Gnum * restrict const orgvnumtax = orggrafptr->s.vnumtax;
213 Gnum * restrict const indvnumtax = indgrafptr->s.vnumtax;
214
215 for (indvertnum = indgrafptr->s.baseval; indvertnum < indgrafptr->s.vertnnd; indvertnum ++)
216 indvnumtax[indvertnum] = orgvnumtax[indvnumtax[indvertnum]];
217 }
218
219 #ifdef SCOTCH_DEBUG_HGRAPH2
220 if (hgraphCheck (indgrafptr) != 0) { /* Check graph consistency */
221 errorPrint ("hgraphInduce2: inconsistent graph data");
222 hgraphExit (indgrafptr);
223 return (1);
224 }
225 #endif /* SCOTCH_DEBUG_HGRAPH2 */
226
227 return (0);
228 }
229
230 #define HGRAPHINDUCE2U
231 #define HGRAPHINDUCE2NAME hgraphInduce2U
232 #define HGRAPHINDUCE2EDLOINIT(e)
233 #define HGRAPHINDUCE2EDLOSUM indgrafptr->s.edgenbr
234 #define HGRAPHINDUCE2ENOHINIT
235 #define HGRAPHINDUCE2ENOHSUM indgrafptr->enohnbr
236 #include "hgraph_induce_edge.c"
237 #undef HGRAPHINDUCE2NAME
238 #undef HGRAPHINDUCE2EDLOINIT
239 #undef HGRAPHINDUCE2EDLOSUM
240 #undef HGRAPHINDUCE2ENOHINIT
241 #undef HGRAPHINDUCE2ENOHSUM
242 #undef HGRAPHINDUCE2U
243
244 #define HGRAPHINDUCE2L
245 #define HGRAPHINDUCE2NAME hgraphInduce2L
246 #define HGRAPHINDUCE2EDLOINIT(e) indedlosum += indedlotax[e] = orgedlotax[orgedgenum]
247 #define HGRAPHINDUCE2EDLOSUM indedlosum
248 #define HGRAPHINDUCE2ENOHINIT indenohsum += orgedlotax[orgedgenum]
249 #define HGRAPHINDUCE2ENOHSUM indenohsum
250 #include "hgraph_induce_edge.c"
251 #undef HGRAPHINDUCE2NAME
252 #undef HGRAPHINDUCE2EDLOINIT
253 #undef HGRAPHINDUCE2EDLOSUM
254 #undef HGRAPHINDUCE2ENOHINIT
255 #undef HGRAPHINDUCE2ENOHSUM
256 #undef HGRAPHINDUCE2L
257
258 /* This routine computes the exact number of edges
259 ** required to build the induced halo subgraph. It
260 ** is used when larger approximations lead to an
261 ** out-of-memory error message. As a side effect,
262 ** yet unnumbered halo vertices of the induced
263 ** subgraph are numbered and the induced halo graph
264 ** data are updated accordingly.
265 ** It returns:
266 ** - >=0 : number of edges in induced halo graph.
267 ** - -1 : if out of memory (this is helpless).
268 */
269
270 static
271 Gnum
hgraphInduce3(const Hgraph * restrict const orggrafptr,const VertList * restrict const orglistptr)272 hgraphInduce3 (
273 const Hgraph * restrict const orggrafptr, /* Pointer to original graph */
274 const VertList * restrict const orglistptr) /* Pointer to vertex list */
275 {
276 Gnum indedgenbr; /* Revised number of edges in induced halo graph */
277 Gnum indvertnum; /* Current vertex number in induced halo graph */
278 Gnum * restrict orgindxtax; /* Array of numbers of selected vertices */
279
280 const Gnum * restrict const orglistvnumtab = orglistptr->vnumtab;
281 const Gnum * restrict const orgverttax = orggrafptr->s.verttax;
282 const Gnum * restrict const orgvendtax = orggrafptr->s.vendtax;
283 const Gnum * restrict const orgedgetax = orggrafptr->s.edgetax;
284
285 if ((orgindxtax = memAlloc (orggrafptr->s.vertnbr * sizeof (Gnum))) == NULL)
286 return (-1);
287 memSet (orgindxtax, ~0, orggrafptr->s.vertnbr * sizeof (Gnum)); /* Preset index array */
288 orgindxtax -= orggrafptr->s.baseval; /* Base access to orgindxtab */
289
290 for (indvertnum = 0; indvertnum < orglistptr->vnumnbr; indvertnum ++) /* For all vertices in list */
291 orgindxtax[orglistvnumtab[indvertnum]] = indvertnum; /* Mark selected vertices */
292
293 for (indvertnum = 0, indedgenbr = 0; /* For all vertices in list */
294 indvertnum < orglistptr->vnumnbr; indvertnum ++) {
295 Gnum orgvertnum; /* Current vertex number in original halo graph */
296 Gnum orgedgenum; /* Current edge number in original halo graph */
297
298 orgvertnum = orglistvnumtab[indvertnum]; /* Get number of original vertex */
299 indedgenbr += orgvendtax[orgvertnum] - orgverttax[orgvertnum]; /* Add degree of original vertex */
300
301 for (orgedgenum = orgverttax[orgvertnum]; /* For all neighbors of original halo vertex */
302 orgedgenum < orgvendtax[orgvertnum]; orgedgenum ++) {
303 if (orgindxtax[orgedgetax[orgedgenum]] == ~0) /* If neighbor is halo vertex */
304 indedgenbr ++; /* Account for the arc once more */
305 }
306 }
307
308 memFree (orgindxtax + orggrafptr->s.baseval);
309
310 return (indedgenbr);
311 }
312