1 /* Copyright 2004,2007,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 : graph_io.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module handles the source graph **/
39 /** input/output functions. **/
40 /** **/
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 15 mar 1999 **/
53 /** # Version 4.0 : from : 25 nov 2001 **/
54 /** to 21 jan 2004 **/
55 /** # Version 5.0 : from : 13 dec 2006 **/
56 /** to 10 sep 2007 **/
57 /** # Version 5.1 : from : 11 aug 2010 **/
58 /** to 11 aug 2010 **/
59 /** **/
60 /************************************************************/
61
62 /*
63 ** The defines and includes.
64 */
65
66 #define GRAPH_IO
67
68 #include "module.h"
69 #include "common.h"
70 #include "graph.h"
71 #include "graph_io.h"
72
73 /*******************************************/
74 /* */
75 /* These routines handle source graph I/O. */
76 /* */
77 /*******************************************/
78
79 /* This routine loads a source graph from
80 ** the given stream.
81 ** It returns:
82 ** - 0 : on success.
83 ** - !0 : on error.
84 */
85
86 int
graphLoad(Graph * restrict const grafptr,FILE * const stream,const Gnum baseval,const GraphFlag flagval)87 graphLoad (
88 Graph * restrict const grafptr, /* Graph structure to fill */
89 FILE * const stream, /* Stream from which to read graph data */
90 const Gnum baseval, /* Base value (-1 means keep file base) */
91 const GraphFlag flagval) /* Graph loading flags */
92 {
93 Gnum edgenum; /* Number of edges really allocated */
94 Gnum edgennd;
95 Gnum vlblnbr; /* = vertnbr if vertex labels */
96 Gnum vlblmax; /* Maximum vertex label number */
97 Gnum velonbr; /* = vertnbr if vertex loads wanted */
98 Gnum velosum; /* Sum of vertex loads */
99 Gnum edlonbr; /* = edgenbr if edge loads wanted */
100 Gnum edlosum; /* Sum of edge loads */
101 Gnum edgeval; /* Value where to read edge end */
102 Gnum baseadj;
103 Gnum versval;
104 Gnum degrmax;
105 Gnum propval;
106 char proptab[4];
107 Gnum vertnum;
108
109 memSet (grafptr, 0, sizeof (Graph));
110
111 if (intLoad (stream, &versval) != 1) { /* Read version number */
112 errorPrint ("graphLoad: bad input (1)");
113 return (1);
114 }
115 if (versval != 0) { /* If version not zero */
116 errorPrint ("graphLoad: old-style graph format no longer supported");
117 return (1);
118 }
119
120 if ((intLoad (stream, &grafptr->vertnbr) != 1) || /* Read rest of header */
121 (intLoad (stream, &grafptr->edgenbr) != 1) ||
122 (intLoad (stream, &baseadj) != 1) ||
123 (intLoad (stream, &propval) != 1) ||
124 (propval < 0) ||
125 (propval > 111)) {
126 errorPrint ("graphLoad: bad input (2)");
127 return (1);
128 }
129 sprintf (proptab, "%3.3d", (int) propval); /* Compute file properties */
130 proptab[0] -= '0'; /* Vertex labels flag */
131 proptab[1] -= '0'; /* Edge weights flag */
132 proptab[2] -= '0'; /* Vertex loads flag */
133
134 grafptr->flagval = GRAPHFREETABS | GRAPHVERTGROUP | GRAPHEDGEGROUP;
135 if (baseval == -1) { /* If keep file graph base */
136 grafptr->baseval = baseadj; /* Set graph base as file base */
137 baseadj = 0; /* No base adjustment needed */
138 }
139 else { /* If set graph base */
140 grafptr->baseval = baseval; /* Set wanted graph base */
141 baseadj = baseval - baseadj; /* Update base adjust */
142 }
143 if (proptab[0] != 0) /* If vertex labels, no base adjust */
144 baseadj = 0;
145
146 velonbr = ((proptab[2] != 0) && ((flagval & GRAPHIONOLOADVERT) == 0)) ? grafptr->vertnbr : 0;
147 vlblnbr = (proptab[0] != 0) ? grafptr->vertnbr : 0;
148 edlonbr = ((proptab[1] != 0) && ((flagval & GRAPHIONOLOADEDGE) == 0)) ? grafptr->edgenbr : 0;
149
150 if ((memAllocGroup ((void **) (void *)
151 &grafptr->verttax, (size_t) ((grafptr->vertnbr + 1) * sizeof (Gnum)),
152 &grafptr->velotax, (size_t) (velonbr * sizeof (Gnum)),
153 &grafptr->vlbltax, (size_t) (vlblnbr * sizeof (Gnum)), NULL) == NULL) ||
154 (memAllocGroup ((void **) (void *)
155 &grafptr->edgetax, (size_t) (grafptr->edgenbr * sizeof (Gnum)),
156 &grafptr->edlotax, (size_t) (edlonbr * sizeof (Gnum)), NULL) == NULL)) {
157 if (grafptr->verttax != NULL)
158 memFree (grafptr->verttax);
159 errorPrint ("graphLoad: out of memory");
160 graphFree (grafptr);
161 return (1);
162 }
163 grafptr->vertnnd = grafptr->vertnbr + grafptr->baseval;
164 grafptr->verttax -= grafptr->baseval;
165 grafptr->vendtax = grafptr->verttax + 1; /* Use compact vertex array */
166 grafptr->velotax = (velonbr != 0) ? (grafptr->velotax - grafptr->baseval) : NULL;
167 grafptr->vlbltax = (vlblnbr != 0) ? (grafptr->vlbltax - grafptr->baseval) : NULL;
168 grafptr->edgetax -= grafptr->baseval;
169 grafptr->edlotax = (edlonbr != 0) ? (grafptr->edlotax - grafptr->baseval) : NULL;
170
171 vlblmax = grafptr->vertnnd - 1; /* No vertex labels known */
172 velosum = (grafptr->velotax == NULL) ? grafptr->vertnbr : 0;
173 edlosum = (grafptr->edlotax == NULL) ? grafptr->edgenbr : 0;
174 edgennd = grafptr->edgenbr + grafptr->baseval;
175 degrmax = 0; /* No maximum degree yet */
176
177 for (vertnum = edgenum = grafptr->baseval; vertnum < grafptr->vertnnd; vertnum ++) {
178 Gnum degrval;
179
180 if (grafptr->vlbltax != NULL) { /* If must read label */
181 Gnum vlblval; /* Value where to read vertex label */
182
183 if (intLoad (stream, &vlblval) != 1) { /* Read label data */
184 errorPrint ("graphLoad: bad input (3)");
185 graphFree (grafptr);
186 return (1);
187 }
188 grafptr->vlbltax[vertnum] = vlblval;
189 if (grafptr->vlbltax[vertnum] > vlblmax) /* Get maximum vertex label */
190 vlblmax = grafptr->vlbltax[vertnum];
191 }
192 if (proptab[2] != 0) { /* If must read vertex load */
193 Gnum veloval; /* Value where to read vertex load */
194
195 if (intLoad (stream, &veloval) != 1) { /* Read vertex load data */
196 errorPrint ("graphLoad: bad input (4)");
197 graphFree (grafptr);
198 return (1);
199 }
200 if (grafptr->velotax != NULL)
201 velosum +=
202 grafptr->velotax[vertnum] = veloval;
203 }
204 if (intLoad (stream, °rval) != 1) { /* Read vertex degree */
205 errorPrint ("graphLoad: bad input (5)");
206 graphFree (grafptr);
207 return (1);
208 }
209 if (degrmax < degrval) /* Set maximum degree */
210 degrmax = degrval;
211
212 grafptr->verttax[vertnum] = edgenum; /* Set index in edge array */
213 degrval += edgenum;
214 if (degrval > edgennd) { /* Check if edge array overflows */
215 errorPrint ("graphLoad: invalid arc count (1)");
216 graphFree (grafptr);
217 return (1);
218 }
219
220 for ( ; edgenum < degrval; edgenum ++) {
221 if (proptab[1] != 0) { /* If must read edge load */
222 Gnum edloval; /* Value where to read edge load */
223
224 if (intLoad (stream, &edloval) != 1) { /* Read edge load data */
225 errorPrint ("graphLoad: bad input (6)");
226 graphFree (grafptr);
227 return (1);
228 }
229 if (grafptr->edlotax != NULL)
230 edlosum +=
231 grafptr->edlotax[edgenum] = (Gnum) edloval;
232 }
233 if (intLoad (stream, &edgeval) != 1) { /* Read edge data */
234 errorPrint ("graphLoad: bad input (7)");
235 graphFree (grafptr);
236 return (1);
237 }
238 grafptr->edgetax[edgenum] = edgeval + baseadj;
239 }
240 }
241 grafptr->verttax[vertnum] = edgenum; /* Set end of edge array */
242 if (edgenum != edgennd) { /* Check if number of edges is valid */
243 errorPrint ("graphLoad: invalid arc count (2)");
244 graphFree (grafptr);
245 return (1);
246 }
247 grafptr->velosum = velosum;
248 grafptr->edlosum = edlosum;
249 grafptr->degrmax = degrmax;
250
251 if (grafptr->vlbltax != NULL) { /* If vertex label renaming necessary */
252 if (graphLoad2 (grafptr->baseval, grafptr->vertnnd, grafptr->verttax, /* Rename edge ends */
253 grafptr->vendtax, grafptr->edgetax, vlblmax, grafptr->vlbltax) != 0) {
254 errorPrint ("graphLoad: cannot relabel vertices");
255 graphFree (grafptr);
256 return (1);
257 }
258 }
259
260 #ifdef SCOTCH_DEBUG_GRAPH2
261 if (graphCheck (grafptr) != 0) { /* Check graph consistency */
262 errorPrint ("graphLoad: inconsistent graph data");
263 graphFree (grafptr);
264 return (1);
265 }
266 #endif /* SCOTCH_DEBUG_GRAPH2 */
267
268 return (0);
269 }
270
271 int
graphLoad2(const Gnum baseval,const Gnum vertnnd,const Gnum * const verttax,const Gnum * const vendtax,Gnum * restrict const edgetax,const Gnum vlblmax,const Gnum * const vlbltax)272 graphLoad2 (
273 const Gnum baseval,
274 const Gnum vertnnd,
275 const Gnum * const verttax,
276 const Gnum * const vendtax,
277 Gnum * restrict const edgetax,
278 const Gnum vlblmax,
279 const Gnum * const vlbltax)
280 {
281 Gnum vertnum; /* Number of current vertex */
282 Gnum * restrict indxtab; /* Vertex label/number index table */
283
284 if ((indxtab = (Gnum *) memAlloc ((vlblmax + 1) * sizeof (Gnum))) == NULL) {
285 errorPrint ("graphLoad2: out of memory");
286 return (1);
287 }
288
289 memSet (indxtab, ~0, (vlblmax + 1) * sizeof (Gnum)); /* Assume labels not used */
290 for (vertnum = baseval; vertnum < vertnnd; vertnum ++) {
291 if (indxtab[vlbltax[vertnum]] != ~0) { /* If vertex label already used */
292 errorPrint ("graphLoad2: duplicate vertex label");
293 memFree (indxtab);
294 return (1);
295 }
296 indxtab[vlbltax[vertnum]] = vertnum; /* Set vertex number index */
297 }
298 for (vertnum = baseval; vertnum < vertnnd; vertnum ++) {
299 Gnum edgenum; /* Number of current edge */
300
301 for (edgenum = verttax[vertnum]; edgenum < vendtax[vertnum]; edgenum ++) {
302 if (edgetax[edgenum] > vlblmax) { /* If invalid edge end number */
303 errorPrint ("graphLoad2: invalid arc end number (1)");
304 memFree (indxtab);
305 return (1);
306 }
307 if (indxtab[edgetax[edgenum]] == ~0) { /* If unused edge end number */
308 errorPrint ("graphLoad2: invalid arc end number (2)");
309 memFree (indxtab);
310 return (1);
311 }
312 edgetax[edgenum] = indxtab[edgetax[edgenum]]; /* Replace label by number */
313 }
314 }
315
316 memFree (indxtab); /* Free index array */
317
318 return (0);
319 }
320
321 /* This routine saves a source graph to
322 ** the given stream, in the new-style
323 ** graph format.
324 ** It returns:
325 ** - 0 : on success.
326 ** - !0 : on error.
327 */
328
329 int
graphSave(const Graph * const grafptr,FILE * const stream)330 graphSave (
331 const Graph * const grafptr,
332 FILE * const stream)
333 {
334 Gnum vertnum;
335 char propstr[4]; /* Property string */
336 int o;
337
338 propstr[0] = (grafptr->vlbltax != NULL) ? '1' : '0'; /* Set property string */
339 propstr[1] = (grafptr->edlotax != NULL) ? '1' : '0';
340 propstr[2] = (grafptr->velotax != NULL) ? '1' : '0';
341 propstr[3] = '\0';
342
343 if (fprintf (stream, "0\n" GNUMSTRING "\t" GNUMSTRING "\n" GNUMSTRING "\t%3s\n", /* Write file header */
344 (Gnum) grafptr->vertnbr,
345 (Gnum) grafptr->edgenbr,
346 (Gnum) grafptr->baseval,
347 propstr) == EOF) {
348 errorPrint ("graphSave: bad output (1)");
349 return (1);
350 }
351
352 for (vertnum = grafptr->baseval, o = 0;
353 (vertnum < grafptr->vertnnd) && (o == 0); vertnum ++) {
354 Gnum edgenum;
355
356 if (grafptr->vlbltax != NULL) /* Write vertex label if necessary */
357 o = (fprintf (stream, GNUMSTRING "\t", (Gnum) grafptr->vlbltax[vertnum]) == EOF);
358 if (grafptr->velotax != NULL) /* Write vertex load if necessary */
359 o |= (fprintf (stream, GNUMSTRING "\t", (Gnum) grafptr->velotax[vertnum]) == EOF);
360
361 o |= (fprintf (stream, GNUMSTRING, (Gnum) (grafptr->vendtax[vertnum] - grafptr->verttax[vertnum])) == EOF); /* Write vertex degree */
362
363 for (edgenum = grafptr->verttax[vertnum];
364 (edgenum < grafptr->vendtax[vertnum]) && (o == 0); edgenum ++) {
365 Gnum vertend;
366
367 o |= (putc ('\t', stream) == EOF);
368 if (grafptr->edlotax != NULL) /* Write edge load if necessary */
369 o |= (fprintf (stream, GNUMSTRING "\t", (Gnum) grafptr->edlotax[edgenum]) == EOF);
370 vertend = grafptr->edgetax[edgenum];
371 o |= (fprintf (stream, GNUMSTRING, (Gnum) ((grafptr->vlbltax != NULL) ? grafptr->vlbltax[vertend] : vertend)) == EOF); /* Write edge end */
372 }
373 o |= (putc ('\n', stream) == EOF);
374 }
375
376 if (o != 0)
377 errorPrint ("graphSave: bad output (2)");
378
379 return (o);
380 }
381