1 /* Copyright 2004,2007,2008,2010,2012 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 : library_mesh_order.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module is the API for the mesh **/
39 /** ordering routines of the libSCOTCH **/
40 /** library. **/
41 /** **/
42 /** DATES : # Version 3.2 : from : 19 aug 1998 **/
43 /** to 22 aug 1998 **/
44 /** # Version 3.3 : from : 01 oct 1998 **/
45 /** to 27 mar 1999 **/
46 /** # Version 4.0 : from : 29 jan 2002 **/
47 /** to 20 dec 2005 **/
48 /** # Version 5.0 : from : 04 aug 2007 **/
49 /** to 31 may 2008 **/
50 /** # Version 5.1 : from : 29 mar 2010 **/
51 /** to 14 aug 2010 **/
52 /** # Version 6.0 : from : 14 nov 2012 **/
53 /** to 14 nov 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 "parser.h"
66 #include "graph.h"
67 #include "mesh.h"
68 #include "order.h"
69 #include "hmesh.h"
70 #include "hmesh_order_st.h"
71 #include "library_order.h"
72 #include "scotch.h"
73
74 /************************************/
75 /* */
76 /* These routines are the C API for */
77 /* the mesh ordering routines. */
78 /* */
79 /************************************/
80
81 /*+ This routine initializes an API ordering
82 *** with respect to the given source graph
83 *** and the locations of output parameters.
84 *** It returns:
85 *** - 0 : on success.
86 *** - !0 : on error.
87 +*/
88
89 int
SCOTCH_meshOrderInit(const SCOTCH_Mesh * const meshptr,SCOTCH_Ordering * const ordeptr,SCOTCH_Num * const permtab,SCOTCH_Num * const peritab,SCOTCH_Num * const cblkptr,SCOTCH_Num * const rangtab,SCOTCH_Num * const treetab)90 SCOTCH_meshOrderInit (
91 const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
92 SCOTCH_Ordering * const ordeptr, /*+ Ordering structure to initialize +*/
93 SCOTCH_Num * const permtab, /*+ Direct permutation array +*/
94 SCOTCH_Num * const peritab, /*+ Inverse permutation array +*/
95 SCOTCH_Num * const cblkptr, /*+ Pointer to number of column blocks +*/
96 SCOTCH_Num * const rangtab, /*+ Column block range array +*/
97 SCOTCH_Num * const treetab) /*+ Separator tree array +*/
98 {
99 Mesh * srcmeshptr;
100 LibOrder * libordeptr;
101
102 #ifdef SCOTCH_DEBUG_LIBRARY1
103 if (sizeof (SCOTCH_Ordering) < sizeof (LibOrder)) {
104 errorPrint ("SCOTCH_meshOrderInit: internal error");
105 return (1);
106 }
107 #endif /* SCOTCH_DEBUG_LIBRARY1 */
108
109 srcmeshptr = (Mesh *) meshptr; /* Use structure as source mesh */
110 libordeptr = (LibOrder *) ordeptr;
111 libordeptr->permtab = ((permtab == NULL) || ((void *) permtab == (void *) meshptr)) ? NULL : (Gnum *) permtab;
112 libordeptr->peritab = ((peritab == NULL) || ((void *) peritab == (void *) meshptr)) ? NULL : (Gnum *) peritab;
113 libordeptr->cblkptr = ((cblkptr == NULL) || ((void *) cblkptr == (void *) meshptr)) ? NULL : (Gnum *) cblkptr;
114 libordeptr->rangtab = ((rangtab == NULL) || ((void *) rangtab == (void *) meshptr)) ? NULL : (Gnum *) rangtab;
115 libordeptr->treetab = ((treetab == NULL) || ((void *) treetab == (void *) meshptr)) ? NULL : (Gnum *) treetab;
116
117 return (orderInit (&libordeptr->o, srcmeshptr->baseval, srcmeshptr->vnodnbr, libordeptr->peritab));
118 }
119
120 /*+ This routine frees an API ordering.
121 *** It returns:
122 *** - VOID : in all cases.
123 +*/
124
125 void
SCOTCH_meshOrderExit(const SCOTCH_Mesh * const meshptr,SCOTCH_Ordering * const ordeptr)126 SCOTCH_meshOrderExit (
127 const SCOTCH_Mesh * const meshptr,
128 SCOTCH_Ordering * const ordeptr)
129 {
130 orderExit (&((LibOrder *) ordeptr)->o);
131 }
132
133 /*+ This routine saves the contents of
134 *** the given ordering to the given stream.
135 *** It returns:
136 *** - 0 : on success.
137 *** - !0 : on error.
138 +*/
139
140 int
SCOTCH_meshOrderSave(const SCOTCH_Mesh * const meshptr,const SCOTCH_Ordering * const ordeptr,FILE * const stream)141 SCOTCH_meshOrderSave (
142 const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
143 const SCOTCH_Ordering * const ordeptr, /*+ Ordering to save +*/
144 FILE * const stream) /*+ Output stream +*/
145 {
146 return (orderSave (&((LibOrder *) ordeptr)->o, ((Mesh *) meshptr)->vlbltax, stream));
147 }
148
149 /*+ This routine saves the mapping data
150 *** associated with the given ordering
151 *** to the given stream.
152 *** It returns:
153 *** - 0 : on success.
154 *** - !0 : on error.
155 +*/
156
157 int
SCOTCH_meshOrderSaveMap(const SCOTCH_Mesh * const meshptr,const SCOTCH_Ordering * const ordeptr,FILE * const stream)158 SCOTCH_meshOrderSaveMap (
159 const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
160 const SCOTCH_Ordering * const ordeptr, /*+ Ordering to save +*/
161 FILE * const stream) /*+ Output stream +*/
162 {
163 return (orderSaveMap (&((LibOrder *) ordeptr)->o, ((Mesh *) meshptr)->vlbltax, stream));
164 }
165
166 /*+ This routine saves to the given stream
167 *** the separator tree data associated with
168 *** the given ordering.
169 *** It returns:
170 *** - 0 : on success.
171 *** - !0 : on error.
172 +*/
173
174 int
SCOTCH_meshOrderSaveTree(const SCOTCH_Mesh * const meshptr,const SCOTCH_Ordering * const ordeptr,FILE * const stream)175 SCOTCH_meshOrderSaveTree (
176 const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
177 const SCOTCH_Ordering * const ordeptr, /*+ Ordering to save +*/
178 FILE * const stream) /*+ Output stream +*/
179 {
180 return (orderSaveTree (&((LibOrder *) ordeptr)->o, ((Mesh *) meshptr)->vlbltax, stream));
181 }
182
183 /*+ This routine computes an ordering
184 *** of the API ordering structure with
185 *** respect to the given strategy.
186 *** It returns:
187 *** - 0 : on success.
188 *** - !0 : on error.
189 +*/
190
191 int
SCOTCH_meshOrderCompute(SCOTCH_Mesh * const meshptr,SCOTCH_Ordering * const ordeptr,SCOTCH_Strat * const stratptr)192 SCOTCH_meshOrderCompute (
193 SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
194 SCOTCH_Ordering * const ordeptr, /*+ Ordering to compute +*/
195 SCOTCH_Strat * const stratptr) /*+ Ordering strategy +*/
196 {
197 return (SCOTCH_meshOrderComputeList (meshptr, ordeptr, 0, NULL, stratptr));
198 }
199
200 /*+ This routine computes a partial ordering
201 *** of the listed nodes of the API ordering
202 *** structure mesh with respect to the given
203 *** strategy.
204 *** It returns:
205 *** - 0 : on success.
206 *** - !0 : on error.
207 +*/
208
209 int
SCOTCH_meshOrderComputeList(SCOTCH_Mesh * const meshptr,SCOTCH_Ordering * const ordeptr,const SCOTCH_Num listnbr,const SCOTCH_Num * const listtab,SCOTCH_Strat * const stratptr)210 SCOTCH_meshOrderComputeList (
211 SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
212 SCOTCH_Ordering * const ordeptr, /*+ Ordering to compute +*/
213 const SCOTCH_Num listnbr, /*+ Number of vertices in list +*/
214 const SCOTCH_Num * const listtab, /*+ List of vertex indices to order +*/
215 SCOTCH_Strat * const stratptr) /*+ Ordering strategy +*/
216 {
217 LibOrder * libordeptr; /* Pointer to ordering */
218 Mesh * srcmeshptr; /* Pointer to source mesh */
219 Hmesh srcmeshdat; /* Halo source mesh structure */
220 VertList srclistdat; /* Subgraph vertex list */
221 VertList * srclistptr; /* Pointer to subgraph vertex list */
222 const Strat * ordstratptr; /* Pointer to ordering strategy */
223
224 srcmeshptr = (Mesh *) meshptr;
225
226 #ifdef SCOTCH_DEBUG_MESH2
227 if (meshCheck (srcmeshptr) != 0) {
228 errorPrint ("SCOTCH_meshOrderComputeList: invalid input mesh");
229 return (1);
230 }
231 #endif /* SCOTCH_DEBUG_MESH2 */
232
233 if (*((Strat **) stratptr) == NULL) /* Set default ordering strategy if necessary */
234 SCOTCH_stratMeshOrderBuild (stratptr, SCOTCH_STRATQUALITY, 0.1);
235
236 ordstratptr = *((Strat **) stratptr);
237 if (ordstratptr->tabl != &hmeshorderststratab) {
238 errorPrint ("SCOTCH_meshOrderComputeList: not a mesh ordering strategy");
239 return (1);
240 }
241
242 memCpy (&srcmeshdat.m, srcmeshptr, sizeof (Mesh)); /* Copy non-halo mesh data */
243 srcmeshdat.m.flagval &= ~MESHFREETABS; /* Do not allow to free arrays */
244 srcmeshdat.vehdtax = srcmeshdat.m.vendtax; /* End of non-halo vertices */
245 srcmeshdat.veihnbr = 0; /* No halo isolated elements */
246 srcmeshdat.vnohnbr = srcmeshdat.m.vnodnbr; /* All nodes are non-halo */
247 srcmeshdat.vnohnnd = srcmeshdat.m.vnodnnd; /* No halo present */
248 srcmeshdat.vnhlsum = srcmeshdat.m.vnlosum; /* Sum of node vertex weights */
249 srcmeshdat.enohnbr = srcmeshdat.m.edgenbr; /* All edges are non-halo */
250 srcmeshdat.levlnum = 0; /* Start from level zero */
251
252 libordeptr = (LibOrder *) ordeptr; /* Get ordering */
253 srclistdat.vnumnbr = (Gnum) listnbr; /* Build vertex list */
254 srclistdat.vnumtab = (Gnum *) listtab;
255 srclistptr = ((srclistdat.vnumnbr == 0) ||
256 (srclistdat.vnumnbr == srcmeshdat.m.vnodnbr))
257 ? NULL : &srclistdat; /* Is the list really necessary */
258 if (srclistptr != NULL) {
259 errorPrint ("SCOTCH_meshOrderComputeList: node lists not yet implemented");
260 return (1);
261 }
262
263 intRandInit (); /* Check that random number generator is initialized */
264
265 hmeshOrderSt (&srcmeshdat, &libordeptr->o, 0, &libordeptr->o.cblktre, ordstratptr);
266
267 #ifdef SCOTCH_DEBUG_LIBRARY2
268 orderCheck (&libordeptr->o);
269 #endif /* SCOTCH_DEBUG_LIBRARY2 */
270
271 if (libordeptr->permtab != NULL) /* Build direct permutation if wanted */
272 orderPeri (libordeptr->o.peritab, libordeptr->o.baseval, libordeptr->o.vnodnbr, libordeptr->permtab, libordeptr->o.baseval);
273 if (libordeptr->rangtab != NULL) /* Build range array if column block data wanted */
274 orderRang (&libordeptr->o, libordeptr->rangtab);
275 if (libordeptr->treetab != NULL) /* Build separator tree array if wanted */
276 orderTree (&libordeptr->o, libordeptr->treetab);
277 if (libordeptr->cblkptr != NULL) /* Set number of column blocks if wanted */
278 *(libordeptr->cblkptr) = libordeptr->o.cblknbr;
279
280 meshExit (&srcmeshdat.m); /* Free in case mesh had been reordered */
281
282 return (0);
283 }
284
285 /*+ This routine computes an ordering
286 *** of the API ordering structure with
287 *** respect to the given strategy.
288 *** It returns:
289 *** - 0 : on success.
290 *** - !0 : on error.
291 +*/
292
293 int
SCOTCH_meshOrder(SCOTCH_Mesh * const meshptr,SCOTCH_Strat * const stratptr,SCOTCH_Num * const permtab,SCOTCH_Num * const peritab,SCOTCH_Num * const cblkptr,SCOTCH_Num * const rangtab,SCOTCH_Num * const treetab)294 SCOTCH_meshOrder (
295 SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
296 SCOTCH_Strat * const stratptr, /*+ Ordering strategy +*/
297 SCOTCH_Num * const permtab, /*+ Ordering permutation +*/
298 SCOTCH_Num * const peritab, /*+ Inverse permutation array +*/
299 SCOTCH_Num * const cblkptr, /*+ Pointer to number of column blocks +*/
300 SCOTCH_Num * const rangtab, /*+ Column block range array +*/
301 SCOTCH_Num * const treetab) /*+ Separator tree array +*/
302 {
303 SCOTCH_Ordering ordedat;
304 int o;
305
306 SCOTCH_meshOrderInit (meshptr, &ordedat, permtab, peritab, cblkptr, rangtab, treetab);
307 o = SCOTCH_meshOrderCompute (meshptr, &ordedat, stratptr);
308 SCOTCH_meshOrderExit (meshptr, &ordedat);
309
310 return (o);
311 }
312
313 /*+ This routine computes an ordering
314 *** of the submesh of the API ordering
315 *** structure mesh induced by the given
316 *** vertex list, with respect to the given
317 *** strategy.
318 *** It returns:
319 *** - 0 : on success.
320 *** - !0 : on error.
321 +*/
322
323 int
SCOTCH_meshOrderList(SCOTCH_Mesh * const meshptr,const SCOTCH_Num listnbr,const SCOTCH_Num * const listtab,SCOTCH_Strat * const stratptr,SCOTCH_Num * const permtab,SCOTCH_Num * const peritab,SCOTCH_Num * const cblkptr,SCOTCH_Num * const rangtab,SCOTCH_Num * const treetab)324 SCOTCH_meshOrderList (
325 SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
326 const SCOTCH_Num listnbr, /*+ Number of vertices in list +*/
327 const SCOTCH_Num * const listtab, /*+ List of vertex indices to order +*/
328 SCOTCH_Strat * const stratptr, /*+ Ordering strategy +*/
329 SCOTCH_Num * const permtab, /*+ Ordering permutation +*/
330 SCOTCH_Num * const peritab, /*+ Inverse permutation array +*/
331 SCOTCH_Num * const cblkptr, /*+ Pointer to number of column blocks +*/
332 SCOTCH_Num * const rangtab, /*+ Column block range array +*/
333 SCOTCH_Num * const treetab) /*+ Column block range array +*/
334 {
335 SCOTCH_Ordering ordedat;
336 int o;
337
338 SCOTCH_meshOrderInit (meshptr, &ordedat, permtab, peritab, cblkptr, rangtab, treetab);
339 o = SCOTCH_meshOrderComputeList (meshptr, &ordedat, listnbr, listtab, stratptr);
340 SCOTCH_meshOrderExit (meshptr, &ordedat);
341
342 return (o);
343 }
344
345 /*+ This routine checks the consistency
346 *** of the given mesh ordering.
347 *** It returns:
348 *** - 0 : on success.
349 *** - !0 : on error.
350 +*/
351
352 int
SCOTCH_meshOrderCheck(const SCOTCH_Mesh * const meshptr,const SCOTCH_Ordering * const ordeptr)353 SCOTCH_meshOrderCheck (
354 const SCOTCH_Mesh * const meshptr,
355 const SCOTCH_Ordering * const ordeptr) /*+ Ordering to check +*/
356 {
357 return (orderCheck (&((LibOrder *) ordeptr)->o));
358 }
359
360 /*+ This routine parses the given
361 *** mesh ordering strategy.
362 *** It returns:
363 *** - 0 : if string successfully scanned.
364 *** - !0 : on error.
365 +*/
366
367 int
SCOTCH_stratMeshOrder(SCOTCH_Strat * const stratptr,const char * const string)368 SCOTCH_stratMeshOrder (
369 SCOTCH_Strat * const stratptr,
370 const char * const string)
371 {
372 if (*((Strat **) stratptr) != NULL)
373 stratExit (*((Strat **) stratptr));
374
375 if ((*((Strat **) stratptr) = stratInit (&hmeshorderststratab, string)) == NULL) {
376 errorPrint ("SCOTCH_stratMeshOrder: error in ordering strategy");
377 return (1);
378 }
379
380 return (0);
381 }
382
383 /*+ This routine provides predefined
384 *** ordering strategies.
385 *** It returns:
386 *** - 0 : if string successfully initialized.
387 *** - !0 : on error.
388 +*/
389
390 int
SCOTCH_stratMeshOrderBuild(SCOTCH_Strat * const stratptr,const SCOTCH_Num flagval,const double balrat)391 SCOTCH_stratMeshOrderBuild (
392 SCOTCH_Strat * const stratptr, /*+ Strategy to create +*/
393 const SCOTCH_Num flagval, /*+ Desired characteristics +*/
394 const double balrat) /*+ Desired imbalance ratio +*/
395 {
396 char bufftab[8192]; /* Should be enough */
397 char bbaltab[32];
398
399 strcpy (bufftab, "c{rat=0.7,cpr=n{sep=/(vnod>120)?m{vnod=100,low=h{pass=10},asc=f{bal=<BBAL>}}:;,ole=v{strat=d{cmin=0,cmax=10000000,frat=0}},ose=g},unc=n{sep=/(vnod>120)?m{vnod=100,low=h{pass=10},asc=f{bal=<BBAL>}}:;,ole=v{strat=d{cmin=0,cmax=10000000,frat=0}},ose=g}}");
400
401 sprintf (bbaltab, "%lf", balrat);
402 stringSubst (bufftab, "<BBAL>", bbaltab);
403
404 if (SCOTCH_stratMeshOrder (stratptr, bufftab) != 0) {
405 errorPrint ("SCOTCH_stratMeshOrderBuild: error in sequential ordering strategy");
406 return (1);
407 }
408
409 return (0);
410 }
411