Scippy

SCIP

Solving Constraint Integer Programs

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