1 /* Copyright 2004,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 : library_graph.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module is the API for the source **/
39 /** graph handling routines of the **/
40 /** libSCOTCH library. **/
41 /** **/
42 /** DATES : # Version 3.2 : from : 18 aug 1998 **/
43 /** to 18 aug 1998 **/
44 /** # Version 3.3 : from : 02 oct 1998 **/
45 /** to 01 nov 2001 **/
46 /** # Version 4.0 : from : 11 dec 2001 **/
47 /** to 09 dec 2005 **/
48 /** # Version 5.0 : from : 10 sep 2006 **/
49 /** to 03 apr 2008 **/
50 /** # Version 5.1 : from : 17 nov 2010 **/
51 /** to 17 nov 2010 **/
52 /** # Version 6.0 : from : 04 dec 2012 **/
53 /** to 04 dec 2012 **/
54 /** **/
55 /************************************************************/
56
57 /*
58 ** The defines and includes.
59 */
60
61 #define LIBRARY
62
63 #include "module.h"
64 #include "common.h"
65 #include "graph.h"
66 #include "graph_io.h"
67 #include "scotch.h"
68
69 /************************************/
70 /* */
71 /* These routines are the C API for */
72 /* the graph handling routines. */
73 /* */
74 /************************************/
75
76 /*+ This routine reserves a memory area
77 *** of a size sufficient to store a
78 *** centralized graph structure.
79 *** It returns:
80 *** - !NULL : if the initialization succeeded.
81 *** - NULL : on error.
82 +*/
83
84 SCOTCH_Graph *
SCOTCH_graphAlloc()85 SCOTCH_graphAlloc ()
86 {
87 return ((SCOTCH_Graph *) memAlloc (sizeof (SCOTCH_Graph)));
88 }
89
90 /*+ This routine initializes the opaque
91 *** graph structure used to handle graphs
92 *** in the Scotch library.
93 *** It returns:
94 *** - 0 : if the initialization succeeded.
95 *** - !0 : on error.
96 +*/
97
98 int
SCOTCH_graphInit(SCOTCH_Graph * const grafptr)99 SCOTCH_graphInit (
100 SCOTCH_Graph * const grafptr)
101 {
102 if (sizeof (SCOTCH_Num) != sizeof (Gnum)) {
103 errorPrint ("SCOTCH_graphInit: internal error (1)");
104 return (1);
105 }
106 if (sizeof (SCOTCH_Graph) < sizeof (Graph)) {
107 errorPrint ("SCOTCH_graphInit: internal error (2)");
108 return (1);
109 }
110
111 return (graphInit ((Graph *) grafptr));
112 }
113
114 /*+ This routine frees the contents of the
115 *** given opaque graph structure.
116 *** It returns:
117 *** - VOID : in all cases.
118 +*/
119
120 void
SCOTCH_graphExit(SCOTCH_Graph * const grafptr)121 SCOTCH_graphExit (
122 SCOTCH_Graph * const grafptr)
123 {
124 graphExit ((Graph *) grafptr);
125 }
126
127 /*+ This routine frees the contents of the
128 *** given opaque graph structure.
129 *** It returns:
130 *** - VOID : in all cases.
131 +*/
132
133 void
SCOTCH_graphFree(SCOTCH_Graph * const grafptr)134 SCOTCH_graphFree (
135 SCOTCH_Graph * const grafptr)
136 {
137 graphFree ((Graph *) grafptr);
138 }
139
140 /*+ This routine loads the given opaque graph
141 *** structure with the data of the given stream.
142 *** The base value allows the user to set the
143 *** graph base to 0 or 1, or to the base value
144 *** of the stream if the base value is equal
145 *** to -1. On input, vertex loads are discarded if
146 *** flagval is 1, edge loads are discarded if flagval
147 *** is 2, and both if flagval is set to 3.
148 *** It returns:
149 *** - 0 : if the loading succeeded.
150 *** - !0 : on error.
151 +*/
152
153 int
SCOTCH_graphLoad(SCOTCH_Graph * const grafptr,FILE * const stream,const SCOTCH_Num baseval,const SCOTCH_Num flagval)154 SCOTCH_graphLoad (
155 SCOTCH_Graph * const grafptr,
156 FILE * const stream,
157 const SCOTCH_Num baseval,
158 const SCOTCH_Num flagval)
159 {
160 GraphFlag srcgrafflag; /* Graph flags */
161
162 if ((baseval < -1) || (baseval > 1)) {
163 errorPrint ("SCOTCH_graphLoad: invalid base parameter");
164 return (1);
165 }
166 if ((flagval < 0) || (flagval > 3)) {
167 errorPrint ("SCOTCH_graphLoad: invalid flag parameter");
168 return (1);
169 }
170
171 srcgrafflag = (((flagval & 1) != 0) ? GRAPHIONOLOADVERT : 0) +
172 (((flagval & 2) != 0) ? GRAPHIONOLOADEDGE : 0);
173
174 return (graphLoad ((Graph * const) grafptr, stream, (Gnum) baseval, srcgrafflag));
175 }
176
177 /*+ This routine saves the contents of the given
178 *** opaque graph structure to the given stream.
179 *** It returns:
180 *** - 0 : if the saving succeeded.
181 *** - !0 : on error.
182 +*/
183
184 int
SCOTCH_graphSave(const SCOTCH_Graph * const grafptr,FILE * const stream)185 SCOTCH_graphSave (
186 const SCOTCH_Graph * const grafptr,
187 FILE * const stream)
188 {
189 return (graphSave ((const Graph * const) grafptr, stream));
190 }
191
192 /*+ This routine fills the contents of the given
193 *** opaque graph structure with the data provided
194 *** by the user. The base value allows the user to
195 *** set the graph base to 0 or 1.
196 *** It returns:
197 *** - 0 : on success.
198 *** - !0 : on error.
199 +*/
200
201 int
SCOTCH_graphBuild(SCOTCH_Graph * const grafptr,const SCOTCH_Num baseval,const SCOTCH_Num vertnbr,const SCOTCH_Num * const verttab,const SCOTCH_Num * const vendtab,const SCOTCH_Num * const velotab,const SCOTCH_Num * const vlbltab,const SCOTCH_Num edgenbr,const SCOTCH_Num * const edgetab,const SCOTCH_Num * const edlotab)202 SCOTCH_graphBuild (
203 SCOTCH_Graph * const grafptr, /* Graph structure to fill */
204 const SCOTCH_Num baseval, /* Base value */
205 const SCOTCH_Num vertnbr, /* Number of vertices */
206 const SCOTCH_Num * const verttab, /* Vertex array [vertnbr or vertnbr+1] */
207 const SCOTCH_Num * const vendtab, /* Vertex end array [vertnbr] */
208 const SCOTCH_Num * const velotab, /* Vertex load array */
209 const SCOTCH_Num * const vlbltab, /* Vertex label array */
210 const SCOTCH_Num edgenbr, /* Number of edges (arcs) */
211 const SCOTCH_Num * const edgetab, /* Edge array [edgenbr] */
212 const SCOTCH_Num * const edlotab) /* Edge load array */
213 {
214 Graph * srcgrafptr; /* Pointer to source graph structure */
215 Gnum vertnum; /* Current vertex number */
216 Gnum degrmax; /* Maximum degree */
217
218 #ifdef SCOTCH_DEBUG_LIBRARY1
219 if (sizeof (SCOTCH_Graph) < sizeof (Graph)) {
220 errorPrint ("SCOTCH_graphBuild: internal error");
221 return (1);
222 }
223 #endif /* SCOTCH_DEBUG_LIBRARY1 */
224 if ((baseval < 0) || (baseval > 1)) {
225 errorPrint ("SCOTCH_graphBuild: invalid base parameter");
226 return (1);
227 }
228
229 srcgrafptr = (Graph *) grafptr; /* Use structure as source graph */
230 srcgrafptr->flagval = GRAPHNONE;
231 srcgrafptr->baseval = baseval;
232 srcgrafptr->vertnbr = vertnbr;
233 srcgrafptr->vertnnd = vertnbr + baseval;
234 srcgrafptr->verttax = (Gnum *) verttab - baseval;
235 srcgrafptr->vendtax = ((vendtab == NULL) || (vendtab == verttab)) ? srcgrafptr->verttax + 1 : (Gnum *) vendtab - baseval;
236 srcgrafptr->velotax = ((velotab == NULL) || (velotab == verttab)) ? NULL : (Gnum *) velotab - baseval;
237 srcgrafptr->vnumtax = NULL;
238 srcgrafptr->vlbltax = ((vlbltab == NULL) || (vlbltab == verttab)) ? NULL : (Gnum *) vlbltab - baseval;
239 srcgrafptr->edgenbr = edgenbr;
240 srcgrafptr->edgetax = (Gnum *) edgetab - baseval;
241 srcgrafptr->edlotax = ((edlotab == NULL) || (edlotab == edgetab)) ? NULL : (Gnum *) edlotab - baseval;
242
243 if (srcgrafptr->velotax == NULL) /* Compute vertex load sum */
244 srcgrafptr->velosum = vertnbr;
245 else {
246 Gnum velosum; /* Sum of vertex loads */
247
248 for (vertnum = srcgrafptr->baseval, velosum = 0; vertnum < srcgrafptr->vertnnd; vertnum ++)
249 velosum += srcgrafptr->velotax[vertnum];
250 srcgrafptr->velosum = velosum;
251 }
252
253 if (srcgrafptr->edlotax == NULL) { /* If no edge loads */
254 srcgrafptr->edlosum = srcgrafptr->edgenbr; /* Edge load sum is known */
255
256 for (vertnum = srcgrafptr->baseval, degrmax = 0; /* Compute maximum degree only */
257 vertnum < srcgrafptr->vertnnd; vertnum ++) {
258 Gnum degrval; /* Degree of current vertex */
259
260 degrval = srcgrafptr->vendtax[vertnum] - srcgrafptr->verttax[vertnum];
261 if (degrval > degrmax)
262 degrmax = degrval;
263 }
264 }
265 else { /* Graph has edge loads, compute edge load sum */
266 Gnum edlosum;
267
268 for (vertnum = srcgrafptr->baseval, edlosum = degrmax = 0;
269 vertnum < srcgrafptr->vertnnd; vertnum ++) {
270 Gnum edgenum;
271 Gnum degrval; /* Degree of current vertex */
272
273 degrval = srcgrafptr->vendtax[vertnum] - srcgrafptr->verttax[vertnum];
274 if (degrval > degrmax)
275 degrmax = degrval;
276 for (edgenum = srcgrafptr->verttax[vertnum]; edgenum < srcgrafptr->vendtax[vertnum]; edgenum ++)
277 edlosum += srcgrafptr->edlotax[edgenum];
278 }
279 srcgrafptr->edlosum = edlosum;
280 }
281 srcgrafptr->degrmax = degrmax;
282
283 return (0);
284 }
285
286 /*+ This routine accesses graph size data.
287 *** NULL pointers on input indicate unwanted
288 *** data.
289 *** It returns:
290 *** - VOID : in all cases.
291 +*/
292
293 void
SCOTCH_graphSize(const SCOTCH_Graph * const grafptr,SCOTCH_Num * const vertnbr,SCOTCH_Num * const edgenbr)294 SCOTCH_graphSize (
295 const SCOTCH_Graph * const grafptr,
296 SCOTCH_Num * const vertnbr,
297 SCOTCH_Num * const edgenbr)
298 {
299 const Graph * srcgrafptr;
300
301 srcgrafptr = (Graph *) grafptr;
302
303 if (vertnbr != NULL)
304 *vertnbr = (SCOTCH_Num) (srcgrafptr->vertnbr);
305 if (edgenbr != NULL)
306 *edgenbr = (SCOTCH_Num) srcgrafptr->edgenbr;
307 }
308
309 /*+ This routine accesses all of the graph data.
310 *** NULL pointers on input indicate unwanted
311 *** data. NULL pointers on output indicate
312 *** unexisting arrays.
313 *** It returns:
314 *** - VOID : in all cases.
315 +*/
316
317 void
SCOTCH_graphData(const SCOTCH_Graph * const grafptr,SCOTCH_Num * const baseptr,SCOTCH_Num * const vertptr,SCOTCH_Num ** const verttab,SCOTCH_Num ** const vendtab,SCOTCH_Num ** const velotab,SCOTCH_Num ** const vlbltab,SCOTCH_Num * const edgeptr,SCOTCH_Num ** const edgetab,SCOTCH_Num ** const edlotab)318 SCOTCH_graphData (
319 const SCOTCH_Graph * const grafptr, /* Graph structure to read */
320 SCOTCH_Num * const baseptr, /* Base value */
321 SCOTCH_Num * const vertptr, /* Number of vertices */
322 SCOTCH_Num ** const verttab, /* Vertex array [vertnbr+1] */
323 SCOTCH_Num ** const vendtab, /* Vertex array [vertnbr] */
324 SCOTCH_Num ** const velotab, /* Vertex load array */
325 SCOTCH_Num ** const vlbltab, /* Vertex label array */
326 SCOTCH_Num * const edgeptr, /* Number of edges (arcs) */
327 SCOTCH_Num ** const edgetab, /* Edge array [edgenbr] */
328 SCOTCH_Num ** const edlotab) /* Edge load array */
329 {
330 const Graph * srcgrafptr; /* Pointer to source graph structure */
331
332 srcgrafptr = (const Graph *) grafptr;
333
334 if (baseptr != NULL)
335 *baseptr = srcgrafptr->baseval;
336 if (vertptr != NULL)
337 *vertptr = srcgrafptr->vertnbr;
338 if (verttab != NULL)
339 *verttab = srcgrafptr->verttax + srcgrafptr->baseval;
340 if (vendtab != NULL)
341 *vendtab = srcgrafptr->vendtax + srcgrafptr->baseval;
342 if (velotab != NULL)
343 *velotab = (srcgrafptr->velotax != NULL) ? srcgrafptr->velotax + srcgrafptr->baseval : NULL;
344 if (vlbltab != NULL)
345 *vlbltab = (srcgrafptr->vlbltax != NULL) ? srcgrafptr->vlbltax + srcgrafptr->baseval : NULL;
346 if (edgeptr != NULL)
347 *edgeptr = srcgrafptr->edgenbr;
348 if (edgetab != NULL)
349 *edgetab = srcgrafptr->edgetax + srcgrafptr->baseval;
350 if (edlotab != NULL)
351 *edlotab = (srcgrafptr->edlotax != NULL) ? srcgrafptr->edlotax + srcgrafptr->baseval : NULL;
352 }
353
354 /*+ This routine computes statistics
355 *** on the given graph.
356 *** It returns:
357 *** - VOID : in all cases.
358 +*/
359
360 void
SCOTCH_graphStat(const SCOTCH_Graph * const grafptr,SCOTCH_Num * const velominptr,SCOTCH_Num * const velomaxptr,SCOTCH_Num * const velosumptr,double * veloavgptr,double * velodltptr,SCOTCH_Num * const degrminptr,SCOTCH_Num * const degrmaxptr,double * degravgptr,double * degrdltptr,SCOTCH_Num * const edlominptr,SCOTCH_Num * const edlomaxptr,SCOTCH_Num * const edlosumptr,double * edloavgptr,double * edlodltptr)361 SCOTCH_graphStat (
362 const SCOTCH_Graph * const grafptr,
363 SCOTCH_Num * const velominptr,
364 SCOTCH_Num * const velomaxptr,
365 SCOTCH_Num * const velosumptr,
366 double * veloavgptr,
367 double * velodltptr,
368 SCOTCH_Num * const degrminptr,
369 SCOTCH_Num * const degrmaxptr,
370 double * degravgptr,
371 double * degrdltptr,
372 SCOTCH_Num * const edlominptr,
373 SCOTCH_Num * const edlomaxptr,
374 SCOTCH_Num * const edlosumptr,
375 double * edloavgptr,
376 double * edlodltptr)
377 {
378 const Graph * srcgrafptr;
379 Gnum vertnum;
380 Gnum vertnbr;
381 Gnum velomin;
382 Gnum velomax;
383 double veloavg;
384 double velodlt;
385 Gnum degrval;
386 Gnum degrmin;
387 Gnum degrmax;
388 double degravg;
389 double degrdlt;
390 Gnum edgenum;
391 Gnum edlomin;
392 Gnum edlomax;
393 Gnum edlosum;
394 double edloavg;
395 double edlodlt;
396
397 srcgrafptr = (Graph *) grafptr;
398
399 vertnbr = srcgrafptr->vertnnd - srcgrafptr->baseval;
400
401 velodlt = 0.0L;
402 if (vertnbr > 0) {
403 if (srcgrafptr->velotax != NULL) { /* If graph has vertex loads */
404 velomin = GNUMMAX;
405 velomax = 0;
406 veloavg = (double) srcgrafptr->velosum / (double) vertnbr;
407
408 for (vertnum = srcgrafptr->baseval; vertnum < srcgrafptr->vertnnd; vertnum ++) {
409 if (srcgrafptr->velotax[vertnum] < velomin) /* Account for vertex loads */
410 velomin = srcgrafptr->velotax[vertnum];
411 if (srcgrafptr->velotax[vertnum] > velomax)
412 velomax = srcgrafptr->velotax[vertnum];
413 velodlt += fabs ((double) srcgrafptr->velotax[vertnum] - veloavg);
414 }
415 velodlt /= (double) vertnbr;
416 }
417 else {
418 velomin =
419 velomax = 1;
420 veloavg = 1.0L;
421 }
422 }
423 else {
424 velomin =
425 velomax = 0;
426 veloavg = 0.0L;
427 }
428
429 if (velominptr != NULL)
430 *velominptr = (SCOTCH_Num) velomin;
431 if (velomaxptr != NULL)
432 *velomaxptr = (SCOTCH_Num) velomax;
433 if (velosumptr != NULL)
434 *velosumptr = (SCOTCH_Num) srcgrafptr->velosum;
435 if (veloavgptr != NULL)
436 *veloavgptr = (double) veloavg;
437 if (velodltptr != NULL)
438 *velodltptr = (double) velodlt;
439
440 degrmax = 0;
441 degrdlt = 0.0L;
442 if (vertnbr > 0) {
443 degrmin = GNUMMAX;
444 degravg = (double) srcgrafptr->edgenbr / (double) vertnbr;
445 for (vertnum = srcgrafptr->baseval; vertnum < srcgrafptr->vertnnd; vertnum ++) {
446 degrval = srcgrafptr->vendtax[vertnum] - srcgrafptr->verttax[vertnum]; /* Get vertex degree */
447 if (degrval < degrmin)
448 degrmin = degrval;
449 if (degrval > degrmax)
450 degrmax = degrval;
451 degrdlt += fabs ((double) degrval - degravg);
452 }
453 degrdlt /= (double) vertnbr;
454 }
455 else {
456 degrmin = 0;
457 degravg = 0.0L;
458 }
459
460 if (degrminptr != NULL)
461 *degrminptr = (SCOTCH_Num) degrmin;
462 if (degrmaxptr != NULL)
463 *degrmaxptr = (SCOTCH_Num) degrmax;
464 if (degravgptr != NULL)
465 *degravgptr = (double) degravg;
466 if (degrdltptr != NULL)
467 *degrdltptr = (double) degrdlt;
468
469 edlodlt = 0.0L;
470 if (srcgrafptr->edgenbr > 0) {
471 if (srcgrafptr->edlotax != NULL) { /* If graph has edge loads */
472 edlomin = GNUMMAX;
473 edlomax = 0;
474 edlosum = 0;
475
476 for (vertnum = srcgrafptr->baseval; vertnum < srcgrafptr->vertnnd; vertnum ++) {
477 for (edgenum = srcgrafptr->verttax[vertnum]; edgenum < srcgrafptr->vendtax[vertnum]; edgenum ++) { /* For all edges */
478 if (srcgrafptr->edlotax[edgenum] < edlomin) /* Account for edge load */
479 edlomin = srcgrafptr->edlotax[edgenum];
480 if (srcgrafptr->edlotax[edgenum] > edlomax)
481 edlomax = srcgrafptr->edlotax[edgenum];
482 edlosum += srcgrafptr->edlotax[edgenum];
483 }
484 }
485 edloavg = (double) edlosum /
486 (double) (2 * srcgrafptr->edgenbr);
487
488 for (vertnum = srcgrafptr->baseval; vertnum < srcgrafptr->vertnnd; vertnum ++) {
489 for (edgenum = srcgrafptr->verttax[vertnum]; edgenum < srcgrafptr->vendtax[vertnum]; edgenum ++) /* For all edges */
490 edlodlt += fabs ((double) srcgrafptr->edlotax[edgenum] - edloavg);
491 }
492 edlodlt /= (double) srcgrafptr->edgenbr;
493 }
494 else {
495 edlomin =
496 edlomax = 1;
497 edlosum = srcgrafptr->edgenbr / 2;
498 edloavg = 1.0L;
499 }
500 }
501 else {
502 edlomin =
503 edlomax = 0;
504 edlosum = 0;
505 edloavg = 0.0L;
506 }
507
508 if (edlominptr != NULL)
509 *edlominptr = (SCOTCH_Num) edlomin;
510 if (edlomaxptr != NULL)
511 *edlomaxptr = (SCOTCH_Num) edlomax;
512 if (edlosumptr != NULL)
513 *edlosumptr = (SCOTCH_Num) edlosum;
514 if (edloavgptr != NULL)
515 *edloavgptr = (double) edloavg;
516 if (edlodltptr != NULL)
517 *edlodltptr = (double) edlodlt;
518 }
519