1 /* Copyright 2011,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 : test_scotch_graph_part_ovl.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module tests the sequential **/
39 /** graph partitioning with overlap **/
40 /** routine. **/
41 /** **/
42 /** DATES : # Version 6.0 : from : 20 sep 2014 **/
43 /** to 20 sep 2014 **/
44 /** **/
45 /************************************************************/
46
47 /*
48 ** The defines and includes.
49 */
50
51 #include <stdio.h>
52 #if (((defined __STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || (defined HAVE_STDINT_H))
53 #include <stdint.h>
54 #endif /* (((defined __STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) || (defined HAVE_STDINT_H)) */
55 #include <stdlib.h>
56 #include <string.h>
57
58 #include "scotch.h"
59
60 /*********************/
61 /* */
62 /* The main routine. */
63 /* */
64 /*********************/
65
66 int
main(int argc,char * argv[])67 main (
68 int argc,
69 char * argv[])
70 {
71 SCOTCH_Graph grafdat;
72 SCOTCH_Strat stradat;
73 SCOTCH_Num baseval;
74 SCOTCH_Num partnbr;
75 SCOTCH_Num partnum;
76 SCOTCH_Num * restrict parttax;
77 SCOTCH_Num vertnbr;
78 SCOTCH_Num vertnum;
79 SCOTCH_Num * verttab;
80 SCOTCH_Num * vendtab;
81 SCOTCH_Num * velotab;
82 SCOTCH_Num * vlbltab;
83 SCOTCH_Num * edgetax;
84 SCOTCH_Num * restrict flagtab;
85 SCOTCH_Num * restrict loadtab;
86 SCOTCH_Num loadmin;
87 SCOTCH_Num loadmax;
88 SCOTCH_Num loadsum;
89 double loadavg;
90 FILE * fileptr;
91
92 SCOTCH_errorProg (argv[0]);
93
94 if ((argc < 4) || (argc > 5)) {
95 SCOTCH_errorPrint ("main: usage is \"%s <nparts> <input source graph file> <output mapping file> [<strategy>]\"\n", argv[0]);
96 exit (1);
97 }
98
99 if ((partnbr = (SCOTCH_Num) atoi (argv[1])) < 1) {
100 SCOTCH_errorPrint ("main: invalid number of parts (\"%s\")", argv[1]);
101 return (1);
102 }
103
104 if (SCOTCH_stratInit (&stradat) != 0) {
105 SCOTCH_errorPrint ("main: cannot initialize strategy");
106 return (1);
107 }
108 if (argc == 5) {
109 if (SCOTCH_stratGraphPartOvl (&stradat, argv[4]) != 0) {
110 SCOTCH_errorPrint ("main: invalid user-provided strategy");
111 return (1);
112 }
113 }
114
115 if (SCOTCH_graphInit (&grafdat) != 0) {
116 SCOTCH_errorPrint ("main: cannot initialize graph");
117 return (1);
118 }
119
120 if ((fileptr = fopen (argv[2], "r")) == NULL) {
121 SCOTCH_errorPrint ("main: cannot open file (1)");
122 return (1);
123 }
124
125 if (SCOTCH_graphLoad (&grafdat, fileptr, -1, 0) != 0) {
126 SCOTCH_errorPrint ("main: cannot load graph");
127 return (1);
128 }
129
130 fclose (fileptr);
131
132 SCOTCH_graphData (&grafdat, &baseval, &vertnbr, &verttab, &vendtab, &velotab, &vlbltab, NULL, &edgetax, NULL);
133
134 if (((parttax = malloc (vertnbr * sizeof (SCOTCH_Num))) == NULL) ||
135 ((flagtab = malloc (partnbr * sizeof (SCOTCH_Num))) == NULL) ||
136 ((loadtab = malloc (partnbr * sizeof (SCOTCH_Num))) == NULL)) {
137 SCOTCH_errorPrint ("main: out of memory");
138 return (1);
139 }
140
141 if (SCOTCH_graphPartOvl (&grafdat, partnbr, &stradat, parttax) != 0) { /* Parttax is not based yet */
142 SCOTCH_errorPrint ("main: cannot compute mapping");
143 return (1);
144 }
145
146 edgetax -= baseval;
147 parttax -= baseval;
148
149 memset (loadtab, 0, partnbr * sizeof (SCOTCH_Num)); /* Part loads set to 0 */
150 memset (flagtab, ~0, partnbr * sizeof (SCOTCH_Num)); /* Flags set to invalid vertex number */
151
152 for (vertnum = 0; vertnum < vertnbr; vertnum ++) {
153 SCOTCH_Num veloval;
154 SCOTCH_Num partval;
155
156 veloval = (velotab == NULL) ? 1 : velotab[vertnum];
157 partval = parttax[vertnum + baseval]; /* vertnum is not based */
158 if (partval >= 0) /* If vertex belongs to one part only */
159 loadtab[partval] += veloval; /* Add vertex load to this part */
160 else { /* Vertex belongs to several parts */
161 SCOTCH_Num edgenum;
162
163 for (edgenum = verttab[vertnum]; edgenum < vendtab[vertnum]; edgenum ++) {
164 SCOTCH_Num vertend;
165 SCOTCH_Num partend;
166
167 vertend = edgetax[edgenum];
168 partend = parttax[vertend]; /* vertend is based */
169 if (partend < 0) /* If neighbor has no identifiable part */
170 continue;
171 if (flagtab[partend] == vertnum) /* If neighbor part already accounted for, skip it */
172 continue;
173
174 loadtab[partend] += veloval; /* Vertex load contributes to this part */
175 flagtab[partend] = vertnum; /* Record a contribution has been made */
176 }
177 }
178 }
179
180 loadsum =
181 loadmax = 0;
182 loadmin = SCOTCH_NUMMAX;
183 for (partnum = 0; partnum < partnbr; partnum ++) {
184 loadsum += loadtab[partnum];
185 if (loadtab[partnum] > loadmax)
186 loadmax = loadtab[partnum];
187 if (loadtab[partnum] < loadmin)
188 loadmin = loadtab[partnum];
189
190 printf ("M\tCompload[%02ld]\t%ld\n",
191 (long) partnum,
192 (long) loadtab[partnum]);
193 }
194
195 loadavg = (double) loadsum / (double) partnbr;
196 printf ("M\tCompLoadAvg\t%g\n",
197 (double) loadavg);
198 printf ("M\tCompLoadMax/Avg\t%g\n",
199 (double) loadmax / loadavg);
200
201 if ((fileptr = fopen (argv[3], "w")) == NULL) {
202 SCOTCH_errorPrint ("main: cannot open file (2)");
203 return (1);
204 }
205
206 if (fprintf (fileptr, "%ld\n", (long) vertnbr) == EOF) {
207 SCOTCH_errorPrint ("main: bad output (1)");
208 return (1);
209 }
210
211 for (vertnum = 0; vertnum < vertnbr; vertnum ++) {
212 if (fprintf (fileptr, "%ld\t%ld\n",
213 (long) ((vlbltab == NULL) ? vertnum : vlbltab[vertnum]),
214 (long) parttax[vertnum + baseval]) == EOF) {
215 SCOTCH_errorPrint ("main: bad output (2)");
216 return (1);
217 }
218 }
219
220 fclose (fileptr);
221
222 free (loadtab);
223 free (flagtab);
224 free (parttax + baseval);
225
226 SCOTCH_stratExit (&stradat);
227 SCOTCH_graphExit (&grafdat);
228
229 exit (0);
230 }
231