1 /* Copyright 2004,2007,2008,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 : hgraph_order_st.c **/
35 /** **/
36 /** AUTHOR : Francois PELLEGRINI **/
37 /** **/
38 /** FUNCTION : This module is the generic call to the **/
39 /** graph ordering module, using a given **/
40 /** strategy. **/
41 /** **/
42 /** DATES : # Version 3.2 : from : 19 oct 1996 **/
43 /** to 09 sep 1998 **/
44 /** # Version 3.3 : from : 02 oct 1998 **/
45 /** to 07 sep 2001 **/
46 /** # Version 4.0 : from : 27 dec 2001 **/
47 /** to 05 jan 2005 **/
48 /** # Version 5.0 : from : 31 may 2008 **/
49 /** to 31 may 2008 **/
50 /** # Version 6.0 : from : 17 oct 2012 **/
51 /** to 17 oct 2012 **/
52 /** **/
53 /************************************************************/
54
55 /*
56 ** The defines and includes.
57 */
58
59 #define HGRAPH_ORDER_ST
60
61 #include "module.h"
62 #include "common.h"
63 #include "parser.h"
64 #include "graph.h"
65 #include "arch.h"
66 #include "mapping.h"
67 #include "order.h"
68 #include "hgraph.h"
69 #include "hgraph_order_bl.h"
70 #include "hgraph_order_cp.h"
71 #include "hgraph_order_gp.h"
72 #include "hgraph_order_hd.h"
73 #include "hgraph_order_hf.h"
74 #include "hgraph_order_kp.h"
75 #include "hgraph_order_nd.h"
76 #include "hgraph_order_si.h"
77 #include "hgraph_order_st.h"
78 #include "kgraph.h"
79 #include "kgraph_map_st.h"
80 #include "vgraph.h"
81 #include "vgraph_separate_st.h"
82
83 /*
84 ** The static and global variables.
85 */
86
87 static Hgraph hgraphorderstgraphdummy; /* Dummy graph for offset computations */
88
89 static union { /* Default parameters for block splitting method */
90 HgraphOrderBlParam param; /* Parameter zone */
91 StratNodeMethodData padding; /* To avoid reading out of structure */
92 } hgraphorderstdefaultbl = { { &stratdummy, 8 } };
93
94 static union {
95 HgraphOrderCpParam param;
96 StratNodeMethodData padding;
97 } hgraphorderstdefaultcp = { { 0.70L, &stratdummy, &stratdummy } };
98
99 static union {
100 HgraphOrderGpParam param;
101 StratNodeMethodData padding;
102 } hgraphorderstdefaultgp = { { 3 } };
103
104 static union {
105 HgraphOrderHdParam param;
106 StratNodeMethodData padding;
107 } hgraphorderstdefaulthd = { { 1, 10000, 0.08L } };
108
109 static union {
110 HgraphOrderHfParam param;
111 StratNodeMethodData padding;
112 } hgraphorderstdefaulthf = { { 1, 1000000, 0.08L } };
113
114 static union {
115 HgraphOrderKpParam param;
116 StratNodeMethodData padding;
117 } hgraphorderstdefaultkp = { { 1, &stratdummy } };
118
119 static union { /* Default parameters for nested dissection method */
120 HgraphOrderNdParam param;
121 StratNodeMethodData padding;
122 } hgraphorderstdefaultnd = { { &stratdummy, &stratdummy, &stratdummy } };
123
124 static StratMethodTab hgraphorderstmethtab[] = { /* Graph ordering methods array */
125 { HGRAPHORDERSTMETHBL, "b", hgraphOrderBl, &hgraphorderstdefaultbl },
126 { HGRAPHORDERSTMETHCP, "c", hgraphOrderCp, &hgraphorderstdefaultcp },
127 { HGRAPHORDERSTMETHGP, "g", hgraphOrderGp, &hgraphorderstdefaultgp },
128 { HGRAPHORDERSTMETHHD, "d", hgraphOrderHd, &hgraphorderstdefaulthd },
129 { HGRAPHORDERSTMETHHF, "f", hgraphOrderHf, &hgraphorderstdefaulthf },
130 { HGRAPHORDERSTMETHKP, "k", hgraphOrderKp, &hgraphorderstdefaultkp },
131 { HGRAPHORDERSTMETHND, "n", hgraphOrderNd, &hgraphorderstdefaultnd },
132 { HGRAPHORDERSTMETHSI, "s", hgraphOrderSi, NULL },
133 { -1, NULL, NULL, NULL } };
134
135 static StratParamTab hgraphorderstparatab[] = { /* The method parameter list */
136 { HGRAPHORDERSTMETHBL, STRATPARAMSTRAT, "strat",
137 (byte *) &hgraphorderstdefaultbl.param,
138 (byte *) &hgraphorderstdefaultbl.param.strat,
139 (void *) &hgraphorderststratab },
140 { HGRAPHORDERSTMETHBL, STRATPARAMINT, "cmin",
141 (byte *) &hgraphorderstdefaultbl.param,
142 (byte *) &hgraphorderstdefaultbl.param.cblkmin,
143 NULL },
144 { HGRAPHORDERSTMETHCP, STRATPARAMDOUBLE, "rat",
145 (byte *) &hgraphorderstdefaultcp.param,
146 (byte *) &hgraphorderstdefaultcp.param.comprat,
147 NULL },
148 { HGRAPHORDERSTMETHCP, STRATPARAMSTRAT, "cpr",
149 (byte *) &hgraphorderstdefaultcp.param,
150 (byte *) &hgraphorderstdefaultcp.param.stratcpr,
151 (void *) &hgraphorderststratab },
152 { HGRAPHORDERSTMETHCP, STRATPARAMSTRAT, "unc",
153 (byte *) &hgraphorderstdefaultcp.param,
154 (byte *) &hgraphorderstdefaultcp.param.stratunc,
155 (void *) &hgraphorderststratab },
156 { HGRAPHORDERSTMETHGP, STRATPARAMINT, "pass",
157 (byte *) &hgraphorderstdefaultgp.param,
158 (byte *) &hgraphorderstdefaultgp.param.passnbr,
159 NULL },
160 { HGRAPHORDERSTMETHHD, STRATPARAMINT, "cmin",
161 (byte *) &hgraphorderstdefaulthd.param,
162 (byte *) &hgraphorderstdefaulthd.param.colmin,
163 NULL },
164 { HGRAPHORDERSTMETHHD, STRATPARAMINT, "cmax",
165 (byte *) &hgraphorderstdefaulthd.param,
166 (byte *) &hgraphorderstdefaulthd.param.colmax,
167 NULL },
168 { HGRAPHORDERSTMETHHD, STRATPARAMDOUBLE, "frat",
169 (byte *) &hgraphorderstdefaulthd.param,
170 (byte *) &hgraphorderstdefaulthd.param.fillrat,
171 NULL },
172 { HGRAPHORDERSTMETHHF, STRATPARAMINT, "cmin",
173 (byte *) &hgraphorderstdefaulthf.param,
174 (byte *) &hgraphorderstdefaulthf.param.colmin,
175 NULL },
176 { HGRAPHORDERSTMETHHF, STRATPARAMINT, "cmax",
177 (byte *) &hgraphorderstdefaulthf.param,
178 (byte *) &hgraphorderstdefaulthf.param.colmax,
179 NULL },
180 { HGRAPHORDERSTMETHHF, STRATPARAMDOUBLE, "frat",
181 (byte *) &hgraphorderstdefaulthf.param,
182 (byte *) &hgraphorderstdefaulthf.param.fillrat,
183 NULL },
184 { HGRAPHORDERSTMETHKP, STRATPARAMINT, "siz",
185 (byte *) &hgraphorderstdefaultkp.param,
186 (byte *) &hgraphorderstdefaultkp.param.partsiz,
187 NULL },
188 { HGRAPHORDERSTMETHKP, STRATPARAMSTRAT, "strat",
189 (byte *) &hgraphorderstdefaultkp.param,
190 (byte *) &hgraphorderstdefaultkp.param.strat,
191 (void *) &kgraphmapststratab },
192 { HGRAPHORDERSTMETHND, STRATPARAMSTRAT, "sep",
193 (byte *) &hgraphorderstdefaultnd.param,
194 (byte *) &hgraphorderstdefaultnd.param.sepstrat,
195 (void *) &vgraphseparateststratab },
196 { HGRAPHORDERSTMETHND, STRATPARAMSTRAT, "ole",
197 (byte *) &hgraphorderstdefaultnd.param,
198 (byte *) &hgraphorderstdefaultnd.param.ordstratlea,
199 (void *) &hgraphorderststratab },
200 { HGRAPHORDERSTMETHND, STRATPARAMSTRAT, "ose",
201 (byte *) &hgraphorderstdefaultnd.param,
202 (byte *) &hgraphorderstdefaultnd.param.ordstratsep,
203 (void *) &hgraphorderststratab },
204 { HGRAPHORDERSTMETHNBR, STRATPARAMINT, NULL,
205 NULL, NULL, NULL } };
206
207 static StratParamTab hgraphorderstcondtab[] = { /* Graph condition parameter table */
208 { STRATNODECOND, STRATPARAMINT, "edge",
209 (byte *) &hgraphorderstgraphdummy,
210 (byte *) &hgraphorderstgraphdummy.s.edgenbr,
211 NULL },
212 { STRATNODECOND, STRATPARAMINT, "levl",
213 (byte *) &hgraphorderstgraphdummy,
214 (byte *) &hgraphorderstgraphdummy.levlnum,
215 NULL },
216 { STRATNODECOND, STRATPARAMINT, "load",
217 (byte *) &hgraphorderstgraphdummy,
218 (byte *) &hgraphorderstgraphdummy.vnlosum,
219 NULL },
220 { STRATNODECOND, STRATPARAMDOUBLE, "mdeg",
221 (byte *) &hgraphorderstgraphdummy,
222 (byte *) &hgraphorderstgraphdummy.s.degrmax,
223 NULL },
224 { STRATNODECOND, STRATPARAMINT, "vert",
225 (byte *) &hgraphorderstgraphdummy,
226 (byte *) &hgraphorderstgraphdummy.vnohnbr, /* Only consider non-halo vertices */
227 NULL },
228 { STRATNODENBR, STRATPARAMINT, NULL,
229 NULL, NULL, NULL } };
230
231 StratTab hgraphorderststratab = { /* Strategy tables for graph ordering methods */
232 hgraphorderstmethtab,
233 hgraphorderstparatab,
234 hgraphorderstcondtab };
235
236 /************************************/
237 /* */
238 /* This routine is the entry point */
239 /* for the graph ordering routines. */
240 /* */
241 /************************************/
242
243 /* This routine computes an ordering
244 ** with respect to a given strategy.
245 ** It returns:
246 ** - 0 : on success.
247 ** - !0 : on error.
248 */
249
250 int
hgraphOrderSt(const Hgraph * restrict const grafptr,Order * restrict const ordeptr,const Gnum ordenum,OrderCblk * restrict const cblkptr,const Strat * restrict const strat)251 hgraphOrderSt (
252 const Hgraph * restrict const grafptr, /*+ Subgraph to order +*/
253 Order * restrict const ordeptr, /*+ Ordering to complete +*/
254 const Gnum ordenum, /*+ Index to start ordering at +*/
255 OrderCblk * restrict const cblkptr, /*+ Current column block +*/
256 const Strat * restrict const strat) /*+ Graph ordering strategy +*/
257 {
258 StratTest val;
259 int o;
260
261 if (grafptr->vnohnbr == 0) /* Return immediately if nothing to do */
262 return (0);
263
264 o = 0;
265 switch (strat->type) {
266 case STRATNODECONCAT :
267 errorPrint ("hgraphOrderSt: concatenation operator not available for graph ordering strategies");
268 return (1);
269 case STRATNODECOND :
270 o = stratTestEval (strat->data.cond.test, &val, (void *) grafptr); /* Evaluate expression */
271 if (o == 0) { /* If evaluation was correct */
272 #ifdef SCOTCH_DEBUG_HGRAPH2
273 if ((val.typetest != STRATTESTVAL) &&
274 (val.typenode != STRATPARAMLOG)) {
275 errorPrint ("hgraphOrderSt: invalid test result");
276 o = 1;
277 break;
278 }
279 #endif /* SCOTCH_DEBUG_HGRAPH2 */
280 if (val.data.val.vallog == 1) /* If expression is true */
281 o = hgraphOrderSt (grafptr, ordeptr, ordenum, cblkptr, strat->data.cond.strat[0]); /* Apply first strategy */
282 else { /* Else if expression is false */
283 if (strat->data.cond.strat[1] != NULL) /* And if there is an else statement */
284 o = hgraphOrderSt (grafptr, ordeptr, ordenum, cblkptr, strat->data.cond.strat[1]); /* Apply second strategy */
285 }
286 }
287 break;
288 case STRATNODEEMPTY :
289 hgraphOrderSi (grafptr, ordeptr, ordenum, cblkptr); /* Always maintain a consistent ordering */
290 break;
291 case STRATNODESELECT :
292 errorPrint ("hgraphOrderSt: selection operator not available for graph ordering strategies");
293 return (1);
294 #ifdef SCOTCH_DEBUG_HGRAPH2
295 case STRATNODEMETHOD :
296 #else /* SCOTCH_DEBUG_HGRAPH2 */
297 default :
298 #endif /* SCOTCH_DEBUG_HGRAPH2 */
299 return (strat->tabl->methtab[strat->data.method.meth].func (grafptr, ordeptr, ordenum, cblkptr, (void *) &strat->data.method.data));
300 #ifdef SCOTCH_DEBUG_HGRAPH2
301 default :
302 errorPrint ("hgraphOrderSt: invalid parameter");
303 return (1);
304 #endif /* SCOTCH_DEBUG_HGRAPH2 */
305 }
306 return (o);
307 }
308