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