1
/* Copyright 2004,2007 ENSEIRB, INRIA & CNRS
3
** This file is part of the Scotch software package for static mapping,
4
** graph partitioning and sparse matrix ordering.
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".
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
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.
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.
32
/************************************************************/
34
/** NAME : library_mesh_order.c **/
36
/** AUTHOR : Francois PELLEGRINI **/
38
/** FUNCTION : This module is the API for the mesh **/
39
/** ordering routines of the libSCOTCH **/
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 04 aug 2007 **/
51
/************************************************************/
54
** The defines and includes.
66
#include "hmesh_order_st.h"
67
#include "library_order.h"
70
/************************************/
72
/* These routines are the C API for */
73
/* the mesh ordering routines. */
75
/************************************/
77
/*+ This routine parses the given
78
*** mesh ordering strategy.
80
*** - 0 : if string successfully scanned.
85
SCOTCH_stratMeshOrder (
86
SCOTCH_Strat * const stratptr,
87
const char * const string)
89
if (*((Strat **) stratptr) != NULL)
90
stratExit (*((Strat **) stratptr));
92
if ((*((Strat **) stratptr) = stratInit (&hmeshorderststratab, string)) == NULL) {
93
errorPrint ("SCOTCH_stratMeshOrder: error in ordering strategy");
100
/*+ This routine initializes an API ordering
101
*** with respect to the given source graph
102
*** and the locations of output parameters.
104
*** - 0 : on success.
109
SCOTCH_meshOrderInit (
110
const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
111
SCOTCH_Ordering * const ordeptr, /*+ Ordering structure to initialize +*/
112
SCOTCH_Num * const permtab, /*+ Direct permutation array +*/
113
SCOTCH_Num * const peritab, /*+ Inverse permutation array +*/
114
SCOTCH_Num * const cblkptr, /*+ Pointer to number of column blocks +*/
115
SCOTCH_Num * const rangtab, /*+ Column block range array +*/
116
SCOTCH_Num * const treetab) /*+ Separator tree array +*/
119
LibOrder * libordeptr;
121
#ifdef SCOTCH_DEBUG_LIBRARY1
122
if (sizeof (SCOTCH_Ordering) < sizeof (LibOrder)) {
123
errorPrint ("SCOTCH_meshOrderInit: internal error");
126
#endif /* SCOTCH_DEBUG_LIBRARY1 */
128
srcmeshptr = (Mesh *) meshptr; /* Use structure as source mesh */
129
libordeptr = (LibOrder *) ordeptr;
130
libordeptr->permtab = ((permtab == NULL) || ((void *) permtab == (void *) meshptr)) ? NULL : (Gnum *) permtab;
131
libordeptr->peritab = ((peritab == NULL) || ((void *) peritab == (void *) meshptr)) ? NULL : (Gnum *) peritab;
132
libordeptr->cblkptr = ((cblkptr == NULL) || ((void *) cblkptr == (void *) meshptr)) ? NULL : (Gnum *) cblkptr;
133
libordeptr->rangtab = ((rangtab == NULL) || ((void *) rangtab == (void *) meshptr)) ? NULL : (Gnum *) rangtab;
134
libordeptr->treetab = ((treetab == NULL) || ((void *) treetab == (void *) meshptr)) ? NULL : (Gnum *) treetab;
136
return (orderInit (&libordeptr->o, srcmeshptr->baseval, srcmeshptr->vnodnbr, libordeptr->peritab));
139
/*+ This routine frees an API ordering.
141
*** - VOID : in all cases.
145
SCOTCH_meshOrderExit (
146
const SCOTCH_Mesh * const meshptr,
147
SCOTCH_Ordering * const ordeptr)
149
orderExit (&((LibOrder *) ordeptr)->o);
152
/*+ This routine saves the contents of
153
*** the given ordering to the given stream.
155
*** - 0 : on success.
160
SCOTCH_meshOrderSave (
161
const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
162
const SCOTCH_Ordering * const ordeptr, /*+ Ordering to save +*/
163
FILE * const stream) /*+ Output stream +*/
165
return (orderSave (&((LibOrder *) ordeptr)->o, ((Mesh *) meshptr)->vlbltax, stream));
168
/*+ This routine saves the mapping data
169
*** associated with the given ordering
170
*** to the given stream.
172
*** - 0 : on success.
177
SCOTCH_meshOrderSaveMap (
178
const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
179
const SCOTCH_Ordering * const ordeptr, /*+ Ordering to save +*/
180
FILE * const stream) /*+ Output stream +*/
182
return (orderSaveMap (&((LibOrder *) ordeptr)->o, ((Mesh *) meshptr)->vlbltax, stream));
185
/*+ This routine saves to the given stream
186
*** the separator tree data associated with
187
*** the given ordering.
189
*** - 0 : on success.
194
SCOTCH_meshOrderSaveTree (
195
const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
196
const SCOTCH_Ordering * const ordeptr, /*+ Ordering to save +*/
197
FILE * const stream) /*+ Output stream +*/
199
return (orderSaveTree (&((LibOrder *) ordeptr)->o, ((Mesh *) meshptr)->vlbltax, stream));
202
/*+ This routine computes an ordering
203
*** of the API ordering structure with
204
*** respect to the given strategy.
206
*** - 0 : on success.
211
SCOTCH_meshOrderCompute (
212
const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
213
SCOTCH_Ordering * const ordeptr, /*+ Ordering to compute +*/
214
const SCOTCH_Strat * const stratptr) /*+ Ordering strategy +*/
216
return (SCOTCH_meshOrderComputeList (meshptr, ordeptr, 0, NULL, stratptr));
219
/*+ This routine computes a partial ordering
220
*** of the listed nodes of the API ordering
221
*** structure mesh with respect to the given
224
*** - 0 : on success.
229
SCOTCH_meshOrderComputeList (
230
const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
231
SCOTCH_Ordering * const ordeptr, /*+ Ordering to compute +*/
232
const SCOTCH_Num listnbr, /*+ Number of vertices in list +*/
233
const SCOTCH_Num * const listtab, /*+ List of vertex indices to order +*/
234
const SCOTCH_Strat * const stratptr) /*+ Ordering strategy +*/
236
LibOrder * libordeptr; /* Pointer to ordering */
237
Mesh * srcmeshptr; /* Pointer to source mesh */
238
Hmesh srcmeshdat; /* Halo source mesh structure */
239
VertList srclistdat; /* Subgraph vertex list */
240
VertList * srclistptr; /* Pointer to subgraph vertex list */
241
const Strat * ordstratptr; /* Pointer to ordering strategy */
243
if (*((Strat **) stratptr) == NULL) /* Set default ordering strategy if necessary */
244
*((Strat **) stratptr) = stratInit (&hmeshorderststratab, "c{rat=0.7,cpr=n{sep=/(vnod>120)?m{vnod=100,low=h{pass=10},asc=f{bal=0.1}}:;,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=0.1}}:;,ole=v{strat=d{cmin=0,cmax=10000000,frat=0}},ose=g}}");
245
ordstratptr = *((Strat **) stratptr);
246
if (ordstratptr->tabl != &hmeshorderststratab) {
247
errorPrint ("SCOTCH_meshOrderComputeList: not a mesh ordering strategy");
251
srcmeshptr = (Mesh *) meshptr;
252
memCpy (&srcmeshdat.m, srcmeshptr, sizeof (Mesh)); /* Copy non-halo mesh data */
253
srcmeshdat.m.flagval &= ~MESHFREETABS; /* Do not allow to free arrays */
254
srcmeshdat.vehdtax = srcmeshdat.m.vendtax; /* End of non-halo vertices */
255
srcmeshdat.veihnbr = 0; /* No halo isolated elements */
256
srcmeshdat.vnohnbr = srcmeshdat.m.vnodnbr; /* All nodes are non-halo */
257
srcmeshdat.vnohnnd = srcmeshdat.m.vnodnnd; /* No halo present */
258
srcmeshdat.vnhlsum = srcmeshdat.m.vnlosum; /* Sum of node vertex weights */
259
srcmeshdat.enohnbr = srcmeshdat.m.edgenbr; /* All edges are non-halo */
260
srcmeshdat.levlnum = 0; /* Start from level zero */
262
libordeptr = (LibOrder *) ordeptr; /* Get ordering */
263
srclistdat.vnumnbr = (Gnum) listnbr; /* Build vertex list */
264
srclistdat.vnumtab = (Gnum *) listtab;
265
srclistptr = ((srclistdat.vnumnbr == 0) ||
266
(srclistdat.vnumnbr == srcmeshdat.m.vnodnbr))
267
? NULL : &srclistdat; /* Is the list really necessary */
268
if (srclistptr != NULL) {
269
errorPrint ("SCOTCH_meshOrderComputeList: node lists not yet implemented");
273
hmeshOrderSt (&srcmeshdat, &libordeptr->o, 0, &libordeptr->o.cblktre, ordstratptr);
275
#ifdef SCOTCH_DEBUG_LIBRARY2
276
orderCheck (&libordeptr->o);
277
#endif /* SCOTCH_DEBUG_LIBRARY2 */
279
if (libordeptr->permtab != NULL) /* Build direct permutation if wanted */
280
orderPeri (libordeptr->o.peritab, libordeptr->o.baseval, libordeptr->o.vnodnbr, libordeptr->permtab, libordeptr->o.baseval);
281
if (libordeptr->rangtab != NULL) /* Build range array if column block data wanted */
282
orderRang (&libordeptr->o, libordeptr->rangtab);
283
if (libordeptr->treetab != NULL) /* Build separator tree array if wanted */
284
orderTree (&libordeptr->o, libordeptr->treetab);
285
if (libordeptr->cblkptr != NULL) /* Set number of column blocks if wanted */
286
*(libordeptr->cblkptr) = libordeptr->o.cblknbr;
288
meshExit (&srcmeshdat.m); /* Free in case mesh had been reordered */
293
/*+ This routine computes an ordering
294
*** of the API ordering structure with
295
*** respect to the given strategy.
297
*** - 0 : on success.
303
const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
304
const SCOTCH_Strat * const stratptr, /*+ Ordering strategy +*/
305
SCOTCH_Num * const permtab, /*+ Ordering permutation +*/
306
SCOTCH_Num * const peritab, /*+ Inverse permutation array +*/
307
SCOTCH_Num * const cblkptr, /*+ Pointer to number of column blocks +*/
308
SCOTCH_Num * const rangtab, /*+ Column block range array +*/
309
SCOTCH_Num * const treetab) /*+ Separator tree array +*/
311
SCOTCH_Ordering ordedat;
314
SCOTCH_meshOrderInit (meshptr, &ordedat, permtab, peritab, cblkptr, rangtab, treetab);
315
o = SCOTCH_meshOrderCompute (meshptr, &ordedat, stratptr);
316
SCOTCH_meshOrderExit (meshptr, &ordedat);
321
/*+ This routine computes an ordering
322
*** of the submesh of the API ordering
323
*** structure mesh induced by the given
324
*** vertex list, with respect to the given
327
*** - 0 : on success.
332
SCOTCH_meshOrderList (
333
const SCOTCH_Mesh * const meshptr, /*+ Mesh to order +*/
334
const SCOTCH_Num listnbr, /*+ Number of vertices in list +*/
335
const SCOTCH_Num * const listtab, /*+ List of vertex indices to order +*/
336
const SCOTCH_Strat * const stratptr, /*+ Ordering strategy +*/
337
SCOTCH_Num * const permtab, /*+ Ordering permutation +*/
338
SCOTCH_Num * const peritab, /*+ Inverse permutation array +*/
339
SCOTCH_Num * const cblkptr, /*+ Pointer to number of column blocks +*/
340
SCOTCH_Num * const rangtab, /*+ Column block range array +*/
341
SCOTCH_Num * const treetab) /*+ Column block range array +*/
343
SCOTCH_Ordering ordedat;
346
SCOTCH_meshOrderInit (meshptr, &ordedat, permtab, peritab, cblkptr, rangtab, treetab);
347
o = SCOTCH_meshOrderComputeList (meshptr, &ordedat, listnbr, listtab, stratptr);
348
SCOTCH_meshOrderExit (meshptr, &ordedat);
353
/*+ This routine checks the consistency
354
*** of the given mesh ordering.
356
*** - 0 : on success.
361
SCOTCH_meshOrderCheck (
362
const SCOTCH_Mesh * const meshptr,
363
const SCOTCH_Ordering * const ordeptr) /*+ Ordering to check +*/
365
return (orderCheck (&((LibOrder *) ordeptr)->o));