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-2025 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.cpp
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/** struct for symmetry callback */
93struct SYMMETRY_Data
94{
95 SCIP* scip; /**< SCIP pointer */
96 SYM_SYMTYPE symtype; /**< type of symmetries that need to be computed */
97 int npermvars; /**< number of variables for permutations */
98 int nperms; /**< number of permutations */
99 int** perms; /**< permutation generators as (nperms x npermvars) matrix */
100 int nmaxperms; /**< maximal number of permutations */
101 int maxgenerators; /**< maximal number of generators constructed (= 0 if unlimited) */
102 SCIP_Bool restricttovars; /**< whether permutations shall be restricted to variables */
103};
104
105#ifdef NAUTY
106/** struct for nauty callback */
107struct NAUTY_Data
108{
109 SCIP* scip; /**< SCIP pointer */
110 int ntreenodes; /**< number of nodes visitied in nauty's search tree */
111 int maxncells; /**< maximum number of cells in nauty's search tree */
112 int maxnnodes; /**< maximum number of nodes in nauty's search tree */
113};
114
115/** static data for nauty callback */
116#if defined(_Thread_local)
117static _Thread_local struct NAUTY_Data nautydata_;
118#else
119static struct NAUTY_Data nautydata_;
120#endif
121
122#endif
123
124/* ------------------- hook functions ------------------- */
125
126/** callback function for sassy */ /*lint -e{715}*/
127static
129 void* user_param, /**< parameter supplied at call to sassy */
130 int n, /**< dimension of permutations */
131 const int* aut, /**< permutation */
132 int nsupp, /**< support size */
133 const int* suppa /**< support list */
134 )
135{
136 assert( aut != NULL );
137 assert( user_param != NULL );
138
139 SYMMETRY_Data* data = static_cast<SYMMETRY_Data*>(user_param);
140 assert( data->scip != NULL );
141 assert( data->maxgenerators >= 0 );
142
143 /* make sure we do not generate more that maxgenerators many permutations */
144 if ( data->maxgenerators != 0 && data->nperms >= data->maxgenerators )
145 return;
146
147 /* copy first part of automorphism */
148 bool isIdentity = true;
149 int* p = 0;
150 int permlen;
151 if ( data->restricttovars )
152 {
153 switch ( data->symtype )
154 {
155 case SYM_SYMTYPE_PERM:
156 permlen = data->npermvars;
157 break;
158 default:
160 permlen = 2 * data->npermvars;
161 }
162 }
163 else
164 permlen = n;
165
166 /* check whether permutation is identity */
167 for (int j = 0; j < permlen; ++j)
168 {
169 if ( (int) aut[j] != j )
170 isIdentity = false;
171 }
172
173 /* don't store identity permutations */
174 if ( isIdentity )
175 return;
176
177 if ( SCIPallocBlockMemoryArray(data->scip, &p, permlen) != SCIP_OKAY )
178 return;
179
180 /* store symmetry */
181 for (int j = 0; j < permlen; ++j)
182 p[j] = (int) aut[j];
183
184 /* check whether we should allocate space for perms */
185 if ( data->nmaxperms <= 0 )
186 {
187 if ( data->maxgenerators == 0 )
188 data->nmaxperms = 100; /* seems to cover many cases */
189 else
190 data->nmaxperms = data->maxgenerators;
191
192 if ( SCIPallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms) != SCIP_OKAY )
193 return;
194 }
195 else if ( data->nperms >= data->nmaxperms ) /* check whether we need to resize */
196 {
197 int newsize = SCIPcalcMemGrowSize(data->scip, data->nperms + 1);
198 assert( newsize >= data->nperms );
199 assert( data->maxgenerators == 0 );
200
201 if ( SCIPreallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms, newsize) != SCIP_OKAY )
202 return;
203
204 data->nmaxperms = newsize;
205 }
206
207 data->perms[data->nperms++] = p;
208}
209
210#ifdef NAUTY
211
212/** callback function for nauty to terminate early */ /*lint -e{715}*/
213static
215 graph* g, /**< sparse graph for nauty */
216 int* lab, /**< labels of node */
217 int* ptn, /**< array indicating change of set in node parition of graph */
218 int level, /**< level of current node in nauty's tree */
219 int numcells, /**< number of cells in current partition */
220 int tc, /**< index of target cells in lab if children need to be explored */
221 int code, /**< code produced by refinement and vertex-invariant procedures */
222 int m, /**< number of edges in the graph */
223 int n /**< number of nodes in the graph */
224 )
225{ /* lint --e{715} */
226 SCIP_Bool terminate = FALSE;
227 nautydata_.ntreenodes++;
228
229 /* add some iteration limit to avoid spending too much time in nauty */
230 if ( numcells >= nautydata_.maxncells )
231 {
232 terminate = TRUE;
234 "symmetry computation terminated early, because number of cells %d in Nauty exceeds limit of %d\n",
235 numcells, nautydata_.maxncells);
237 "for running full symmetry detection, increase value of parameter propagating/symmetry/nautymaxncells\n");
238 }
239 else if ( nautydata_.ntreenodes >= nautydata_.maxnnodes )
240 {
241 terminate = TRUE;
243 "symmetry computation terminated early, because number of"
244 " nodes %d in Nauty's search tree exceeds limit of %d\n", nautydata_.ntreenodes, nautydata_.maxnnodes);
246 "for running full symmetry detection, increase value of"
247 " parameter propagating/symmetry/nautymaxnnodes\n");
248 }
249
250 if ( terminate )
251 {
252 /* request a kill from nauty */
253 nauty_kill_request = 1;
254 return;
255 }
256}
257
258#endif
259
260/** return whether symmetry can be computed */
262{
263 return TRUE;
264}
265
266/** nauty/traces version string */
267#ifdef NAUTY
268static const char nautyname[] = {'N', 'a', 'u', 't', 'y', ' ', NAUTYVERSIONID/10000 + '0', '.', (NAUTYVERSIONID%10000)/1000 + '0', '.', (NAUTYVERSIONID%1000)/10 + '0', '\0'};
269#else
270static const char nautyname[] = {'T', 'r', 'a', 'c', 'e', 's', ' ', NAUTYVERSIONID/10000 + '0', '.', (NAUTYVERSIONID%10000)/1000 + '0', '.', (NAUTYVERSIONID%1000)/10 + '0', '\0'};
271#endif
272
273/** return name of external program used to compute generators */
274const char* SYMsymmetryGetName(void)
275{
276 return nautyname;
277}
278
279/** return description of external program used to compute generators */
280const char* SYMsymmetryGetDesc(void)
281{
282#ifdef NAUTY
283 return "Computing Graph Automorphism Groups by Brendan D. McKay (users.cecs.anu.edu.au/~bdm/nauty)";
284#else
285 return "Computing Graph Automorphism Groups by Adolfo Piperno (pallini.di.uniroma1.it)";
286#endif
287}
288
289#define STR(x) #x
290#define XSTR(x) STR(x)
291
292/** return name of additional external program used for computing symmetries */
293const char* SYMsymmetryGetAddName(void)
294{
295 return "sassy " XSTR(SASSY_VERSION_MAJOR) "." XSTR(SASSY_VERSION_MINOR);
296}
297
298/** return description of additional external program used to compute symmetries */
299const char* SYMsymmetryGetAddDesc(void)
300{
301 return "Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)";
302}
303
304/** computes autormorphisms of a graph */
305static
307 SCIP* scip, /**< SCIP pointer */
308 SYM_SYMTYPE symtype, /**< type of symmetries that need to be computed */
309 sassy::static_graph* G, /**< pointer to graph for that automorphisms are computed */
310 int nsymvars, /**< number of variables encoded in graph */
311 int maxgenerators, /**< maximum number of generators to be constructed (=0 if unlimited) */
312 int*** perms, /**< pointer to store generators as (nperms x npermvars) matrix */
313 int* nperms, /**< pointer to store number of permutations */
314 int* nmaxperms, /**< pointer to store maximal number of permutations
315 * (needed for freeing storage) */
316 SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
317 SCIP_Bool restricttovars, /**< whether permutations shall be restricted to variables */
318 SCIP_Real* symcodetime, /**< pointer to store the time for symmetry code */
319 SCIP_Bool canterminateearly /**< whether we allow to interrupt symmetry detection early
320 * (e.g., because of iteration limits) */
321 )
322{
323 SCIP_Real oldtime;
324
325 assert( scip != NULL );
326 assert( G != NULL );
327 assert( maxgenerators >= 0 );
328 assert( perms != NULL );
329 assert( nperms != NULL );
330 assert( nmaxperms != NULL );
331 assert( log10groupsize != NULL );
332 assert( symcodetime != NULL );
333
334 /* init */
335 *nperms = 0;
336 *nmaxperms = 0;
337 *perms = NULL;
338 *log10groupsize = 0;
339 *symcodetime = 0.0;
340
341 /* init data */
342 struct SYMMETRY_Data data;
343 data.scip = scip;
344 data.symtype = symtype;
345 data.npermvars = nsymvars;
346 data.nperms = 0;
347 data.nmaxperms = 0;
349 data.perms = NULL;
351
352#ifdef NAUTY
353 nautydata_.scip = scip;
354 nautydata_.ntreenodes = 0;
355 SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/nautymaxncells", &nautydata_.maxncells) );
356 SCIP_CALL( SCIPgetIntParam(scip, "propagating/symmetry/nautymaxnnodes", &nautydata_.maxnnodes) );
357#endif
358
359 oldtime = SCIPgetSolvingTime(scip);
360
361 /* set up sassy preprocessor */
362 sassy::preprocessor sassy;
363
364 /* turn off some preprocessing that generates redudant permutations */
365 sassy::configstruct sconfig;
366 sconfig.CONFIG_PREP_DEACT_PROBE = true;
367 sassy.configure(&sconfig);
368
369 /* lambda function to have access to data and pass it to sassyhook above */
370 sassy::sassy_hook sassyglue = [&](int n, const int* p, int nsupp, const int* suppa) {
371 sassyhook((void*)&data, n, p, nsupp, suppa);
372 };
373
374 /* call sassy to reduce graph */
375 sassy.reduce(G, &sassyglue);
376
377 /* first, convert the graph */
378 sparsegraph sg;
379 DYNALLSTAT(int, lab, lab_sz);
380 DYNALLSTAT(int, ptn, ptn_sz);
381
382#ifdef NAUTY
383 convert_sassy_to_nauty(G, &sg, &lab, &lab_sz, &ptn, &ptn_sz);
384 statsblk stats;
385 DYNALLSTAT(int, orbits, orbits_sz);
386 DYNALLOC1(int, orbits, orbits_sz, sg.nv, "malloc");
387 DEFAULTOPTIONS_SPARSEGRAPH(options);
388 /* init callback functions for nauty (accumulate the group generators found by nauty) */
389 options.writeautoms = FALSE;
390 options.userautomproc = sassy::preprocessor::nauty_hook;
391 options.defaultptn = FALSE; /* use color classes */
392 if ( canterminateearly )
393 options.usernodeproc = nautyterminationhook;
394 *log10groupsize = 0.0;
395 if(sg.nv > 0) {
396 sparsenauty(&sg, lab, ptn, orbits, &options, &stats, NULL);
397 *log10groupsize = (SCIP_Real) stats.grpsize2;
398 }
399#else
400 convert_sassy_to_traces(&sassygraph, &sg, &lab, &lab_sz, &ptn, &ptn_sz);
401 TracesStats stats;
402 DYNALLSTAT(int, orbits, orbits_sz);
403 DYNALLOC1(int, orbits, orbits_sz, sg.nv, "malloc");
404 DEFAULTOPTIONS_TRACES(options);
405 /* init callback functions for traces (accumulate the group generators found by traces) */
406 options.writeautoms = FALSE;
407 options.userautomproc = sassy::preprocessor::traces_hook;
408 options.defaultptn = FALSE; /* use color classes */
409 if(sg.nv > 0) {
410 Traces(&sg, lab, ptn, orbits, &options, &stats, NULL);
411 }
412#endif
413
414 /* clean up */
415 DYNFREE(lab, lab_sz);
416 DYNFREE(ptn, ptn_sz);
417 SG_FREE(sg);
418
419 *symcodetime = SCIPgetSolvingTime(scip) - oldtime;
420
421 /* prepare return values */
422 if ( data.nperms > 0 )
423 {
424 *perms = data.perms;
425 *nperms = data.nperms;
426 *nmaxperms = data.nmaxperms;
427 }
428 else
429 {
430 assert( data.perms == NULL );
431 assert( data.nmaxperms == 0 );
432
433 *perms = NULL;
434 *nperms = 0;
435 *nmaxperms = 0;
436 }
437
438 return SCIP_OKAY;
439}
440
441/** compute generators of symmetry group */
443 SCIP* scip, /**< SCIP pointer */
444 int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
445 SYM_GRAPH* symgraph, /**< symmetry detection graph */
446 int* nperms, /**< pointer to store number of permutations */
447 int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
448 int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
449 SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
450 SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
451 )
452{
453 SCIP_Bool success = FALSE;
454
455 assert( scip != NULL );
456 assert( maxgenerators >= 0 );
457 assert( symgraph != NULL );
458 assert( nperms != NULL );
459 assert( nmaxperms != NULL );
460 assert( perms != NULL );
461 assert( log10groupsize != NULL );
462 assert( symcodetime != NULL );
463
464 /* init */
465 *nperms = 0;
466 *nmaxperms = 0;
467 *perms = NULL;
468 *log10groupsize = 0;
469 *symcodetime = 0.0;
470
471 /* create sassy graph */
472 sassy::static_graph sassygraph;
473
474 SCIP_CALL( SYMbuildSassyGraph(scip, &sassygraph, symgraph, &success) );
475
476 /* compute symmetries */
478 maxgenerators, perms, nperms, nmaxperms, log10groupsize, TRUE, symcodetime, TRUE) );
479
480 return SCIP_OKAY;
481}
482
483/** returns whether two given graphs are identical */
485 SCIP* scip, /**< SCIP pointer */
486 SYM_SYMTYPE symtype, /**< type of symmetries to be checked */
487 SYM_GRAPH* G1, /**< first graph */
488 SYM_GRAPH* G2 /**< second graph */
489 )
490{
491 int** perms;
492 int nnodes;
493 int nperms;
494 int nmaxperms;
495 int nnodesfromG1;
496 SCIP_Real symcodetime = 0.0;
497 SCIP_Real log10groupsize;
498 SCIP_Bool success;
499
500 /* create sassy graph */
501 sassy::static_graph sassygraph;
502
503 SCIP_CALL( SYMbuildSassyGraphCheck(scip, &sassygraph, G1, G2, &nnodes, &nnodesfromG1, &success) );
504
505 if ( ! success )
506 return FALSE;
507
508 /* compute symmetries */
510 &perms, &nperms, &nmaxperms, &log10groupsize, FALSE, &symcodetime, FALSE) );
511
512 /* since G1 and G2 are connected and disjoint, they are isomorphic iff there is a permutation
513 * mapping a node from G1 to a node of G2
514 */
515 success = FALSE;
516 for (int p = 0; p < nperms && ! success; ++p)
517 {
518 for (int i = 0; i < nnodesfromG1; ++i)
519 {
520 if ( perms[p][i] >= nnodesfromG1 )
521 {
522 success = TRUE;
523 break;
524 }
525 }
526 }
527
528 for (int p = 0; p < nperms; ++p)
529 {
531 }
533
534 return success;
535}
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
static const char nautyname[]
static void nautyterminationhook(graph *g, int *lab, int *ptn, int level, int numcells, int tc, int code, int m, int n)
SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
const char * SYMsymmetryGetName(void)
const char * SYMsymmetryGetAddName(void)
SCIP_Bool SYMcanComputeSymmetry(void)
const char * SYMsymmetryGetDesc(void)
static struct NAUTY_Data nautydata_
static void sassyhook(void *user_param, int n, const int *aut, int nsupp, const int *suppa)
static void nautyterminationhook(graph *g, int *lab, int *ptn, int level, int numcells, int tc, int code, int m, int n)
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, SCIP_Bool canterminateearly)
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:266
#define SCIP_Bool
Definition def.h:91
#define SCIP_Real
Definition def.h:172
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIP_CALL_ABORT(x)
Definition def.h:352
#define SCIP_CALL(x)
Definition def.h:373
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
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition scip_param.c:269
#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
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
public methods for memory management
methods for dealing with symmetry detection graphs
struct SYM_Graph SYM_GRAPH
Definition type_cons.h:68
@ SCIP_VERBLEVEL_MINIMAL
enum SCIP_Retcode SCIP_RETCODE
struct Scip SCIP
Definition type_scip.h:39
enum SYM_Symtype SYM_SYMTYPE
@ SYM_SYMTYPE_SIGNPERM
@ SYM_SYMTYPE_PERM