Scippy

SCIP

Solving Constraint Integer Programs

compute_symmetry_nauty.c
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_nauty.c
26  * @brief interface for symmetry computations to nauty/traces
27  * @author Marc Pfetsch
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #include "compute_symmetry.h"
33 
34 /* the following determines whether nauty or traces is used: */
35 #define NAUTY
36 
37 /* include nauty/traces */
38 /* turn off warning (just for including nauty/traces) */
39 #pragma GCC diagnostic ignored "-Wunused-variable"
40 #pragma GCC diagnostic ignored "-Wredundant-decls"
41 #pragma GCC diagnostic ignored "-Wpedantic"
42 
43 #ifdef NAUTY
44 #include "nauty/nauty.h"
45 #include "nauty/nausparse.h"
46 #else
47 #include "nauty/traces.h"
48 #endif
49 
50 #pragma GCC diagnostic warning "-Wunused-variable"
51 #pragma GCC diagnostic warning "-Wredundant-decls"
52 #pragma GCC diagnostic warning "-Wpedantic"
53 
54 #include "scip/symmetry_graph.h"
55 #include "scip/expr_var.h"
56 #include "scip/expr_sum.h"
57 #include "scip/expr_pow.h"
58 #include "scip/expr.h"
59 #include "scip/cons_nonlinear.h"
60 #include "scip/cons_linear.h"
61 #include "scip/scip_mem.h"
62 
63 
64 /** struct for nauty callback */
65 struct NAUTY_Data
66 {
67  SCIP* scip; /**< SCIP pointer */
68  SYM_SYMTYPE symtype; /**< type of symmetries that need to be computed */
69  int npermvars; /**< number of variables for permutations */
70  int nperms; /**< number of permutations */
71  int** perms; /**< permutation generators as (nperms x npermvars) matrix */
72  int nmaxperms; /**< maximal number of permutations */
73  int maxgenerators; /**< maximal number of generators to be constructed (= 0 if unlimited) */
74  SCIP_Bool restricttovars; /**< whether permutations shall be restricted to variables */
75 };
76 
77 /* static data for nauty callback */
78 static struct NAUTY_Data data_;
79 
80 /* ------------------- hook functions ------------------- */
81 
82 #ifdef NAUTY
83 
84 /** callback function for nauty */ /*lint -e{715}*/
85 static
86 void nautyhook(
87  int count, /**< ID of this generator */
88  int* p, /**< generator (permutation) that nauty found */
89  int* orbits, /**< orbits generated by the group found so far */
90  int numorbits, /**< number of orbits */
91  int stabvertex, /**< stabilizing node */
92  int n /**< number of nodes in the graph */
93  )
94 { /* lint --e{715} */
95  SCIP_Bool isidentity = TRUE;
96  int permlen;
97  int* pp;
98 
99  assert( p != NULL );
100 
101  /* make sure we do not generate more than maxgenerators many permutations */
103  {
104  /* request a kill from nauty */
105  nauty_kill_request = 1;
106  return;
107  }
108 
109  /* copy first part of automorphism */
110  if ( data_.restricttovars )
111  {
112  if ( data_.symtype == SYM_SYMTYPE_PERM )
113  permlen = data_.npermvars;
114  else
115  permlen = 2 * data_.npermvars;
116  }
117  else
118  permlen = n;
119 
120  /* check whether permutation is identity */
121  for (int j = 0; j < permlen; ++j)
122  {
123  if ( (int) p[j] != j )
124  isidentity = FALSE;
125  }
126 
127  /* don't store identity permutations */
128  if ( isidentity )
129  return;
130 
131  /* check whether we should allocate space for perms */
132  if ( data_.nmaxperms <= 0 )
133  {
134  if ( data_.maxgenerators == 0 )
135  data_.nmaxperms = 100; /* seems to cover many cases */
136  else
138 
140  return;
141  }
142  else if ( data_.nperms >= data_.nmaxperms ) /* check whether we need to resize */
143  {
144  int newsize;
145 
146  newsize = SCIPcalcMemGrowSize(data_.scip, data_.nperms + 1);
147  assert( newsize >= data_.nperms );
148  assert( data_.maxgenerators == 0 );
149 
151  return;
152 
153  data_.nmaxperms = newsize;
154  }
155 
156  if ( SCIPduplicateBlockMemoryArray(data_.scip, &pp, p, permlen) != SCIP_OKAY )
157  return;
158  data_.perms[data_.nperms++] = pp;
159 }
160 
161 #else
162 
163 /** callback function for traces */
164 static
165 void traceshook(
166  int count, /**< number of generator */
167  int* p, /**< generator that traces found */
168  int n /**< number of nodes in the graph */
169  )
170 {
171  SCIP_Bool isidentity = TRUE;
172  int permlen;
173  int* pp;
174  int j;
175 
176  assert( p != NULL );
177 
178  /* make sure we do not generate more than maxgenerators many permutations */
180  {
181  /* request a kill from traces */
182  nauty_kill_request = 1;
183  return;
184  }
185 
186  /* copy first part of automorphism */
187  if ( data_.restricttovars )
188  {
189  if ( data_.symtype == SYM_SYMTYPE_PERM )
190  permlen = data_.npermvars;
191  else
192  permlen = 2 * data_.npermvars;
193  }
194  else
195  permlen = n;
196 
197  /* check whether permutation is identity */
198  for (j = 0; j < permlen; ++j)
199  {
200  if ( (int) p[j] != j )
201  isidentity = FALSE;
202  }
203 
204  /* ignore trivial generators, i.e. generators that only permute the constraints */
205  if ( isidentity )
206  return;
207 
208  /* check whether we should allocate space for perms */
209  if ( data_.nmaxperms <= 0 )
210  {
211  if ( data_.maxgenerators == 0 )
212  data_.nmaxperms = 100; /* seems to cover many cases */
213  else
215 
217  return;
218  }
219  else if ( data_.nperms >= data_.nmaxperms ) /* check whether we need to resize */
220  {
221  int newsize;
222 
223  newsize = SCIPcalcMemGrowSize(data_.scip, data_.nperms + 1);
224  assert( newsize >= data_.nperms );
225  assert( data_.maxgenerators == 0 );
226 
228  return;
229 
230  data_.nmaxperms = newsize;
231  }
232 
233  if ( SCIPduplicateBlockMemoryArray(data_.scip, &pp, p, permlen) != SCIP_OKAY )
234  return;
235  data_.perms[data_.nperms++] = pp;
236 }
237 
238 #endif
239 
240 /** returns whether an edge is considered in grouping process */
241 static
243  SYM_GRAPH* symgraph, /**< symmetry detection graph */
244  int edgeidx, /**< index of edge to be checked */
245  SCIP_Bool groupbycons /**< whether edges are grouped by constraints */
246  )
247 {
248  int first;
249  int second;
250 
251  assert(symgraph != NULL);
252 
253  first = SCIPgetSymgraphEdgeFirst(symgraph, edgeidx);
254  second = SCIPgetSymgraphEdgeSecond(symgraph, edgeidx);
255 
256  /* uncolored edges are not grouped */
257  if ( ! SCIPisSymgraphEdgeColored(symgraph, edgeidx) )
258  return FALSE;
259 
260  /* two variable nodes are connected */
261  if ( first < 0 && second < 0 )
262  return FALSE;
263 
264  if ( ! groupbycons )
265  {
266  /* grouping by variables requires one variable node */
267  if ( first < 0 || second < 0 )
268  return TRUE;
269  }
270  else
271  {
272  /* check whether there is exactly one constraint node in edge */
273  if ( first >= 0 && second >= 0 )
274  {
275  if ( (SCIPgetSymgraphNodeType(symgraph, first) == SYM_NODETYPE_CONS
276  && SCIPgetSymgraphNodeType(symgraph, second) != SYM_NODETYPE_CONS)
277  || (SCIPgetSymgraphNodeType(symgraph, first) != SYM_NODETYPE_CONS
278  && SCIPgetSymgraphNodeType(symgraph, second) == SYM_NODETYPE_CONS) )
279  return TRUE;
280  }
281  else if ( first >= 0 )
282  {
283  if ( SCIPgetSymgraphNodeType(symgraph, first) == SYM_NODETYPE_CONS )
284  return TRUE;
285  }
286  else
287  {
288  if ( SCIPgetSymgraphNodeType(symgraph, second) == SYM_NODETYPE_CONS )
289  return TRUE;
290  }
291  }
292 
293  return FALSE;
294 }
295 
296 /** adds grouped edges all of which have one common endpoint to a graph
297  *
298  * The grouping mechanism works by sorting the edges according to their color. If two
299  * edges have the same color, they share the same intermediate node, which is connected
300  * to the common node and the other endpoints of equivalent edges.
301  */
302 static
304  SCIP* scip, /**< SCIP pointer */
305  sparsegraph* SG, /**< graph to be constructed */
306  int* edgestartpos, /**< initialized array of starting positions of new edges for each node */
307  SCIP_Bool determinesize, /**< whether only the effect of grouping on the graph shall be checked */
308  int* internodeid, /**< (initialized) pointer to store the ID of the next intermediate node */
309  int** degrees, /**< pointer to array of degrees for nodes in G */
310  int* maxdegrees, /**< (initialized) pointer to maximum number of entries degrees can hold */
311  int** colorstostore, /**< pointer to array of colors of graph to be constructed */
312  int* ncolorstostore, /**< (initialized) pointer to maximum number of entries in colorstostore */
313  int* nnodes, /**< (initialized) pointer to store the number of */
314  int* nedges, /**< (initialized) pointer to store the number of */
315  int commonnodeidx, /**< index of common node in G */
316  int* neighbors, /**< neighbors of common node */
317  int* colors, /**< colors of edges to neighbors */
318  int nneighbors, /**< number of neighbors */
319  int* naddednodes, /**< pointer to store number of nodes added to G */
320  int* naddededges /**< pointer to store number of edges added to G */
321  )
322 {
323  int curcolor;
324  int curstart;
325  int e;
326  int f;
327 
328  assert( SG != NULL || determinesize );
329  assert( internodeid != NULL );
330  assert( *internodeid >= 0 );
331  assert( degrees != NULL );
332  assert( maxdegrees != NULL );
333  assert( *maxdegrees > 0 );
334  assert( nnodes != NULL );
335  assert( nedges != NULL );
336  assert( neighbors != NULL );
337  assert( colors != NULL );
338  assert( naddednodes != NULL );
339  assert( naddededges != NULL );
340  assert( commonnodeidx <= *internodeid );
341 
342  *naddednodes = 0;
343  *naddededges = 0;
344 
345  /* sort edges according to color */
346  SCIPsortIntInt(colors, neighbors, nneighbors);
347 
348  /* iterate over groups of identical edges and group them, ignoring the last group */
349  curcolor = colors[0];
350  curstart = 0;
351  for (e = 1; e < nneighbors; ++e)
352  {
353  /* if a new group started, add edges for previous group */
354  if ( colors[e] != curcolor )
355  {
356  if ( determinesize )
357  {
358  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *internodeid + 1) );
359  SCIP_CALL( SCIPensureBlockMemoryArray(scip, colorstostore, ncolorstostore, *internodeid + 1) );
360  (*degrees)[*internodeid] = 1;
361  ++(*degrees)[commonnodeidx];
362  (*colorstostore)[*internodeid] = curcolor;
363 
364  for (f = curstart; f < e; ++f)
365  {
366  assert( neighbors[f] <= *internodeid );
367  ++(*degrees)[*internodeid];
368  ++(*degrees)[neighbors[f]];
369  }
370  }
371  else
372  {
373  SG->e[edgestartpos[commonnodeidx]++] = *internodeid;
374  SG->e[edgestartpos[*internodeid]++] = commonnodeidx;
375 
376  for (f = curstart; f < e; ++f)
377  {
378  SG->e[edgestartpos[neighbors[f]]++] = *internodeid;
379  SG->e[edgestartpos[*internodeid]++] = neighbors[f];
380  }
381  }
382  *naddednodes += 1;
383  *naddededges += e - curstart + 1;
384  ++(*internodeid);
385 
386  curcolor = colors[e];
387  curstart = e;
388  }
389  }
390 
391  /* add edges of last group */
392  if ( determinesize )
393  {
394  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *internodeid + 1) );
395  SCIP_CALL( SCIPensureBlockMemoryArray(scip, colorstostore, ncolorstostore, *internodeid + 1) );
396 
397  (*degrees)[*internodeid] = 1;
398  ++(*degrees)[commonnodeidx];
399  (*colorstostore)[*internodeid] = curcolor;
400 
401  for (f = curstart; f < nneighbors; ++f)
402  {
403  assert( neighbors[f] <= *internodeid );
404  ++(*degrees)[*internodeid];
405  ++(*degrees)[neighbors[f]];
406  }
407  }
408  else
409  {
410  SG->e[edgestartpos[commonnodeidx]++] = *internodeid;
411  SG->e[edgestartpos[*internodeid]++] = commonnodeidx;
412 
413  for (f = curstart; f < nneighbors; ++f)
414  {
415  SG->e[edgestartpos[*internodeid]++] = neighbors[f];
416  SG->e[edgestartpos[neighbors[f]]++] = *internodeid;
417  }
418  }
419  *naddednodes += 1;
420  *naddededges += nneighbors - curstart + 1;
421  ++(*internodeid);
422 
423  return SCIP_OKAY;
424 }
425 
426 /** either creates a graph or determines its size */
427 static
429  SCIP* scip, /**< SCIP instance */
430  SYM_GRAPH* symgraph, /**< symmetry detection graph */
431  SCIP_Bool determinesize, /**< whether only the size of the graph shall be determined */
432  sparsegraph* SG, /**< graph to be constructed */
433  int* nnodes, /**< pointer to store the total number of nodes in graph */
434  int* nedges, /**< pointer to store the total number of edges in graph */
435  int** degrees, /**< pointer to store the degrees of the nodes */
436  int* maxdegrees, /**< pointer to store the maximal size of the degree array */
437  int** colors, /**< pointer to store the colors of the nodes */
438  int* ncolors, /**< pointer to store number of different colors in graph */
439  SCIP_Bool* success /**< pointer to store whether the construction was successful */
440  )
441 { /*lint !e438*/
443  SYM_NODETYPE comparetype;
444  SCIP_Bool groupByConstraints;
445  int* groupfirsts = NULL;
446  int* groupseconds = NULL;
447  int* groupcolors = NULL;
448  int* pos = NULL;
449  int edgebegincnt = 0;
450  int ngroupedges = 0;
451  int nvarnodestoadd;
452  int internodeid;
453  int nsymvars;
454  int nsymedges;
455  int first;
456  int second;
457  int e;
458  int j;
459 
460  assert( scip != NULL );
461  assert( symgraph != NULL );
462  assert( SG != NULL || determinesize );
463  assert( nnodes != NULL );
464  assert( nedges != NULL );
465  assert( degrees != NULL );
466  assert( maxdegrees != NULL );
467  assert( colors != NULL );
468  assert( ncolors != NULL );
469  assert( success != NULL );
470 
471  *success = TRUE;
472 
473  /* collect basic information from symmetry detection graph */
474  nsymvars = SCIPgetSymgraphNVars(symgraph);
475  symtype = SCIPgetSymgraphSymtype(symgraph);
476  switch ( symtype )
477  {
478  case SYM_SYMTYPE_PERM:
479  nvarnodestoadd = nsymvars;
480  break;
481  default:
482  assert( symtype == SYM_SYMTYPE_SIGNPERM );
483  nvarnodestoadd = 2 * nsymvars;
484  } /*lint !e788*/
485 
486  /* possibly find number of nodes in sassy graph */
487  if ( determinesize )
488  {
489  int cnt = 0;
490 
491  /* initialize counters */
492  *nnodes = SCIPgetSymgraphNNodes(symgraph) + nvarnodestoadd;
493  *nedges = 0;
494 
495  /* possibly allocate memory for degrees (will grow dynamically) */
496  *degrees = NULL;
497  *maxdegrees = 0;
498  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *nnodes + 100) );
499  for (j = 0; j < *nnodes; ++j)
500  (*degrees)[j] = 0;
501 
502  /* possibly allocate memory for colors (will grow dynamically) */
503  *colors = NULL;
504  *ncolors = 0;
505  SCIP_CALL( SCIPensureBlockMemoryArray(scip, colors, ncolors, *nnodes + 100) );
506  for (j = 0; j < nvarnodestoadd; ++j)
507  (*colors)[cnt++] = SCIPgetSymgraphVarnodeColor(symgraph, j);
508  for (j = 0; j < SCIPgetSymgraphNNodes(symgraph); ++j)
509  (*colors)[cnt++] = SCIPgetSymgraphNodeColor(symgraph, j);
510  }
511  else
512  {
513  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &pos, *nnodes) );
514 
515  /* add nodes for variables and remaining (axuiliary) nodes in graph */
516  for (j = 0; j < *nnodes; ++j)
517  {
518  SG->d[j] = (*degrees)[j];
519  SG->v[j] = (size_t) (unsigned) edgebegincnt;
520  pos[j] = edgebegincnt;
521  edgebegincnt += (*degrees)[j];
522  }
523  }
524 
525  /* determine grouping depending on the number of rhs vs. variables */
526  groupByConstraints = SCIPgetSymgraphNConsnodes(symgraph) < SCIPgetSymgraphNVars(symgraph);
527 
528  /* allocate arrays to collect edges to be grouped */
529  nsymedges = SCIPgetSymgraphNEdges(symgraph);
530  SCIP_CALL( SCIPallocBufferArray(scip, &groupfirsts, nsymedges) );
531  SCIP_CALL( SCIPallocBufferArray(scip, &groupseconds, nsymedges) );
532  SCIP_CALL( SCIPallocBufferArray(scip, &groupcolors, nsymedges) );
533 
534  /* loop through all edges of the symmetry detection graph and either get degrees of nodes or add edges */
535  internodeid = SCIPgetSymgraphNNodes(symgraph) + nvarnodestoadd;
536  for (e = 0; e < SCIPgetSymgraphNEdges(symgraph); ++e)
537  {
538  first = SCIPgetSymgraphEdgeFirst(symgraph, e);
539  second = SCIPgetSymgraphEdgeSecond(symgraph, e);
540 
541  /* get the first and second node in edge (corrected by variable shift) */
542  if ( first < 0 )
543  first = -first - 1;
544  else
545  first += nvarnodestoadd;
546  if ( second < 0 )
547  second = -second - 1;
548  else
549  second += nvarnodestoadd;
550  assert(first >= 0);
551  assert(second >= 0);
552 
553  /* check whether edge is used for grouping */
554  if ( ! SCIPhasGraphUniqueEdgetype(symgraph) && isEdgeGroupable(symgraph, e, groupByConstraints) )
555  {
556  /* store edge, first becomes the cons or var node */
557  comparetype = groupByConstraints ? SYM_NODETYPE_CONS : SYM_NODETYPE_VAR;
558 
559  if ( SCIPgetSymgraphNodeType(symgraph, SCIPgetSymgraphEdgeFirst(symgraph, e)) == comparetype )
560  {
561  groupfirsts[ngroupedges] = first;
562  groupseconds[ngroupedges] = second;
563  }
564  else
565  {
566  groupfirsts[ngroupedges] = second;
567  groupseconds[ngroupedges] = first;
568  }
569  groupcolors[ngroupedges++] = SCIPgetSymgraphEdgeColor(symgraph, e);
570  }
571  else
572  {
573  /* immediately add edge or increase degrees */
574  assert(0 <= first && first < *nnodes);
575  assert(0 <= second && second < *nnodes);
576 
577  /* possibly split edge if it is colored */
578  if ( ! SCIPhasGraphUniqueEdgetype(symgraph) && SCIPisSymgraphEdgeColored(symgraph, e) )
579  {
580  if ( determinesize )
581  {
582  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, internodeid + 1) );
583  SCIP_CALL( SCIPensureBlockMemoryArray(scip, colors, ncolors, internodeid + 1) );
584  ++(*degrees)[first];
585  ++(*degrees)[second];
586  (*degrees)[internodeid] = 2;
587  ++(*nnodes);
588  *nedges += 2;
589  (*colors)[internodeid] = SCIPgetSymgraphEdgeColor(symgraph, e);
590  ++internodeid;
591  }
592  else
593  {
594  assert( internodeid < *nnodes );
595 
596  /* add (bidirected) edges */
597  SG->e[pos[first]++] = internodeid;
598  SG->e[pos[internodeid]++] = first;
599  SG->e[pos[second]++] = internodeid;
600  SG->e[pos[internodeid]++] = second;
601 
602  assert( first == *nnodes - 1 || pos[first] <= (int) SG->v[first+1] );
603  assert( second == *nnodes - 1 || pos[second] <= (int) SG->v[second+1] );
604  assert( internodeid == *nnodes - 1 || pos[internodeid] <= (int) SG->v[internodeid+1] );
605 
606  ++internodeid;
607  }
608  }
609  else
610  {
611  if ( determinesize )
612  {
613  ++(*degrees)[first];
614  ++(*degrees)[second];
615  ++(*nedges);
616  }
617  else
618  {
619  /* add (bidirected) edge */
620  SG->e[pos[first]++] = second;
621  SG->e[pos[second]++] = first;
622 
623  assert( first == *nnodes - 1 || pos[first] <= (int) SG->v[first+1] );
624  assert( second == *nnodes - 1 || pos[second] <= (int) SG->v[second+1] );
625  }
626  }
627  }
628  }
629 
630  /* possibly add groupable edges */
631  if ( ngroupedges > 0 )
632  {
633  int firstidx = 0;
634  int firstnodeidx;
635  int naddednodes;
636  int naddededges;
637 
638  /* sort edges according to their first nodes */
639  SCIPsortIntIntInt(groupfirsts, groupseconds, groupcolors, ngroupedges);
640  firstnodeidx = groupfirsts[0];
641 
642  for (j = 1; j < ngroupedges; ++j)
643  {
644  /* if a new first node has been found, group the edges of the previous first node; ignoring the last group */
645  if ( groupfirsts[j] != firstnodeidx )
646  {
647  SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, SG, pos, determinesize, &internodeid,
648  degrees, maxdegrees, colors, ncolors, nnodes, nedges, firstnodeidx, &groupseconds[firstidx],
649  &groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );
650 
651  firstidx = j;
652  firstnodeidx = groupfirsts[j];
653 
654  if ( determinesize )
655  {
656  *nnodes += naddednodes;
657  *nedges += naddededges;
658  }
659  }
660  }
661 
662  /* process the last group */
663  SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, SG, pos, determinesize, &internodeid,
664  degrees, maxdegrees, colors, ncolors, nnodes, nedges, firstnodeidx, &groupseconds[firstidx],
665  &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );
666 
667  if ( determinesize )
668  {
669  *nnodes += naddednodes;
670  *nedges += naddededges;
671  }
672  }
673 
674  SCIPfreeBufferArray(scip, &groupcolors);
675  SCIPfreeBufferArray(scip, &groupseconds);
676  SCIPfreeBufferArray(scip, &groupfirsts);
677 
678  /* for signed permutation, also add edges connecting a variable and its negation */
679  switch ( SCIPgetSymgraphSymtype(symgraph) )
680  {
682  if ( determinesize )
683  {
684  for (j = 0; j < nvarnodestoadd; ++j)
685  ++(*degrees)[j];
686  *nedges += nsymvars;
687  }
688  else
689  {
690  for (j = 0; j < nsymvars; ++j)
691  {
692  SG->e[pos[j]++] = j + nsymvars;
693  SG->e[pos[j + nsymvars]++] = j;
694 
695  assert( pos[j] <= (int) SG->v[j+1] );
696  assert( j + nsymvars == *nnodes - 1 || pos[j+nsymvars] <= (int) SG->v[j+nsymvars+1] );
697  }
698  }
699  break;
700  default:
701  assert( SCIPgetSymgraphSymtype(symgraph) == SYM_SYMTYPE_PERM );
702  } /*lint !e788*/
703 
704  if ( determinesize )
705  {
706  SCIPdebugMsg(scip, "#nodes: %d\n", *nnodes);
707  SCIPdebugMsg(scip, "#nodes for variables: %d\n", nvarnodestoadd);
708  SCIPdebugMsg(scip, "#nodes for rhs: %d\n", SCIPgetSymgraphNConsnodes(symgraph));
709  SCIPdebugMsg(scip, "#edges: %d\n", *nedges);
710  }
711  else
712  {
713  SCIPfreeBlockMemoryArray(scip, &pos, *nnodes);
714  }
715 
716  return SCIP_OKAY;
717 }
718 
719 /** either creates a graph for checking symmetries or determines its size
720  *
721  * The input are two graphs and the graph to be constructed consists of copies
722  * of the two input graphs, in which non-variable nodes are colored according
723  * to the colors used in symmetry detection. Each variable gets a unique color.
724  * Finally, a dummy node is introduced that is adjacent with all remaining nodes.
725  */
726 static
728  SCIP* scip, /**< SCIP instance */
729  SYM_GRAPH* graph1, /**< first symmetry detection graph */
730  SYM_GRAPH* graph2, /**< second symmetry detection graph */
731  SCIP_Bool determinesize, /**< whether only the size of the graph shall be determined */
732  sparsegraph* SG, /**< graph to be constructed */
733  int* nnodes, /**< pointer to store the total number of nodes in graph */
734  int* nedges, /**< pointer to store the total number of edges in graph */
735  int** degrees, /**< pointer to store the degrees of the nodes */
736  int* maxdegrees, /**< pointer to store the maximal size of the degree array */
737  int** colors, /**< pointer to store the colors of the nodes */
738  int* ncolors, /**< pointer to store number of different colors in graph */
739  int* nusedvars, /**< pointer to store number of variables used in one graph */
740  int* nnodesfromgraph1, /**< pointer to store number of nodes arising from graph1 (or NULL) */
741  SCIP_Bool* success /**< pointer to store whether the graph could be built */
742  )
743 {
745  SYM_NODETYPE comparetype;
746  SCIP_Bool groupByConstraints;
747  SYM_GRAPH* symgraph;
748  int* nvarused1 = NULL;
749  int* nvarused2 = NULL;
750  int* varlabel = NULL;
751  int* groupfirsts = NULL;
752  int* groupseconds = NULL;
753  int* groupcolors = NULL;
754  int* pos = NULL;
755  int nusdvars = 0;
756  int edgebegincnt = 0;
757  int ngroupedges = 0;
758  int nodeshift;
759  int curnnodes;
760  int nvarnodestoadd;
761  int internodeid;
762  int nsymvars;
763  int nsymedges;
764  int first;
765  int second;
766  int color;
767  int e;
768  int i;
769  int j;
770 
771  assert( scip != NULL );
772  assert( graph1 != NULL );
773  assert( graph2 != NULL );
774  assert( SG != NULL || determinesize );
775  assert( nnodes != NULL );
776  assert( nedges != NULL );
777  assert( degrees != NULL );
778  assert( maxdegrees != NULL );
779  assert( colors != NULL );
780  assert( ncolors != NULL );
781  assert( nusedvars != NULL );
782  assert( ! determinesize || nnodesfromgraph1 != NULL );
783  assert( success != NULL );
784 
785  *success = FALSE;
786  if ( determinesize )
787  {
788  *degrees = NULL;
789  *colors = NULL;
790  *maxdegrees = 0;
791  *ncolors = 0;
792  }
793 
794  /* graphs cannot be symmetric */
795  if ( SCIPgetSymgraphNEdges(graph1) != SCIPgetSymgraphNEdges(graph2)
796  || SCIPgetSymgraphNVars(graph1) != SCIPgetSymgraphNVars(graph2) )
797  return SCIP_OKAY;
798 
799  /* collect basic information from symmetry detection graph */
800  nsymvars = SCIPgetSymgraphNVars(graph1);
801  nsymedges = SCIPgetSymgraphNEdges(graph1);
802  symtype = SCIPgetSymgraphSymtype(graph1);
803  switch ( symtype )
804  {
805  case SYM_SYMTYPE_PERM:
806  nvarnodestoadd = nsymvars;
807  break;
808  default:
809  assert( symtype == SYM_SYMTYPE_SIGNPERM );
810  nvarnodestoadd = 2 * nsymvars;
811  } /*lint !e788*/
812 
813  /* find the variables that are contained in an edge */
814  SCIP_CALL( SCIPallocClearBufferArray(scip, &nvarused1, nvarnodestoadd) );
815  SCIP_CALL( SCIPallocClearBufferArray(scip, &nvarused2, nvarnodestoadd) );
816  SCIP_CALL( SCIPallocBufferArray(scip, &varlabel, nvarnodestoadd) );
817 
818  for (e = 0; e < nsymedges; ++e)
819  {
820  first = SCIPgetSymgraphEdgeFirst(graph1, e);
821  second = SCIPgetSymgraphEdgeSecond(graph1, e);
822  if ( first < 0 )
823  nvarused1[-first - 1] += 1;
824  if ( second < 0 )
825  nvarused1[-second - 1] += 1;
826 
827  first = SCIPgetSymgraphEdgeFirst(graph2, e);
828  second = SCIPgetSymgraphEdgeSecond(graph2, e);
829  if ( first < 0 )
830  nvarused2[-first - 1] += 1;
831  if ( second < 0 )
832  nvarused2[-second - 1] += 1;
833  }
834 
835  for (j = 0; j < nvarnodestoadd; ++j)
836  {
837  /* graphs cannot be identical */
838  if ( nvarused1[j] != nvarused2[j] )
839  {
840  SCIPfreeBufferArray(scip, &varlabel);
841  SCIPfreeBufferArray(scip, &nvarused2);
842  SCIPfreeBufferArray(scip, &nvarused1);
843 
844  return SCIP_OKAY;
845  }
846 
847  /* relabel variables by restricting to variables used in constraint (or their negation) */
848  if ( nvarused1[j] > 0 || nvarused1[j % SCIPgetSymgraphNVars(graph1)] > 0 )
849  varlabel[j] = nusdvars++;
850  else
851  varlabel[j] = -1;
852  }
853 
854  /* possibly find number of nodes in sassy graph and allocate memory for dynamic array */
855  if ( determinesize )
856  {
857  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees,
858  SCIPgetSymgraphNNodes(graph1) + SCIPgetSymgraphNNodes(graph2) + 2 * nusdvars + 100) );
859  SCIP_CALL( SCIPensureBlockMemoryArray(scip, colors, ncolors,
860  SCIPgetSymgraphNNodes(graph1) + SCIPgetSymgraphNNodes(graph2) + 2 * nusdvars + 100) );
861 
862  *nnodes = 0;
863  *nedges = 0;
864  }
865  else
866  {
867  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &pos, *nnodes) );
868 
869  /* add nodes for variables and remaining (axuiliary) nodes in graph */
870  for (j = 0; j < *nnodes; ++j)
871  {
872  SG->d[j] = (*degrees)[j];
873  SG->v[j] = (size_t) (unsigned) edgebegincnt;
874  pos[j] = edgebegincnt;
875  edgebegincnt += (*degrees)[j];
876  }
877  }
878 
879  /* determine grouping depending on the number of rhs vs. variables */
880  groupByConstraints = SCIPgetSymgraphNConsnodes(graph1) < SCIPgetSymgraphNVars(graph1);
881 
882  /* allocate arrays to collect edges to be grouped */
883  SCIP_CALL( SCIPallocBufferArray(scip, &groupfirsts, nsymedges) );
884  SCIP_CALL( SCIPallocBufferArray(scip, &groupseconds, nsymedges) );
885  SCIP_CALL( SCIPallocBufferArray(scip, &groupcolors, nsymedges) );
886 
887  /* collect information or generate graphs, we shift the node indices of the second graph when adding them to G */
888  nodeshift = 0;
889  for (i = 0; i < 2; ++i)
890  {
891  curnnodes = 0;
892  symgraph = i == 0 ? graph1 : graph2;
893  ngroupedges = 0;
894 
895  /* possibly add nodes for variables and remaining nodes, each variable gets a unique color */
896  if ( determinesize )
897  {
898  /* add nodes for variables */
899  for (j = 0; j < nvarnodestoadd; ++j)
900  {
901  if ( varlabel[j] >= 0 )
902  {
903  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *nnodes + 1) );
904  (*degrees)[nodeshift + varlabel[j]] = 0;
905  (*colors)[nodeshift + varlabel[j]] = SCIPgetSymgraphVarnodeColor(symgraph, j);
906  ++(*nnodes);
907  ++curnnodes;
908  }
909  }
910 
911  /* add nodes for remaining nodes of graph */
912  for (j = 0; j < SCIPgetSymgraphNNodes(symgraph); ++j)
913  {
914  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *nnodes + 1) );
915  (*degrees)[nodeshift + nusdvars + j] = 0;
916  (*colors)[nodeshift + nusdvars + j] = SCIPgetSymgraphNodeColor(symgraph, j);
917  ++(*nnodes);
918  ++curnnodes;
919  }
920  }
921  else
922  {
923  /* increase counter of nodes */
924  for (j = 0; j < nvarnodestoadd; ++j)
925  {
926  if ( varlabel[j] >= 0 )
927  ++curnnodes;
928  }
929  curnnodes += SCIPgetSymgraphNNodes(symgraph);
930  }
931 
932  /* loop through all edges of the symmetry detection graph and either get degrees of nodes or add edges */
933  internodeid = nodeshift + curnnodes;
934  for (e = 0; e < nsymedges; ++e)
935  {
936  first = SCIPgetSymgraphEdgeFirst(symgraph, e);
937  second = SCIPgetSymgraphEdgeSecond(symgraph, e);
938 
939  /* get the first and second node in edge (corrected by variable shift) */
940  if ( first < 0 )
941  first = varlabel[-first - 1];
942  else
943  first = nusdvars + first;
944  if ( second < 0 )
945  second = varlabel[-second - 1];
946  else
947  second = nusdvars + second;
948 
949  /* check whether edge is used for grouping */
950  if ( ! SCIPhasGraphUniqueEdgetype(symgraph) && isEdgeGroupable(symgraph, e, groupByConstraints) )
951  {
952  /* store edge, first becomes the cons or var node */
953  comparetype = groupByConstraints ? SYM_NODETYPE_CONS : SYM_NODETYPE_VAR;
954 
955  if ( SCIPgetSymgraphNodeType(symgraph, SCIPgetSymgraphEdgeFirst(symgraph, e)) == comparetype )
956  {
957  groupfirsts[ngroupedges] = nodeshift + first;
958  groupseconds[ngroupedges] = nodeshift + second;
959  }
960  else
961  {
962  groupfirsts[ngroupedges] = nodeshift + second;
963  groupseconds[ngroupedges] = nodeshift + first;
964  }
965  groupcolors[ngroupedges++] = nusdvars + SCIPgetSymgraphEdgeColor(symgraph, e);
966  }
967  else
968  {
969  /* immediately add edge or increase degrees */
970  assert(0 <= first && first < *nnodes);
971  assert(0 <= second && second < *nnodes);
972 
973  /* possibly split edge if it is colored */
974  if ( ! SCIPhasGraphUniqueEdgetype(symgraph) && SCIPisSymgraphEdgeColored(symgraph, e) )
975  {
976  if ( determinesize )
977  {
978  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, nodeshift + internodeid + 1) );
979  SCIP_CALL( SCIPensureBlockMemoryArray(scip, colors, ncolors, nodeshift + internodeid + 1) );
980 
981  ++(*degrees)[nodeshift + first];
982  ++(*degrees)[nodeshift + second];
983  (*degrees)[internodeid] = 2;
984 
985  color = SCIPgetSymgraphEdgeColor(symgraph, e);
986  (*colors)[internodeid] = nusdvars + color;
987 
988  ++(*nnodes);
989  *nedges += 2;
990  }
991  else
992  {
993  assert( internodeid < *nnodes );
994 
995  SG->e[pos[internodeid]++] = nodeshift + first;
996  SG->e[pos[internodeid]++] = nodeshift + second;
997  SG->e[pos[nodeshift + first]++] = internodeid;
998  SG->e[pos[nodeshift + second]++] = internodeid;
999 
1000  assert( internodeid == *nnodes - 1
1001  || pos[internodeid] <= (int) SG->v[internodeid+1] );
1002  assert( nodeshift + first == *nnodes - 1
1003  || pos[nodeshift + first] <= (int) SG->v[nodeshift+first+1] );
1004  assert( nodeshift + second == *nnodes - 1 ||
1005  pos[nodeshift + second] <= (int) SG->v[nodeshift+second+1] );
1006  }
1007  ++internodeid;
1008  ++curnnodes;
1009  }
1010  else
1011  {
1012  if ( determinesize )
1013  {
1014  ++(*degrees)[nodeshift + first];
1015  ++(*degrees)[nodeshift + second];
1016  ++(*nedges);
1017  }
1018  else
1019  {
1020  SG->e[pos[nodeshift + first]++] = nodeshift + second;
1021  SG->e[pos[nodeshift + second]++] = nodeshift + first;
1022 
1023  assert( nodeshift+first == *nnodes - 1 || pos[nodeshift+first] <= (int) SG->v[nodeshift+first+1] );
1024  assert( nodeshift+second == *nnodes - 1 || pos[nodeshift+second] <= (int) SG->v[nodeshift+second+1] );
1025  }
1026  }
1027  }
1028  }
1029 
1030  /* possibly add groupable edges */
1031  if ( ngroupedges > 0 )
1032  {
1033  int firstidx = 0;
1034  int firstnodeidx;
1035  int naddednodes;
1036  int naddededges;
1037 
1038  /* sort edges according to their first nodes */
1039  SCIPsortIntIntInt(groupfirsts, groupseconds, groupcolors, ngroupedges);
1040  firstnodeidx = groupfirsts[0];
1041 
1042  for (j = 1; j < ngroupedges; ++j)
1043  {
1044  /* if a new first node has been found, group the edges of the previous first node; ignoring the last group */
1045  if ( groupfirsts[j] != firstnodeidx )
1046  {
1047  SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, SG, pos, determinesize, &internodeid,
1048  degrees, maxdegrees, colors, ncolors, nnodes, nedges, firstnodeidx,
1049  &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );
1050 
1051  firstidx = j;
1052  firstnodeidx = groupfirsts[j];
1053 
1054  if ( determinesize )
1055  {
1056  *nnodes += naddednodes;
1057  *nedges += naddededges;
1058  }
1059  curnnodes += naddednodes;
1060  }
1061  }
1062 
1063  /* process the last group */
1064  SCIP_CALL( addOrDetermineEffectOfGroupedEdges(scip, SG, pos, determinesize, &internodeid,
1065  degrees, maxdegrees, colors, ncolors, nnodes, nedges, firstnodeidx,
1066  &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );
1067 
1068  if ( determinesize )
1069  {
1070  *nnodes += naddednodes;
1071  *nedges += naddededges;
1072  }
1073  curnnodes += naddednodes;
1074  }
1075 
1076  /* for signed permutation, also add edges connecting a variable and its negation */
1078  {
1079  if ( determinesize )
1080  {
1081  for (j = 0; j < nusdvars; ++j)
1082  ++(*degrees)[nodeshift + j];
1083  (*nedges) += nusdvars / 2;
1084  }
1085  else
1086  {
1087  for (j = 0; j < nusdvars/2; ++j)
1088  {
1089  SG->e[pos[nodeshift+j]++] = nodeshift + j + nusdvars/2;
1090  SG->e[pos[nodeshift + j + nusdvars/2]++] = nodeshift + j;
1091 
1092  assert( pos[nodeshift+j] <= (int) SG->v[nodeshift+j+1] );
1093  assert( nodeshift+j+nusdvars/2 == *nnodes - 1
1094  || pos[nodeshift+j+nusdvars/2] <= (int) SG->v[nodeshift+j+nusdvars/2+1] );
1095  }
1096  }
1097  }
1098  nodeshift = curnnodes;
1099 
1100  /* possibly store number of nodes arising from first graph */
1101  if ( determinesize && i == 0 )
1102  *nnodesfromgraph1 = *nnodes;
1103  }
1104 
1105  /* add dummy node */
1106  if ( determinesize )
1107  {
1108  SCIP_CALL( SCIPensureBlockMemoryArray(scip, degrees, maxdegrees, *nnodes + 1) );
1109  SCIP_CALL( SCIPensureBlockMemoryArray(scip, colors, ncolors, *nnodes + 1) );
1110 
1111  ++(*nnodes);
1112  for (j = 0; j < *nnodes - 1; ++j)
1113  ++(*degrees)[j];
1114  (*degrees)[*nnodes - 1] = *nnodes - 1;
1115  (*nedges) += *nnodes - 1;
1116  (*colors)[*nnodes - 1] = 8;
1117  }
1118  else
1119  {
1120  for (j = 0; j < *nnodes - 1; ++j)
1121  {
1122  SG->e[pos[j]++] = *nnodes - 1;
1123  SG->e[pos[*nnodes-1]++] = j;
1124  }
1125  SCIPfreeBlockMemoryArray(scip, &pos, *nnodes);
1126  }
1127 
1128  SCIPfreeBufferArray(scip, &groupcolors);
1129  SCIPfreeBufferArray(scip, &groupseconds);
1130  SCIPfreeBufferArray(scip, &groupfirsts);
1131 
1132  SCIPfreeBufferArray(scip, &varlabel);
1133  SCIPfreeBufferArray(scip, &nvarused2);
1134  SCIPfreeBufferArray(scip, &nvarused1);
1135 
1136  *success = TRUE;
1137  if ( determinesize )
1138  *nusedvars = nusdvars;
1139 
1140  return SCIP_OKAY;
1141 }
1142 
1143 /** return whether symmetry can be computed */
1145 {
1146  return TRUE;
1147 }
1148 
1149 /** static variable for holding the name of nauty */
1150 static TLS_ATTR char nautyname[20];
1151 
1152 /** return name of external program used to compute generators */
1153 const char* SYMsymmetryGetName(void)
1154 {
1155  /* 28080+HAVE_TLS -> 2.8.(0)8 */
1156 #ifdef NAUTY
1157  (void) SCIPsnprintf(nautyname, (int)sizeof(nautyname), "Nauty %d.%d.%d", NAUTYVERSIONID/10000, (NAUTYVERSIONID%10000)/1000, (NAUTYVERSIONID%1000)/10);
1158 #else
1159  (void) SCIPsnprintf(nautyname, (int)sizeof(nautyname), "Traces %d.%d.%d", NAUTYVERSIONID/10000, (NAUTYVERSIONID%10000)/1000, (NAUTYVERSIONID%1000)/10);
1160 #endif
1161  return nautyname;
1162 }
1163 
1164 /** return description of external program used to compute generators */
1165 const char* SYMsymmetryGetDesc(void)
1166 {
1167 #ifdef NAUTY
1168  return "Computing Graph Automorphism Groups by Brendan D. McKay (https://users.cecs.anu.edu.au/~bdm/nauty/)";
1169 #else
1170  return "Computing Graph Automorphism Groups by Adolfo Piperno (https://pallini.di.uniroma1.it/)";
1171 #endif
1172 }
1173 
1174 /** return name of additional external program used for computing symmetries */
1175 const char* SYMsymmetryGetAddName(void)
1176 {
1177  return NULL;
1178 }
1179 
1180 /** return description of additional external program used to compute symmetries */
1181 const char* SYMsymmetryGetAddDesc(void)
1182 {
1183  return NULL;
1184 }
1185 
1186 /** compute generators of symmetry group */
1188  SCIP* scip, /**< SCIP pointer */
1189  int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
1190  SYM_GRAPH* symgraph, /**< symmetry detection graph */
1191  int* nperms, /**< pointer to store number of permutations */
1192  int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
1193  int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
1194  SCIP_Real* log10groupsize, /**< pointer to store size of group */
1195  SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
1196  )
1197 {
1198  SCIP_Real oldtime;
1199  int nnodes;
1200  int nedges;
1201  int* degrees;
1202  int maxdegrees;
1203  int* colors;
1204  int ncolors;
1205  SCIP_Bool success;
1206  int v;
1207 
1208  /* nauty data structures */
1209  sparsegraph SG;
1210  int* lab;
1211  int* ptn;
1212  int* orbits;
1213 
1214 #ifdef NAUTY
1215  DEFAULTOPTIONS_SPARSEGRAPH(options);
1216  statsblk stats;
1217 #else
1218  static DEFAULTOPTIONS_TRACES(options);
1219  TracesStats stats;
1220 #endif
1221 
1222  /* init */
1223  *nperms = 0;
1224  *nmaxperms = 0;
1225  *perms = NULL;
1226  *log10groupsize = 0;
1227  *symcodetime = 0.0;
1228 
1229  /* init options */
1230 #ifdef NAUTY
1231  /* init callback functions for nauty (accumulate the group generators found by nauty) */
1232  options.writeautoms = FALSE;
1233  options.userautomproc = nautyhook;
1234  options.defaultptn = FALSE; /* use color classes */
1235 #else
1236  /* init callback functions for traces (accumulate the group generators found by traces) */
1237  options.writeautoms = FALSE;
1238  options.userautomproc = traceshook;
1239  options.defaultptn = FALSE; /* use color classes */
1240 #endif
1241 
1242  oldtime = SCIPgetSolvingTime(scip);
1243 
1244  /* determine the number of nodes and edges */
1245  SCIP_CALL( createOrDetermineSizeGraph(scip, symgraph, TRUE, NULL, &nnodes, &nedges,
1246  &degrees, &maxdegrees, &colors, &ncolors, &success) );
1247 
1248  if ( ! success )
1249  {
1251  "Stopped symmetry computation: Symmetry graph would become too large.\n");
1252  return SCIP_OKAY;
1253  }
1254 
1255  /* init graph */
1256  SG_INIT(SG);
1257 
1258  SG_ALLOC(SG, (size_t) nnodes, 2 * (size_t)(unsigned) nedges, "malloc"); /*lint !e647*//*lint !e774*//*lint !e571*/
1259 
1260  SG.nv = nnodes; /* number of nodes */
1261  SG.nde = (size_t) (unsigned) (2 * nedges); /* number of directed edges */
1262 
1263  /* add the nodes for linear and nonlinear constraints to the graph */
1264  SCIP_CALL( createOrDetermineSizeGraph(scip, symgraph, FALSE, &SG, &nnodes, &nedges,
1265  &degrees, &maxdegrees, &colors, &ncolors, &success) );
1266 
1267  SCIPfreeBlockMemoryArray(scip, &degrees, maxdegrees);
1268 
1269  /* memory allocation for nauty/traces */
1270  SCIP_CALL( SCIPallocBufferArray(scip, &lab, nnodes) );
1271  SCIP_CALL( SCIPallocBufferArray(scip, &ptn, nnodes) );
1272  SCIP_CALL( SCIPallocBufferArray(scip, &orbits, nnodes) );
1273 
1274  /* fill in array with colors for variables */
1275  for (v = 0; v < nnodes; ++v)
1276  lab[v] = v;
1277 
1278  /* sort nodes according to colors */
1279  SCIPsortIntInt(colors, lab, nnodes);
1280 
1281  /* set up ptn marking new colors */
1282  for (v = 0; v < nnodes; ++v)
1283  {
1284  if ( v < nnodes-1 && colors[v] == colors[v+1] )
1285  ptn[v] = 1; /* color class does not end */
1286  else
1287  ptn[v] = 0; /* color class ends */
1288  }
1289 
1290  SCIPdebugMsg(scip, "Symmetry detection graph has %d nodes.\n", nnodes);
1291 
1292  data_.scip = scip;
1293  data_.npermvars = SCIPgetSymgraphNVars(symgraph);
1294  data_.nperms = 0;
1295  data_.nmaxperms = 0;
1297  data_.perms = NULL;
1298  data_.symtype = SCIPgetSymgraphSymtype(symgraph);
1300 
1301  /* call nauty/traces */
1302 #ifdef NAUTY
1303  sparsenauty(&SG, lab, ptn, orbits, &options, &stats, NULL);
1304 #else
1305  Traces(&SG, lab, ptn, orbits, &options, &stats, NULL);
1306 #endif
1307  *symcodetime = SCIPgetSolvingTime(scip) - oldtime;
1308 
1309  SCIPfreeBufferArray(scip, &orbits);
1310  SCIPfreeBufferArray(scip, &ptn);
1311  SCIPfreeBufferArray(scip, &lab);
1312 
1313  SCIPfreeBlockMemoryArray(scip, &colors, ncolors);
1314 
1315  SG_FREE(SG); /*lint !e774*/
1316 
1317  /* prepare return values */
1318  if ( data_.nperms > 0 )
1319  {
1320  *perms = data_.perms;
1321  *nperms = data_.nperms;
1322  *nmaxperms = data_.nmaxperms;
1323  }
1324  else
1325  {
1326  assert( data_.perms == NULL );
1327  assert( data_.nmaxperms == 0 );
1328 
1329  *perms = NULL;
1330  *nperms = 0;
1331  *nmaxperms = 0;
1332  }
1333 
1334  /* determine log10 of symmetry group size */
1335  *log10groupsize = (SCIP_Real) stats.grpsize2;
1336 
1337  return SCIP_OKAY;
1338 }
1339 
1340 /** returns whether two given graphs are identical */
1342  SCIP* scip, /**< SCIP pointer */
1343  SYM_SYMTYPE symtype, /**< type of symmetries to be checked */
1344  SYM_GRAPH* G1, /**< first graph */
1345  SYM_GRAPH* G2 /**< second graph */
1346  )
1347 {
1348  int nnodes;
1349  int nedges;
1350  int* degrees;
1351  int maxdegrees;
1352  int* colors;
1353  int ncolors;
1354  int nusedvars;
1355  SCIP_Bool success;
1356  int v;
1357  int nnodesfromG1;
1358 
1359  assert( scip != NULL );
1360  assert( G1 != NULL );
1361  assert( G2 != NULL );
1362 
1363  /* some simple checks */
1364  if ( G1->nnodes != G2->nnodes || G1->nopnodes != G2->nopnodes || G1->nvalnodes != G2->nvalnodes
1365  || G1->nconsnodes != G2->nconsnodes || G1->nedges != G2->nedges )
1366  return FALSE;
1367 
1368  SCIP_CALL_ABORT( createOrDetermineSizeGraphCheck(scip, G1, G2, TRUE, NULL, &nnodes, &nedges, &degrees, &maxdegrees,
1369  &colors, &ncolors, &nusedvars, &nnodesfromG1, &success) );
1370 
1371  if ( ! success )
1372  {
1373  SCIPfreeBlockMemoryArrayNull(scip, &degrees, maxdegrees);
1374  SCIPfreeBlockMemoryArrayNull(scip, &colors, ncolors);
1375 
1376  return FALSE;
1377  }
1378 
1379  /* nauty data structures */
1380  sparsegraph SG;
1381  int* lab;
1382  int* ptn;
1383  int* orbits;
1384 
1385 #ifdef NAUTY
1386  DEFAULTOPTIONS_SPARSEGRAPH(options);
1387  statsblk stats;
1388 #else
1389  static DEFAULTOPTIONS_TRACES(options);
1390  TracesStats stats;
1391 #endif
1392 
1393  /* init options */
1394 #ifdef NAUTY
1395  /* init callback functions for nauty (accumulate the group generators found by nauty) */
1396  options.writeautoms = FALSE;
1397  options.userautomproc = nautyhook;
1398  options.defaultptn = FALSE; /* use color classes */
1399 #else
1400  /* init callback functions for traces (accumulate the group generators found by traces) */
1401  options.writeautoms = FALSE;
1402  options.userautomproc = traceshook;
1403  options.defaultptn = FALSE; /* use color classes */
1404 #endif
1405 
1406  /* init graph */
1407  SG_INIT(SG);
1408 
1409  SG_ALLOC(SG, (size_t) nnodes, 2 * (size_t)(unsigned) nedges, "malloc"); /*lint !e647*//*lint !e774*//*lint !e571*/
1410 
1411  SG.nv = nnodes; /* number of nodes */
1412  SG.nde = (size_t) (unsigned) (2 * nedges); /* number of directed edges */
1413 
1414  /* add the nodes for linear and nonlinear constraints to the graph */
1415  SCIP_CALL_ABORT( createOrDetermineSizeGraphCheck(scip, G1, G2, FALSE, &SG, &nnodes, &nedges, &degrees, &maxdegrees,
1416  &colors, &ncolors, &nusedvars, NULL, &success) );
1417  assert( success );
1418 
1419  SCIPfreeBlockMemoryArray(scip, &degrees, maxdegrees);
1420 
1421 #ifdef SCIP_DISABLED_CODE
1422  /* print information about sparsegraph */
1423  SCIPinfoMessage(scip, NULL, "number of nodes: %d\n", SG.nv);
1424  SCIPinfoMessage(scip, NULL, "number of (directed) edges: %lu\n", SG.nde);
1425  SCIPinfoMessage(scip, NULL, "degrees\n");
1426  for (v = 0; v < SG.nv; ++v)
1427  {
1428  SCIPinfoMessage(scip, NULL, "node %d: %d\n", v, SG.d[v]);
1429  }
1430  SCIPinfoMessage(scip, NULL, "colors\n");
1431  for (v = 0; v < SG.nv; ++v)
1432  {
1433  SCIPinfoMessage(scip, NULL, "node %d: %d\n", v, colors[v]);
1434  }
1435  SCIPinfoMessage(scip, NULL, "edges\n");
1436  for (v = 0; v < SG.nv; ++v)
1437  {
1438  for (int w = 0; w < SG.d[v]; ++w)
1439  {
1440  SCIPinfoMessage(scip, NULL, "(%d,%d)\n", v, SG.e[SG.v[v] + w]);
1441  }
1442  }
1443 #endif
1444 
1445  /* memory allocation for nauty/traces */
1446  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &lab, nnodes) );
1447  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &ptn, nnodes) );
1448  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &orbits, nnodes) );
1449 
1450  /* fill in array with colors for variables */
1451  for (v = 0; v < nnodes; ++v)
1452  lab[v] = v;
1453 
1454  /* sort nodes according to colors */
1455  SCIPsortIntInt(colors, lab, nnodes);
1456 
1457  /* set up ptn marking new colors */
1458  for (v = 0; v < nnodes; ++v)
1459  {
1460  if ( v < nnodes-1 && colors[v] == colors[v+1] )
1461  ptn[v] = 1; /* color class does not end */
1462  else
1463  ptn[v] = 0; /* color class ends */
1464  }
1465 
1466 #ifdef SCIP_DISABLED_CODE
1467  /* print further information about sparsegraph */
1468  SCIPinfoMessage(scip, NULL, "lab (and ptn):\n");
1469  for (v = 0; v < SG.nv; ++v)
1470  {
1471  SCIPinfoMessage(scip, NULL, "%d (%d)\n", lab[v], ptn[v]);
1472  }
1473 #endif
1474 
1475  /* compute automorphisms */
1476  data_.scip = scip;
1478  data_.nperms = 0;
1479  data_.nmaxperms = 0;
1480  data_.maxgenerators = 0;
1481  data_.perms = NULL;
1482  data_.symtype = symtype;
1484 
1485  /* call nauty/traces */
1486 #ifdef NAUTY
1487  sparsenauty(&SG, lab, ptn, orbits, &options, &stats, NULL);
1488 #else
1489  Traces(&SG, lab, ptn, orbits, &options, &stats, NULL);
1490 #endif
1491 
1492  SCIPfreeBufferArray(scip, &orbits);
1493  SCIPfreeBufferArray(scip, &ptn);
1494  SCIPfreeBufferArray(scip, &lab);
1495 
1496  SCIPfreeBlockMemoryArray(scip, &colors, ncolors);
1497 
1498  SG_FREE(SG); /*lint !e774*/
1499 
1500  /* G1 and G2 cannot be isomorphic */
1501  if ( data_.nperms == 0 )
1502  return FALSE;
1503 
1504  success = FALSE;
1505  for (int p = 0; p < data_.nperms; ++p)
1506  {
1507  for (int i = 0; i < nnodesfromG1; ++i)
1508  {
1509  if ( data_.perms[p][i] >= nnodesfromG1 )
1510  {
1511  success = TRUE;
1512  break;
1513  }
1514  }
1515  }
1516 
1517  /* free memory */
1518  for (int p = 0; p < data_.nperms; ++p)
1519  {
1520  SCIPfreeBlockMemoryArray(scip, &data_.perms[p], nnodes);
1521  }
1523 
1524  SG_FREE(SG); /*lint !e774*/
1525 
1526  return success;
1527 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
static SCIP_RETCODE addOrDetermineEffectOfGroupedEdges(SCIP *scip, sparsegraph *SG, int *edgestartpos, SCIP_Bool determinesize, int *internodeid, int **degrees, int *maxdegrees, int **colorstostore, int *ncolorstostore, int *nnodes, int *nedges, int commonnodeidx, int *neighbors, int *colors, int nneighbors, int *naddednodes, int *naddededges)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
#define NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_Bool SYMcanComputeSymmetry(void)
public methods for memory management
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
int SCIPgetSymgraphNodeColor(SYM_GRAPH *graph, int nodeidx)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
void SCIPsortIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)
private functions to work with algebraic expressions
#define FALSE
Definition: def.h:94
int SCIPgetSymgraphNEdges(SYM_GRAPH *graph)
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
SCIP_Bool SCIPhasGraphUniqueEdgetype(SYM_GRAPH *graph)
const char * SYMsymmetryGetAddName(void)
static struct NAUTY_Data data_
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
static void nautyhook(int count, int *p, int *orbits, int numorbits, int stabvertex, int n)
variable expression handler
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
interface for symmetry computations
SCIP_VAR * w
Definition: circlepacking.c:67
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
methods for dealing with symmetry detection graphs
int SCIPgetSymgraphEdgeFirst(SYM_GRAPH *graph, int edgeidx)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
static SCIP_Bool isEdgeGroupable(SYM_GRAPH *symgraph, int edgeidx, SCIP_Bool groupbycons)
const char * SYMsymmetryGetAddDesc(void)
SCIP_Bool SCIPisSymgraphEdgeColored(SYM_GRAPH *graph, int edgeidx)
power and signed power expression handlers
#define SCIP_CALL(x)
Definition: def.h:380
static SCIP_RETCODE createOrDetermineSizeGraph(SCIP *scip, SYM_GRAPH *symgraph, SCIP_Bool determinesize, sparsegraph *SG, int *nnodes, int *nedges, int **degrees, int *maxdegrees, int **colors, int *ncolors, SCIP_Bool *success)
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition: scip_mem.h:107
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
static SCIP_RETCODE createOrDetermineSizeGraphCheck(SCIP *scip, SYM_GRAPH *graph1, SYM_GRAPH *graph2, SCIP_Bool determinesize, sparsegraph *SG, int *nnodes, int *nedges, int **degrees, int *maxdegrees, int **colors, int *ncolors, int *nusedvars, int *nnodesfromgraph1, SCIP_Bool *success)
const char * SYMsymmetryGetName(void)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIP_Bool
Definition: def.h:91
const char * SYMsymmetryGetDesc(void)
constraint handler for nonlinear constraints specified by algebraic expressions
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
Constraint handler for linear constraints in their most general form, .
int SCIPgetSymgraphEdgeColor(SYM_GRAPH *graph, int edgeidx)
SCIP_Bool restricttovars
int SCIPgetSymgraphNConsnodes(SYM_GRAPH *graph)
#define SCIP_Real
Definition: def.h:173
SYM_NODETYPE SCIPgetSymgraphNodeType(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
SYM_SYMTYPE symtype
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
SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
enum SYM_Nodetype SYM_NODETYPE
Definition: type_symmetry.h:74
int SCIPgetSymgraphVarnodeColor(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphNNodes(SYM_GRAPH *graph)
int SCIPgetSymgraphEdgeSecond(SYM_GRAPH *graph, int edgeidx)
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_GRAPH *symgraph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
static TLS_ATTR char nautyname[20]