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-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.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 
93 /** struct for symmetry callback */
94 struct 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}*/
110 static
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:
142  assert( data->symtype == SYM_SYMTYPE_SIGNPERM );
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 
160  if ( SCIPallocBlockMemoryArray(data->scip, &p, permlen) != SCIP_OKAY )
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 /** static variable for holding the name of nauty */
201 static TLS_ATTR char nautyname[20];
202 
203 /** return name of external program used to compute generators */
204 const char* SYMsymmetryGetName(void)
205 {
206  /* 28080+HAVE_TLS -> 2.8.(0)8 */
207 #ifdef NAUTY
208  (void) SCIPsnprintf(nautyname, (int)sizeof(nautyname), "Nauty %d.%d.%d", NAUTYVERSIONID/10000, (NAUTYVERSIONID%10000)/1000, (NAUTYVERSIONID%1000)/10);
209 #else
210  (void) SCIPsnprintf(nautyname, (int)sizeof(nautyname), "Traces %d.%d.%d", NAUTYVERSIONID/10000, (NAUTYVERSIONID%10000)/1000, (NAUTYVERSIONID%1000)/10);
211 #endif
212  return nautyname;
213 }
214 
215 /** return description of external program used to compute generators */
216 const char* SYMsymmetryGetDesc(void)
217 {
218 #ifdef NAUTY
219  return "Computing Graph Automorphism Groups by Brendan D. McKay (users.cecs.anu.edu.au/~bdm/nauty)";
220 #else
221  return "Computing Graph Automorphism Groups by Adolfo Piperno (pallini.di.uniroma1.it)";
222 #endif
223 }
224 
225 #define STR(x) #x
226 #define XSTR(x) STR(x)
227 
228 /** return name of additional external program used for computing symmetries */
229 const char* SYMsymmetryGetAddName(void)
230 {
231  return "sassy " XSTR(SASSY_VERSION_MAJOR) "." XSTR(SASSY_VERSION_MINOR);
232 }
233 
234 /** return description of additional external program used to compute symmetries */
235 const char* SYMsymmetryGetAddDesc(void)
236 {
237  return "Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)";
238 }
239 
240 /** computes autormorphisms of a graph */
241 static
243  SCIP* scip, /**< SCIP pointer */
244  SYM_SYMTYPE symtype, /**< type of symmetries that need to be computed */
245  sassy::static_graph* G, /**< pointer to graph for that automorphisms are computed */
246  int nsymvars, /**< number of variables encoded in graph */
247  int maxgenerators, /**< maximum number of generators to be constructed (=0 if unlimited) */
248  int*** perms, /**< pointer to store generators as (nperms x npermvars) matrix */
249  int* nperms, /**< pointer to store number of permutations */
250  int* nmaxperms, /**< pointer to store maximal number of permutations
251  * (needed for freeing storage) */
252  SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
253  SCIP_Bool restricttovars, /**< whether permutations shall be restricted to variables */
254  SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
255  )
256 {
257  SCIP_Real oldtime;
258 
259  assert( scip != NULL );
260  assert( G != NULL );
261  assert( maxgenerators >= 0 );
262  assert( perms != NULL );
263  assert( nperms != NULL );
264  assert( nmaxperms != NULL );
265  assert( log10groupsize != NULL );
266  assert( symcodetime != NULL );
267 
268  /* init */
269  *nperms = 0;
270  *nmaxperms = 0;
271  *perms = NULL;
272  *log10groupsize = 0;
273  *symcodetime = 0.0;
274 
275  /* init data */
276  struct SYMMETRY_Data data;
277  data.scip = scip;
278  data.symtype = symtype;
279  data.npermvars = nsymvars;
280  data.nperms = 0;
281  data.nmaxperms = 0;
283  data.perms = NULL;
285 
286  oldtime = SCIPgetSolvingTime(scip);
287 
288  /* set up sassy preprocessor */
289  sassy::preprocessor sassy;
290 
291  /* turn off some preprocessing that generates redudant permutations */
292  sassy::configstruct sconfig;
293  sconfig.CONFIG_PREP_DEACT_PROBE = true;
294  sassy.configure(&sconfig);
295 
296  /* lambda function to have access to data and pass it to sassyhook above */
297  sassy::sassy_hook sassyglue = [&](int n, const int* p, int nsupp, const int* suppa) {
298  sassyhook((void*)&data, n, p, nsupp, suppa);
299  };
300 
301  /* call sassy to reduce graph */
302  sassy.reduce(G, &sassyglue);
303 
304  /* first, convert the graph */
305  sparsegraph sg;
306  DYNALLSTAT(int, lab, lab_sz);
307  DYNALLSTAT(int, ptn, ptn_sz);
308 
309 #ifdef NAUTY
310  convert_sassy_to_nauty(G, &sg, &lab, &lab_sz, &ptn, &ptn_sz);
311  statsblk stats;
312  DYNALLSTAT(int, orbits, orbits_sz);
313  DYNALLOC1(int, orbits, orbits_sz, sg.nv, "malloc");
314  DEFAULTOPTIONS_SPARSEGRAPH(options);
315  /* init callback functions for nauty (accumulate the group generators found by nauty) */
316  options.writeautoms = FALSE;
317  options.userautomproc = sassy::preprocessor::nauty_hook;
318  options.defaultptn = FALSE; /* use color classes */
319  *log10groupsize = 0.0;
320  if(sg.nv > 0) {
321  sparsenauty(&sg, lab, ptn, orbits, &options, &stats, NULL);
322  *log10groupsize = (SCIP_Real) stats.grpsize2;
323  }
324 #else
325  convert_sassy_to_traces(&sassygraph, &sg, &lab, &lab_sz, &ptn, &ptn_sz);
326  TracesStats stats;
327  DYNALLSTAT(int, orbits, orbits_sz);
328  DYNALLOC1(int, orbits, orbits_sz, sg.nv, "malloc");
329  DEFAULTOPTIONS_TRACES(options);
330  /* init callback functions for traces (accumulate the group generators found by traces) */
331  options.writeautoms = FALSE;
332  options.userautomproc = sassy::preprocessor::traces_hook;
333  options.defaultptn = FALSE; /* use color classes */
334  if(sg.nv > 0) {
335  Traces(&sg, lab, ptn, orbits, &options, &stats, NULL);
336  }
337 #endif
338 
339  /* clean up */
340  DYNFREE(lab, lab_sz);
341  DYNFREE(ptn, ptn_sz);
342  SG_FREE(sg);
343 
344  *symcodetime = SCIPgetSolvingTime(scip) - oldtime;
345 
346  /* prepare return values */
347  if ( data.nperms > 0 )
348  {
349  *perms = data.perms;
350  *nperms = data.nperms;
351  *nmaxperms = data.nmaxperms;
352  }
353  else
354  {
355  assert( data.perms == NULL );
356  assert( data.nmaxperms == 0 );
357 
358  *perms = NULL;
359  *nperms = 0;
360  *nmaxperms = 0;
361  }
362 
363  return SCIP_OKAY;
364 }
365 
366 /** compute generators of symmetry group */
368  SCIP* scip, /**< SCIP pointer */
369  int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
370  SYM_GRAPH* symgraph, /**< symmetry detection graph */
371  int* nperms, /**< pointer to store number of permutations */
372  int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
373  int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
374  SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
375  SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
376  )
377 {
378  SCIP_Bool success = FALSE;
379 
380  assert( scip != NULL );
381  assert( maxgenerators >= 0 );
382  assert( symgraph != NULL );
383  assert( nperms != NULL );
384  assert( nmaxperms != NULL );
385  assert( perms != NULL );
386  assert( log10groupsize != NULL );
387  assert( symcodetime != NULL );
388 
389  /* init */
390  *nperms = 0;
391  *nmaxperms = 0;
392  *perms = NULL;
393  *log10groupsize = 0;
394  *symcodetime = 0.0;
395 
396  /* create sassy graph */
397  sassy::static_graph sassygraph;
398 
399  SCIP_CALL( SYMbuildSassyGraph(scip, &sassygraph, symgraph, &success) );
400 
401  /* compute symmetries */
402  SCIP_CALL( computeAutomorphisms(scip, SCIPgetSymgraphSymtype(symgraph), &sassygraph, SCIPgetSymgraphNVars(symgraph),
403  maxgenerators, perms, nperms, nmaxperms, log10groupsize, TRUE, symcodetime) );
404 
405  return SCIP_OKAY;
406 }
407 
408 /** returns whether two given graphs are identical */
410  SCIP* scip, /**< SCIP pointer */
411  SYM_SYMTYPE symtype, /**< type of symmetries to be checked */
412  SYM_GRAPH* G1, /**< first graph */
413  SYM_GRAPH* G2 /**< second graph */
414  )
415 {
416  int** perms;
417  int nnodes;
418  int nperms;
419  int nmaxperms;
420  int nnodesfromG1;
421  SCIP_Real symcodetime = 0.0;
422  SCIP_Real log10groupsize;
423  SCIP_Bool success;
424 
425  /* create sassy graph */
426  sassy::static_graph sassygraph;
427 
428  SCIP_CALL( SYMbuildSassyGraphCheck(scip, &sassygraph, G1, G2, &nnodes, &nnodesfromG1, &success) );
429 
430  if ( ! success )
431  return FALSE;
432 
433  /* compute symmetries */
434  SCIP_CALL_ABORT( computeAutomorphisms(scip, SCIPgetSymgraphSymtype(G1), &sassygraph, nnodes, 0,
435  &perms, &nperms, &nmaxperms, &log10groupsize, FALSE, &symcodetime) );
436 
437  /* since G1 and G2 are connected and disjoint, they are isomorphic iff there is a permutation
438  * mapping a node from G1 to a node of G2
439  */
440  success = FALSE;
441  for (int p = 0; p < nperms && ! success; ++p)
442  {
443  for (int i = 0; i < nnodesfromG1; ++i)
444  {
445  if ( perms[p][i] >= nnodesfromG1 )
446  {
447  success = TRUE;
448  break;
449  }
450  }
451  }
452 
453  for (int p = 0; p < nperms; ++p)
454  {
455  SCIPfreeBlockMemoryArray(scip, &perms[p], nnodes);
456  }
457  SCIPfreeBlockMemoryArrayNull(scip, &perms, nmaxperms);
458 
459  return success;
460 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
const char * SYMsymmetryGetAddDesc(void)
#define NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
public methods for memory management
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
methods to build sassy graph for symmetry detection
private functions to work with algebraic expressions
#define FALSE
Definition: def.h:94
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
variable expression handler
#define XSTR(x)
static void sassyhook(void *user_param, int n, const int *aut, int nsupp, const int *suppa)
interface for symmetry computations
methods for dealing with symmetry detection graphs
SCIP_Bool SYMcanComputeSymmetry(void)
power and signed power expression handlers
#define SCIP_CALL(x)
Definition: def.h:380
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
const char * SYMsymmetryGetAddName(void)
#define SCIP_Bool
Definition: def.h:91
constraint handler for nonlinear constraints specified by algebraic expressions
static TLS_ATTR char nautyname[20]
const char * SYMsymmetryGetName(void)
SCIP_RETCODE SYMbuildSassyGraphCheck(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *G1, SYM_GRAPH *G2, int *nnodes, int *nnodesfromG1, SCIP_Bool *success)
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_GRAPH *symgraph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SYMbuildSassyGraph(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *graph, SCIP_Bool *success)
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 * SYMsymmetryGetDesc(void)
#define SCIP_Real
Definition: def.h:173
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
sum expression handler
#define nnodes
Definition: gastrans.c:74
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIP_CALL_ABORT(x)
Definition: def.h:359