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_induce.c **/
36
/** AUTHOR : Francois PELLEGRINI **/
38
/** FUNCTION : This module handles the source graph **/
39
/** subgraph-making 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 : 28 nov 2001 **/
54
/** to 17 apr 2006 **/
55
/** # Version 5.0 : from : 14 dec 2006 **/
56
/** to 10 sep 2007 **/
58
/** NOTES : # Several algorithms, such as the **/
59
/** active graph building routine of **/
60
/** bgraphInit2, assume that, for every **/
61
/** vertex, remaining edges will be kept **/
62
/** in the same order as in the original **/
63
/** graph. This must be enforced. **/
65
/************************************************************/
68
** The defines and includes.
77
#include "graph_induce.h"
79
/****************************************/
81
/* These routines handle source graphs. */
83
/****************************************/
85
/* This routine builds the graph induced
86
** by the original graph and the list of
88
** The induced vnumtab array is the list
89
** array if the original graph does not have
90
** a vnumtab, or the proper subset of the
91
** original vnumtab else.
99
const Graph * restrict const orggrafptr,
100
const VertList * restrict const indlistptr,
101
Graph * restrict const indgrafptr)
103
Gnum * restrict orgindxtax; /* Based access to vertex translation array */
104
Gnum indvertnbr; /* Number of vertices in induced graph */
105
Gnum indvertnum; /* Number of current vertex in induced graph */
106
Gnum * restrict indedgetab; /* Pointer to pre-allocated edge array */
107
Gnum indedgenbr; /* (Approximate) number of edges in induced graph */
109
memSet (indgrafptr, 0, sizeof (Graph)); /* Initialize graph fields */
110
indgrafptr->flagval = GRAPHFREETABS | GRAPHVERTGROUP | GRAPHEDGEGROUP;
111
indgrafptr->baseval = orggrafptr->baseval;
113
indvertnbr = indlistptr->vnumnbr;
115
if (orggrafptr->velotax != NULL) {
116
if (memAllocGroup ((void **) (void *)
117
&indgrafptr->verttax, (size_t) ((indvertnbr + 1) * sizeof (Gnum)),
118
&indgrafptr->vnumtax, (size_t) ( indvertnbr * sizeof (Gnum)),
119
&indgrafptr->velotax, (size_t) ( indvertnbr * sizeof (Gnum)), NULL) == NULL) {
120
errorPrint ("graphInduceList: out of memory (1)");
121
return (1); /* Nothing to free because group allocation failed */
123
indgrafptr->velotax -= indgrafptr->baseval;
126
if (memAllocGroup ((void **) (void *)
127
&indgrafptr->verttax, (size_t) ((indvertnbr + 1) * sizeof (Gnum)),
128
&indgrafptr->vnumtax, (size_t) ( indvertnbr * sizeof (Gnum)), NULL) == NULL) {
129
errorPrint ("graphInduceList: out of memory (2)");
133
indgrafptr->verttax -= indgrafptr->baseval; /* Adjust base of arrays */
134
indgrafptr->vnumtax -= indgrafptr->baseval;
135
indgrafptr->vertnbr = indvertnbr;
136
indgrafptr->vertnnd = indvertnbr + indgrafptr->baseval;
138
indedgenbr = ((indvertnbr * orggrafptr->degrmax) < orggrafptr->edgenbr) /* Choose best upper bound on number of edges */
139
? (indvertnbr * orggrafptr->degrmax) : orggrafptr->edgenbr;
140
if (orggrafptr->edlotax != NULL) /* If graph has edge weights */
141
indedgenbr *= 2; /* Account for edge weights */
143
if (memAllocGroup ((void *)
144
&indedgetab, (size_t) (indedgenbr * sizeof (Gnum)), /* Pre-allocate space for edgetab (and edlotab) */
145
&orgindxtax, (size_t) (orggrafptr->vertnbr * sizeof (Gnum)), NULL) == NULL) { /* orgindxtab is at the end of the heap */
146
errorPrint ("graphInduceList: out of memory (3)");
147
graphExit (indgrafptr);
151
/* TODO: Vertex list can be kept as it is the one of *graphOrderNd */
153
memCpy (indgrafptr->vnumtax + indgrafptr->baseval, /* Copy vertex number array from list */
154
indlistptr->vnumtab, indvertnbr * sizeof (Gnum));
156
memSet (orgindxtax, ~0, orggrafptr->vertnbr * sizeof (Gnum)); /* Preset index array */
157
orgindxtax -= orggrafptr->baseval;
159
for (indvertnum = indgrafptr->baseval, indedgenbr = 0; /* Fill index array */
160
indvertnum < indgrafptr->baseval + indvertnbr; indvertnum ++) {
163
orgvertnum = indgrafptr->vnumtax[indvertnum];
165
orgindxtax[orgvertnum] = indvertnum; /* Mark selected vertices */
166
indedgenbr += orggrafptr->vendtax[orgvertnum] - orggrafptr->verttax[orgvertnum];
169
return (graphInduce2 (orggrafptr, indgrafptr, indvertnbr, indedgenbr, indedgetab, orgindxtax));
172
/* This routine builds the graph induced
173
** by the original graph and the vector
174
** of selected vertices.
175
** The induced vnumtab array is the list of
176
** selected vertices if the original graph
177
** does not have a vnumtab, or the proper
178
** subset of the original vnumtab else.
186
const Graph * restrict const orggrafptr, /* Pointer to original graph */
187
const GraphPart * const orgparttax, /* Based array of vertex partition flags */
188
const Gnum indvertnbr, /* Number of vertices in selected part */
189
const GraphPart indpartval, /* Partition value of vertices to keep */
190
Graph * restrict const indgrafptr) /* Pointer to induced subgraph */
192
Gnum * restrict orgindxtab; /* Original to induced vertex translation array */
193
Gnum * restrict orgindxtax; /* Based access to vertex translation array */
194
Gnum indvertnum; /* Number of current vertex in induced graph */
195
Gnum * restrict indedgetab; /* Pointer to pre-allocated edge array */
196
Gnum indedgenbr; /* (Approximate) number of edges in induced graph */
199
memSet (indgrafptr, 0, sizeof (Graph)); /* Initialize graph fields */
200
indgrafptr->flagval = GRAPHFREETABS | GRAPHVERTGROUP | GRAPHEDGEGROUP;
201
indgrafptr->baseval = orggrafptr->baseval;
203
indedgenbr = ((indvertnbr * orggrafptr->degrmax) < orggrafptr->edgenbr) /* Choose best upper bound on number of edges */
204
? (indvertnbr * orggrafptr->degrmax) : orggrafptr->edgenbr;
205
if (orggrafptr->edlotax != NULL) /* If graph has edge weights */
206
indedgenbr *= 2; /* Account for edge weights */
208
if (orggrafptr->velotax != NULL) {
209
if (memAllocGroup ((void **) (void *)
210
&indgrafptr->verttax, (size_t) ((indvertnbr + 1) * sizeof (Gnum)),
211
&indgrafptr->vnumtax, (size_t) ( indvertnbr * sizeof (Gnum)),
212
&indgrafptr->velotax, (size_t) ( indvertnbr * sizeof (Gnum)), NULL) == NULL) {
213
errorPrint ("graphInducePart: out of memory (1)");
214
return (1); /* Nothing to free because group allocation failed */
216
indgrafptr->velotax -= indgrafptr->baseval;
219
if (memAllocGroup ((void **) (void *)
220
&indgrafptr->verttax, (size_t) ((indvertnbr + 1) * sizeof (Gnum)),
221
&indgrafptr->vnumtax, (size_t) ( indvertnbr * sizeof (Gnum)), NULL) == NULL) {
222
errorPrint ("graphInducePart: out of memory (2)");
226
indgrafptr->verttax -= indgrafptr->baseval; /* Adjust base of arrays */
227
indgrafptr->vnumtax -= indgrafptr->baseval;
228
indgrafptr->vertnbr = indvertnbr;
229
indgrafptr->vertnnd = indvertnbr + indgrafptr->baseval;
231
if (memAllocGroup ((void *)
232
&indedgetab, (size_t) (indedgenbr * sizeof (Gnum)), /* Pre-allocate space for edgetab (and edlotab) */
233
&orgindxtab, (size_t) (orggrafptr->vertnbr * sizeof (Gnum)), NULL) == NULL) { /* orgindxtab is at the end of the heap */
234
errorPrint ("graphInducePart: out of memory (3)");
235
graphExit (indgrafptr);
238
orgindxtax = orgindxtab - orggrafptr->baseval;
240
for (indvertnum = indgrafptr->baseval, indedgenbr = 0, orgvertnum = orggrafptr->baseval; /* Fill index array */
241
orgvertnum < orggrafptr->vertnnd; orgvertnum ++) {
242
if (orgparttax[orgvertnum] == indpartval) { /* If vertex should be kept */
243
orgindxtax[orgvertnum] = indvertnum; /* Mark selected vertex */
244
indgrafptr->vnumtax[indvertnum] = orgvertnum;
245
indedgenbr += orggrafptr->vendtax[orgvertnum] - orggrafptr->verttax[orgvertnum];
246
indvertnum ++; /* One more induced vertex created */
249
orgindxtax[orgvertnum] = ~0;
251
#ifdef SCOTCH_DEBUG_GRAPH2
252
if ((indvertnum - indgrafptr->baseval) != indvertnbr) {
253
errorPrint ("graphInducePart: inconsistent data");
254
memFree (indedgetab);
255
graphExit (indgrafptr);
258
#endif /* SCOTCH_DEBUG_GRAPH2 */
260
return (graphInduce2 (orggrafptr, indgrafptr, indvertnbr, indedgenbr, indedgetab, orgindxtax));
263
/* This routine finalizes the building
264
** of the induced subgraph.
273
const Graph * restrict const orggrafptr, /* Pointer to original graph */
274
Graph * restrict const indgrafptr, /* Pointer to induced graph */
275
const Gnum indvertnbr, /* Number of vertices in induced graph */
276
const Gnum indedgenbr, /* (Upper bound of) number of edges in induced graph */
277
Gnum * restrict const indedgetab, /* Pointer to pre-allocated edge and edge load arrays */
278
const Gnum * restrict const orgindxtax) /* Array of numbers of selected vertices */
280
Gnum indvertnum; /* Current induced vertex number */
281
Gnum indvelosum; /* Overall induced vertex load */
282
Gnum indedlosum; /* Overall induced edge load */
283
Gnum indedgenum; /* Number of current induced edge */
284
Gnum orgvertnum; /* Number of current vertex in original graph */
285
Gnum orgedgenum; /* Number of current edge in original graph */
287
if (orggrafptr->edlotax != NULL) {
288
memOffset ((void *) indedgetab,
289
&indgrafptr->edgetax, (size_t) (indedgenbr * sizeof (Gnum)),
290
&indgrafptr->edlotax, (size_t) (indedgenbr * sizeof (Gnum)), NULL);
291
indgrafptr->edgetax -= indgrafptr->baseval;
292
indgrafptr->edlotax -= indgrafptr->baseval;
295
indgrafptr->edgetax = indedgetab - indgrafptr->baseval;
297
indvelosum = (indgrafptr->velotax == NULL) ? indgrafptr->vertnbr : 0;
299
for (indvertnum = indedgenum = indgrafptr->baseval;
300
indvertnum < indgrafptr->vertnnd; indvertnum ++) {
301
orgvertnum = indgrafptr->vnumtax[indvertnum];
302
indgrafptr->verttax[indvertnum] = indedgenum;
303
if (indgrafptr->velotax != NULL) { /* If graph has vertex weights */
304
indvelosum += /* Accumulate vertex loads */
305
indgrafptr->velotax[indvertnum] = orggrafptr->velotax[orgvertnum];
308
if (indgrafptr->edlotax != NULL) { /* If graph has edge weights */
309
for (orgedgenum = orggrafptr->verttax[orgvertnum];
310
orgedgenum < orggrafptr->vendtax[orgvertnum]; orgedgenum ++) {
311
if (orgindxtax[orggrafptr->edgetax[orgedgenum]] != ~0) { /* If edge should be kept */
313
indgrafptr->edlotax[indedgenum] = orggrafptr->edlotax[orgedgenum];
314
indgrafptr->edgetax[indedgenum] = orgindxtax[orggrafptr->edgetax[orgedgenum]];
320
for (orgedgenum = orggrafptr->verttax[orgvertnum];
321
orgedgenum < orggrafptr->vendtax[orgvertnum]; orgedgenum ++) {
322
if (orgindxtax[orggrafptr->edgetax[orgedgenum]] != ~0) { /* If edge should be kept */
323
indgrafptr->edgetax[indedgenum] = orgindxtax[orggrafptr->edgetax[orgedgenum]];
329
indgrafptr->verttax[indvertnum] = indedgenum; /* Mark end of edge array */
330
indgrafptr->vendtax = indgrafptr->verttax + 1; /* Use compact representation of vertex arrays */
331
indgrafptr->vertnbr = indvertnum - indgrafptr->baseval;
332
indgrafptr->vertnnd = indvertnum;
333
indgrafptr->velosum = indvelosum;
334
indgrafptr->edgenbr = indedgenum - indgrafptr->baseval; /* Set actual number of edges */
335
indgrafptr->edlosum = (indgrafptr->edlotax != NULL) ? indedlosum : indgrafptr->edgenbr;
336
indgrafptr->degrmax = orggrafptr->degrmax; /* Induced maximum degree is likely to be the one of the original graph */
338
if (indgrafptr->edlotax != NULL) { /* Re-allocate arrays and delete orgindxtab */
339
size_t indedlooftval; /* Offset of edge load array with respect to edge array */
341
indedlooftval = indgrafptr->edlotax - indgrafptr->edgetax;
342
indgrafptr->edgetax = memRealloc (indgrafptr->edgetax + indgrafptr->baseval, (indedlooftval + indgrafptr->edgenbr) * sizeof (Gnum));
343
indgrafptr->edgetax -= indgrafptr->baseval;
344
indgrafptr->edlotax = indgrafptr->edgetax + indedlooftval; /* Use old index into old array as new index */
347
indgrafptr->edgetax = memRealloc (indgrafptr->edgetax + indgrafptr->baseval, indgrafptr->edgenbr * sizeof (Gnum));
348
indgrafptr->edgetax -= indgrafptr->baseval;
351
if (orggrafptr->vnumtax != NULL) { /* Adjust vnumtax */
352
for (indvertnum = indgrafptr->baseval; indvertnum < indgrafptr->vertnnd; indvertnum ++)
353
indgrafptr->vnumtax[indvertnum] = orggrafptr->vnumtax[indgrafptr->vnumtax[indvertnum]];
356
#ifdef SCOTCH_DEBUG_GRAPH2
357
if (graphCheck (indgrafptr) != 0) { /* Check graph consistency */
358
errorPrint ("graphInduce2: inconsistent graph data");
359
graphExit (indgrafptr);
362
#endif /* SCOTCH_DEBUG_GRAPH2 */
added
removed
src/libscotch/graph_induce.c
