SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
compute_symmetry_sassy_nauty.cpp
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file compute_symmetry_sassy_nauty.c
26 * @brief interface for symmetry computations to sassy as a preprocessor to nauty
27 * @author Marc Pfetsch
28 * @author Gioni Mexi
29 * @author Christopher Hojny
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
34#include "build_sassy_graph.h"
35#include "compute_symmetry.h"
36
37/* the following determines whether nauty or traces is used: */
38#define NAUTY
39
40#ifdef NAUTY
41#include "nauty/nauty.h"
42#include "nauty/nausparse.h"
43#else
44#include "nauty/traces.h"
45#endif
46
47/* include sassy */
48#ifdef __GNUC__
49#pragma GCC diagnostic ignored "-Wshadow"
50#pragma GCC diagnostic ignored "-Wunused-variable"
51#pragma GCC diagnostic ignored "-Wsign-compare"
52#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
53#endif
54
55#ifdef _MSC_VER
56# pragma warning(push)
57# pragma warning(disable: 4189) // local variable is initialized but not referenced
58# pragma warning(disable: 4388) // compare signed and unsigned expression
59# pragma warning(disable: 4456) // shadowed variable
60# pragma warning(disable: 4430) // missing type specifier
61#endif
62
63#include <sassy/preprocessor.h>
64#ifdef NAUTY
65#include "sassy/tools/nauty_converter.h"
66#else
67#include "sassy/tools/traces_converter.h"
68#endif
69
70#ifdef __GNUC__
71#pragma GCC diagnostic warning "-Wunused-but-set-variable"
72#pragma GCC diagnostic warning "-Wsign-compare"
73#pragma GCC diagnostic warning "-Wunused-variable"
74#pragma GCC diagnostic warning "-Wshadow"
75#endif
76
77#ifdef _MSC_VER
78# pragma warning(pop)
79#endif
80
81#include "build_sassy_graph.h"
82
83#include "scip/expr_var.h"
84#include "scip/expr_sum.h"
85#include "scip/expr_pow.h"
86#include "scip/expr.h"
87#include "scip/cons_nonlinear.h"
88#include "scip/cons_linear.h"
89#include "scip/scip_mem.h"
90#include "scip/symmetry_graph.h"
91
92
93/** struct for symmetry callback */
94struct SYMMETRY_Data
95{
96 SCIP* scip; /**< SCIP pointer */
97 SYM_SYMTYPE symtype; /**< type of symmetries that need to be computed */
98 int npermvars; /**< number of variables for permutations */
99 int nperms; /**< number of permutations */
100 int** perms; /**< permutation generators as (nperms x npermvars) matrix */
101 int nmaxperms; /**< maximal number of permutations */
102 int maxgenerators; /**< maximal number of generators constructed (= 0 if unlimited) */
103 SCIP_Bool restricttovars; /**< whether permutations shall be restricted to variables */
104};
105
106
107/* ------------------- hook functions ------------------- */
108
109/** callback function for sassy */ /*lint -e{715}*/
110static
112 void* user_param, /**< parameter supplied at call to sassy */
113 int n, /**< dimension of permutations */
114 const int* aut, /**< permutation */
115 int nsupp, /**< support size */
116 const int* suppa /**< support list */
117 )
118{
119 assert( aut != NULL );
120 assert( user_param != NULL );
121
122 SYMMETRY_Data* data = static_cast<SYMMETRY_Data*>(user_param);
123 assert( data->scip != NULL );
124 assert( data->maxgenerators >= 0 );
125
126 /* make sure we do not generate more that maxgenerators many permutations */
127 if ( data->maxgenerators != 0 && data->nperms >= data->maxgenerators )
128 return;
129
130 /* copy first part of automorphism */
131 bool isIdentity = true;
132 int* p = 0;
133 int permlen;
134 if ( data->restricttovars )
135 {
136 switch ( data->symtype )
137 {
138 case SYM_SYMTYPE_PERM:
139 permlen = data->npermvars;
140 break;
141 default:
143 permlen = 2 * data->npermvars;
144 }
145 }
146 else
147 permlen = n;
148
149 /* check whether permutation is identity */
150 for (int j = 0; j < permlen; ++j)
151 {
152 if ( (int) aut[j] != j )
153 isIdentity = false;
154 }
155
156 /* don't store identity permutations */
157 if ( isIdentity )
158 return;
159
161 return;
162
163 /* store symmetry */
164 for (int j = 0; j < permlen; ++j)
165 p[j] = (int) aut[j];
166
167 /* check whether we should allocate space for perms */
168 if ( data->nmaxperms <= 0 )
169 {
170 if ( data->maxgenerators == 0 )
171 data->nmaxperms = 100; /* seems to cover many cases */
172 else
173 data->nmaxperms = data->maxgenerators;
174
175 if ( SCIPallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms) != SCIP_OKAY )
176 return;
177 }
178 else if ( data->nperms >= data->nmaxperms ) /* check whether we need to resize */
179 {
180 int newsize = SCIPcalcMemGrowSize(data->scip, data->nperms + 1);
181 assert( newsize >= data->nperms );
182 assert( data->maxgenerators == 0 );
183
184 if ( SCIPreallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms, newsize) != SCIP_OKAY )
185 return;
186
187 data->nmaxperms = newsize;
188 }
189
190 data->perms[data->nperms++] = p;
191}
192
193
194/** return whether symmetry can be computed */
196{
197 return TRUE;
198}
199
200
201/** return name of external program used to compute generators */
202const char* SYMsymmetryGetName(void)
203{
204#ifdef NAUTY
205 return "Nauty " NAUTYVERSION;
206#else
207 return "Traces " NAUTYVERSION;
208#endif
209}
210
211/** return description of external program used to compute generators */
212const char* SYMsymmetryGetDesc(void)
213{
214#ifdef NAUTY
215 return "Computing Graph Automorphism Groups by Brendan D. McKay (users.cecs.anu.edu.au/~bdm/nauty)";
216#else
217 return "Computing Graph Automorphism Groups by Adolfo Piperno (pallini.di.uniroma1.it)";
218#endif
219}
220
221#define STR(x) #x
222#define XSTR(x) STR(x)
223
224/** return name of additional external program used for computing symmetries */
225const char* SYMsymmetryGetAddName(void)
226{
227 return "sassy " XSTR(SASSY_VERSION_MAJOR) "." XSTR(SASSY_VERSION_MINOR);
228}
229
230/** return description of additional external program used to compute symmetries */
231const char* SYMsymmetryGetAddDesc(void)
232{
233 return "Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)";
234}
235
236/** computes autormorphisms of a graph */
237static
239 SCIP* scip, /**< SCIP pointer */
240 SYM_SYMTYPE symtype, /**< type of symmetries that need to be computed */
241 sassy::static_graph* G, /**< pointer to graph for that automorphisms are computed */
242 int nsymvars, /**< number of variables encoded in graph */
243 int maxgenerators, /**< maximum number of generators to be constructed (=0 if unlimited) */
244 int*** perms, /**< pointer to store generators as (nperms x npermvars) matrix */
245 int* nperms, /**< pointer to store number of permutations */
246 int* nmaxperms, /**< pointer to store maximal number of permutations
247 * (needed for freeing storage) */
248 SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
249 SCIP_Bool restricttovars, /**< whether permutations shall be restricted to variables */
250 SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
251 )
252{
253 SCIP_Real oldtime;
254
255 assert( scip != NULL );
256 assert( G != NULL );
257 assert( maxgenerators >= 0 );
258 assert( perms != NULL );
259 assert( nperms != NULL );
260 assert( nmaxperms != NULL );
261 assert( log10groupsize != NULL );
262 assert( symcodetime != NULL );
263
264 /* init */
265 *nperms = 0;
266 *nmaxperms = 0;
267 *perms = NULL;
268 *log10groupsize = 0;
269 *symcodetime = 0.0;
270
271 /* init data */
272 struct SYMMETRY_Data data;
273 data.scip = scip;
274 data.symtype = symtype;
275 data.npermvars = nsymvars;
276 data.nperms = 0;
277 data.nmaxperms = 0;
279 data.perms = NULL;
281
283
284 /* set up sassy preprocessor */
285 sassy::preprocessor sassy;
286
287 /* turn off some preprocessing that generates redudant permutations */
288 sassy::configstruct sconfig;
289 sconfig.CONFIG_PREP_DEACT_PROBE = true;
290 sassy.configure(&sconfig);
291
292 /* lambda function to have access to data and pass it to sassyhook above */
293 sassy::sassy_hook sassyglue = [&](int n, const int* p, int nsupp, const int* suppa) {
294 sassyhook((void*)&data, n, p, nsupp, suppa);
295 };
296
297 /* call sassy to reduce graph */
298 sassy.reduce(G, &sassyglue);
299
300 /* first, convert the graph */
302 DYNALLSTAT(int, lab, lab_sz);
303 DYNALLSTAT(int, ptn, ptn_sz);
304
305#ifdef NAUTY
307 statsblk stats;
308 DYNALLSTAT(int, orbits, orbits_sz);
309 DYNALLOC1(int, orbits, orbits_sz, sg.nv, "malloc");
311 /* init callback functions for nauty (accumulate the group generators found by nauty) */
312 options.writeautoms = FALSE;
313 options.userautomproc = sassy::preprocessor::nauty_hook;
314 options.defaultptn = FALSE; /* use color classes */
315 *log10groupsize = 0.0;
316 if(sg.nv > 0) {
317 sparsenauty(&sg, lab, ptn, orbits, &options, &stats, NULL);
318 *log10groupsize = (SCIP_Real) stats.grpsize2;
319 }
320#else
322 TracesStats stats;
323 DYNALLSTAT(int, orbits, orbits_sz);
324 DYNALLOC1(int, orbits, orbits_sz, sg.nv, "malloc");
326 /* init callback functions for traces (accumulate the group generators found by traces) */
327 options.writeautoms = FALSE;
328 options.userautomproc = sassy::preprocessor::traces_hook;
329 options.defaultptn = FALSE; /* use color classes */
330 if(sg.nv > 0) {
331 Traces(&sg, lab, ptn, orbits, &options, &stats, NULL);
332 }
333#endif
334
335 /* clean up */
338 SG_FREE(sg);
339
341
342 /* prepare return values */
343 if ( data.nperms > 0 )
344 {
345 *perms = data.perms;
346 *nperms = data.nperms;
347 *nmaxperms = data.nmaxperms;
348 }
349 else
350 {
351 assert( data.perms == NULL );
352 assert( data.nmaxperms == 0 );
353
354 *perms = NULL;
355 *nperms = 0;
356 *nmaxperms = 0;
357 }
358
359 return SCIP_OKAY;
360}
361
362/** compute generators of symmetry group */
364 SCIP* scip, /**< SCIP pointer */
365 int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
366 SYM_GRAPH* symgraph, /**< symmetry detection graph */
367 int* nperms, /**< pointer to store number of permutations */
368 int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
369 int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
370 SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
371 SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
372 )
373{
374 SCIP_Bool success = FALSE;
375
376 assert( scip != NULL );
377 assert( maxgenerators >= 0 );
378 assert( symgraph != NULL );
379 assert( nperms != NULL );
380 assert( nmaxperms != NULL );
381 assert( perms != NULL );
382 assert( log10groupsize != NULL );
383 assert( symcodetime != NULL );
384
385 /* init */
386 *nperms = 0;
387 *nmaxperms = 0;
388 *perms = NULL;
389 *log10groupsize = 0;
390 *symcodetime = 0.0;
391
392 /* create sassy graph */
393 sassy::static_graph sassygraph;
394
396
397 /* compute symmetries */
399 maxgenerators, perms, nperms, nmaxperms, log10groupsize, TRUE, symcodetime) );
400
401 return SCIP_OKAY;
402}
403
404/** returns whether two given graphs are identical */
406 SCIP* scip, /**< SCIP pointer */
407 SYM_SYMTYPE symtype, /**< type of symmetries to be checked */
408 SYM_GRAPH* G1, /**< first graph */
409 SYM_GRAPH* G2 /**< second graph */
410 )
411{
412 int** perms;
413 int nnodes;
414 int nperms;
415 int nmaxperms;
416 int nnodesfromG1;
417 SCIP_Real symcodetime = 0.0;
418 SCIP_Real log10groupsize;
419 SCIP_Bool success;
420
421 /* create sassy graph */
422 sassy::static_graph sassygraph;
423
425
426 if ( ! success )
427 return FALSE;
428
429 /* compute symmetries */
431 &perms, &nperms, &nmaxperms, &log10groupsize, FALSE, &symcodetime) );
432
433 /* since G1 and G2 are connected and disjoint, they are isomorphic iff there is a permutation
434 * mapping a node from G1 to a node of G2
435 */
436 success = FALSE;
437 for (int p = 0; p < nperms && ! success; ++p)
438 {
439 for (int i = 0; i < nnodesfromG1; ++i)
440 {
441 if ( perms[p][i] >= nnodesfromG1 )
442 {
443 success = TRUE;
444 break;
445 }
446 }
447 }
448
449 for (int p = 0; p < nperms; ++p)
450 {
452 }
454
455 return success;
456}
SCIP_RETCODE SYMbuildSassyGraph(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *graph, SCIP_Bool *success)
SCIP_RETCODE SYMbuildSassyGraphCheck(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *G1, SYM_GRAPH *G2, int *nnodes, int *nnodesfromG1, SCIP_Bool *success)
methods to build sassy graph for symmetry detection
interface for symmetry computations
SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
const char * SYMsymmetryGetName(void)
static SCIP_RETCODE computeAutomorphisms(SCIP *scip, SYM_SYMTYPE symtype, sassy::static_graph *G, int nsymvars, int maxgenerators, int ***perms, int *nperms, int *nmaxperms, SCIP_Real *log10groupsize, SCIP_Bool restricttovars, SCIP_Real *symcodetime)
const char * SYMsymmetryGetAddName(void)
SCIP_Bool SYMcanComputeSymmetry(void)
const char * SYMsymmetryGetDesc(void)
static void sassyhook(void *user_param, int n, const int *aut, int nsupp, const int *suppa)
const char * SYMsymmetryGetAddDesc(void)
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_GRAPH *symgraph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
Constraint handler for linear constraints in their most general form, .
constraint handler for nonlinear constraints specified by algebraic expressions
#define NULL
Definition def.h:267
#define SCIP_Real
Definition def.h:173
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_CALL_ABORT(x)
Definition def.h:353
#define SCIP_CALL(x)
Definition def.h:374
private functions to work with algebraic expressions
power and signed power expression handlers
sum expression handler
variable expression handler
#define nnodes
Definition gastrans.c:74
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition scip_mem.c:139
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition scip_mem.h:111
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
public methods for memory management
methods for dealing with symmetry detection graphs
enum SCIP_Retcode SCIP_RETCODE
enum SYM_Symtype SYM_SYMTYPE
@ SYM_SYMTYPE_SIGNPERM
@ SYM_SYMTYPE_PERM