Scippy

SCIP

Solving Constraint Integer Programs

compute_symmetry_bliss.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_bliss.cpp
26  * @brief interface for symmetry computations to bliss
27  * @author Marc Pfetsch
28  * @author Thomas Rehn
29  * @author Fabian Wegscheider
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include "compute_symmetry.h"
35 
36 /* include bliss graph */
37 #include <bliss/defs.hh>
38 #include <bliss/graph.hh>
39 
40 #include <string.h>
41 #include <vector>
42 #include <list>
43 #include <math.h>
44 
45 #include "scip/expr_var.h"
46 #include "scip/expr_sum.h"
47 #include "scip/expr_pow.h"
48 #include "scip/expr.h"
49 #include "scip/cons_nonlinear.h"
50 #include "scip/cons_linear.h"
51 #include "scip/symmetry.h"
52 #include "scip/symmetry_graph.h"
53 
54 using std::vector;
55 
56 
57 /** struct for bliss callback */
58 struct BLISS_Data
59 {
60  SCIP* scip; /**< SCIP pointer */
61  SYM_SYMTYPE symtype; /**< type of symmetries that need to be computed */
62  int npermvars; /**< number of variables for permutations */
63  int nperms; /**< number of permutations */
64  int** perms; /**< permutation generators as (nperms x npermvars) matrix */
65  int nmaxperms; /**< maximal number of permutations */
66  int maxgenerators; /**< maximal number of generators constructed (= 0 if unlimited) */
67  SCIP_Bool restricttovars; /**< whether permutations shall be restricted to variables */
68 };
69 
70 /** callback function for bliss */
71 static
72 void blisshook(
73  void* user_param, /**< parameter supplied at call to bliss */
74  unsigned int n, /**< size of aut vector */
75  const unsigned int* aut /**< automorphism */
76  )
77 {
78  assert( aut != NULL );
79  assert( user_param != NULL );
80 
81  BLISS_Data* data = static_cast<BLISS_Data*>(user_param);
82  assert( data->scip != NULL );
83  assert( data->maxgenerators >= 0);
84 
85  /* make sure we do not generate more that maxgenerators many permutations, if the limit in bliss is not available */
86  if ( data->maxgenerators != 0 && data->nperms >= data->maxgenerators )
87  return;
88 
89  /* copy first part of automorphism */
90  bool isIdentity = true;
91  int* p = 0;
92  int permlen;
93  if ( data->restricttovars )
94  {
95  if ( data->symtype == SYM_SYMTYPE_PERM )
96  permlen = data->npermvars;
97  else
98  permlen = 2 * data->npermvars;
99  }
100  else
101  permlen = n;
102 
103  /* check whether permutation is identity */
104  for (int j = 0; j < permlen; ++j)
105  {
106  if ( (int) aut[j] != j )
107  isIdentity = false;
108  }
109 
110  /* don't store identity permutations */
111  if ( isIdentity )
112  return;
113 
114  if ( SCIPallocBlockMemoryArray(data->scip, &p, permlen) != SCIP_OKAY )
115  return;
116 
117  /* store symmetry */
118  for (int j = 0; j < permlen; ++j)
119  p[j] = (int) aut[j];
120 
121  /* check whether we should allocate space for perms */
122  if ( data->nmaxperms <= 0 )
123  {
124  if ( data->maxgenerators == 0 )
125  data->nmaxperms = 100; /* seems to cover many cases */
126  else
127  data->nmaxperms = data->maxgenerators;
128 
129  if ( SCIPallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms) != SCIP_OKAY )
130  return;
131  }
132  else if ( data->nperms >= data->nmaxperms ) /* check whether we need to resize */
133  {
134  int newsize = SCIPcalcMemGrowSize(data->scip, data->nperms + 1);
135  assert( newsize >= data->nperms );
136  assert( data->maxgenerators == 0 );
137 
138  if ( SCIPreallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms, newsize) != SCIP_OKAY )
139  return;
140 
141  data->nmaxperms = newsize;
142  }
143 
144  data->perms[data->nperms++] = p;
145 }
146 
147 /** return whether symmetry can be computed */
149 {
150  return TRUE;
151 }
152 
153 /** return name of external program used to compute generators */
154 const char* SYMsymmetryGetName(void)
155 {
156 #ifdef BLISS_PATCH_PRESENT
157  return "bliss " BLISS_VERSION "p";
158 #else
159  return "bliss " BLISS_VERSION;
160 #endif
161 }
162 
163 /** return description of external program used to compute generators */
164 const char* SYMsymmetryGetDesc(void)
165 {
166  return "Computing Graph Automorphism Groups by T. Junttila and P. Kaski (users.aalto.fi/~tjunttil/bliss)";
167 }
168 
169 /** return name of additional external program used for computing symmetries */
170 const char* SYMsymmetryGetAddName(void)
171 {
172  return NULL;
173 }
174 
175 /** return description of additional external program used to compute symmetries */
176 const char* SYMsymmetryGetAddDesc(void)
177 {
178  return NULL;
179 }
180 
181 /** returns whether an edge is considered in grouping process */
183  SYM_GRAPH* graph, /**< symmetry detection graph */
184  int edgeidx, /**< index of edge to be checked */
185  SCIP_Bool groupbycons /**< whether edges are grouped by constraints */
186  )
187 {
188  assert(graph != NULL);
189 
190  int first = SCIPgetSymgraphEdgeFirst(graph, edgeidx);
191  int second = SCIPgetSymgraphEdgeSecond(graph, edgeidx);
192 
193  /* uncolored edges are not grouped */
194  if ( ! SCIPisSymgraphEdgeColored(graph, edgeidx) )
195  return FALSE;
196 
197  /* two variable nodes are connected */
198  if ( first < 0 && second < 0 )
199  return FALSE;
200 
201  if ( ! groupbycons )
202  {
203  /* grouping by variables requires one variable node */
204  if ( first < 0 || second < 0 )
205  return TRUE;
206  }
207  else
208  {
209  /* check whether there is exactly one constraint node in edge */
210  if ( first >= 0 && second >= 0 )
211  {
212  if ( (SCIPgetSymgraphNodeType(graph, first) == SYM_NODETYPE_CONS
213  && SCIPgetSymgraphNodeType(graph, second) != SYM_NODETYPE_CONS)
214  || (SCIPgetSymgraphNodeType(graph, first) != SYM_NODETYPE_CONS
215  && SCIPgetSymgraphNodeType(graph, second) == SYM_NODETYPE_CONS) )
216  return TRUE;
217  }
218  else if ( first >= 0 )
219  {
220  if ( SCIPgetSymgraphNodeType(graph, first) == SYM_NODETYPE_CONS )
221  return TRUE;
222  }
223  else
224  {
225  if ( SCIPgetSymgraphNodeType(graph, second) == SYM_NODETYPE_CONS )
226  return TRUE;
227  }
228  }
229 
230  return FALSE;
231 }
232 
233 /** adds grouped edges all of which have one common endpoint to a graph
234  *
235  * The grouping mechanism works by sorting the edges according to their color. If two
236  * edges have the same color, they share the same intermediate node, which is connected
237  * to the common node and the other endpoints of equivalent edges.
238  */
239 static
241  bliss::Graph* G, /**< pointer to graph which gets extended */
242  int commonnodeidx, /**< index of common node in G */
243  int* neighbors, /**< neighbors of common node */
244  int* colors, /**< colors of edges to neighbors */
245  int nneighbors, /**< number of neighbors */
246  int* naddednodes, /**< pointer to store number of nodes added to G */
247  int* naddededges /**< pointer to store number of edges added to G */
248  )
249 {
250  assert( G != NULL );
251  assert( neighbors != NULL );
252  assert( colors != NULL );
253  assert( naddednodes != NULL );
254  assert( naddededges != NULL );
255 
256  *naddednodes = 0;
257  *naddededges = 0;
258 
259  /* sort edges according to color */
260  SCIPsortIntInt(colors, neighbors, nneighbors);
261 
262  /* iterate over groups of identical edges and group them, ignoring the last group */
263  int curcolor = colors[0];
264  int curstart = 0;
265  for (int e = 1; e < nneighbors; ++e)
266  {
267  /* if a new group started, add edges for previous group */
268  if ( colors[e] != curcolor )
269  {
270  int internode = (*G).add_vertex(curcolor);
271  (*G).add_edge(commonnodeidx, internode);
272  *naddednodes += 1;
273 
274  for (int f = curstart; f < e; ++f)
275  (*G).add_edge(internode, neighbors[f]);
276  *naddededges += e - curstart + 1;
277 
278  curcolor = colors[e];
279  curstart = e;
280  }
281  }
282 
283  /* add edges of last group */
284  int internode = (*G).add_vertex(curcolor);
285  (*G).add_edge(commonnodeidx, internode);
286  *naddednodes += 1;
287 
288  for (int f = curstart; f < nneighbors; ++f)
289  (*G).add_edge(internode, neighbors[f]);
290  *naddededges += nneighbors - curstart + 1;
291 
292  return SCIP_OKAY;
293 }
294 
295 /** computes autormorphisms of a graph */
296 static
298  SCIP* scip, /**< SCIP pointer */
299  SYM_SYMTYPE symtype, /**< type of symmetries that need to be computed */
300  bliss::Graph* G, /**< pointer to graph for that automorphisms are computed */
301  int nsymvars, /**< number of variables encoded in graph */
302  int maxgenerators, /**< maximum number of generators to be constructed (=0 if unlimited) */
303  int*** perms, /**< pointer to store generators as (nperms x npermvars) matrix */
304  int* nperms, /**< pointer to store number of permutations */
305  int* nmaxperms, /**< pointer to store maximal number of permutations
306  * (needed for freeing storage) */
307  SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
308  SCIP_Bool restricttovars, /**< whether permutations shall be restricted to variables */
309  SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
310  )
311 {
312  SCIP_Real oldtime;
313 
314  assert( scip != NULL );
315  assert( G != NULL );
316  assert( perms != NULL );
317  assert( nperms != NULL );
318  assert( nmaxperms != NULL );
319  assert( log10groupsize != NULL );
320  assert( maxgenerators >= 0 );
321  assert( symcodetime != NULL );
322 
323  /* init */
324  *nperms = 0;
325  *nmaxperms = 0;
326  *perms = NULL;
327  *log10groupsize = 0;
328  *symcodetime = 0.0;
329 
330  bliss::Stats stats;
331  BLISS_Data data;
332  data.scip = scip;
333  data.symtype = symtype;
334  data.npermvars = nsymvars;
335  data.nperms = 0;
336  data.nmaxperms = 0;
338  data.perms = NULL;
340 
341  /* Prefer splitting partition cells corresponding to variables over those corresponding
342  * to inequalities. This is because we are only interested in the action
343  * of the automorphism group on the variables, and we need a base for this action */
344  G->set_splitting_heuristic(bliss::Graph::shs_f);
345  /* disable component recursion as advised by Tommi Junttila from bliss */
346  G->set_component_recursion(false);
347 
348  oldtime = SCIPgetSolvingTime(scip);
349 #if BLISS_VERSION_MAJOR >= 1 || BLISS_VERSION_MINOR >= 76
350  /* lambda function to have access to data and pass it to the blisshook above */
351  auto reportglue = [&](unsigned int n, const unsigned int* aut) {
352  blisshook((void*)&data, n, aut);
353  };
354 
355  /* lambda function to have access to data and terminate the search if maxgenerators are reached */
356  auto term = [&]() {
357  return (maxgenerators != 0 && data.nperms >= maxgenerators); /* check the number of generators that we have created so far */
358  };
359 
360  /* start search */
361  G->find_automorphisms(stats, reportglue, term);
362 #else
363 
364  /* Older bliss versions do not allow to terminate with a limit on the number of generators unless patched. */
365 #ifdef BLISS_PATCH_PRESENT
366  /* If patch is present, do not use a node limit, but set generator limit. This approach is not very accurate, since
367  * it limits the generators considered in bliss and not the ones that we generate (the ones that work on the variable
368  * set). */
369  G->set_search_limits(0, (unsigned) maxgenerators);
370 #endif
371 
372  /* start search */
373  G->find_automorphisms(stats, blisshook, (void*) &data);
374 #endif
375  *symcodetime = SCIPgetSolvingTime(scip) - oldtime;
376 
377 #ifdef SCIP_OUTPUT
378  (void) stats.print(stdout);
379 #endif
380 
381  /* prepare return values */
382  if ( data.nperms > 0 )
383  {
384  *perms = data.perms;
385  *nperms = data.nperms;
386  *nmaxperms = data.nmaxperms;
387  }
388  else
389  {
390  assert( data.perms == NULL );
391  assert( data.nmaxperms == 0 );
392 
393  *perms = NULL;
394  *nperms = 0;
395  *nmaxperms = 0;
396  }
397 
398  /* determine log10 of symmetry group size */
399  *log10groupsize = (SCIP_Real) log10l(stats.get_group_size_approx());
400 
401  return SCIP_OKAY;
402 }
403 
404 /** compute generators of symmetry group */
406  SCIP* scip, /**< SCIP pointer */
407  int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
408  SYM_GRAPH* graph, /**< symmetry detection graph */
409  int* nperms, /**< pointer to store number of permutations */
410  int* nmaxperms, /**< pointer to store maximal number of permutations
411  * (needed for freeing storage) */
412  int*** perms, /**< pointer to store generators as (nperms x npermvars) matrix */
413  SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
414  SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
415  )
416 {
417  int nvarnodestoadd;
418  int first;
419  int second;
420  int nnodes = 0;
421  int nedges = 0;
422 
423  assert( scip != NULL );
424  assert( graph != NULL );
425  assert( nperms != NULL );
426  assert( nmaxperms != NULL );
427  assert( perms != NULL );
428  assert( log10groupsize != NULL );
429  assert( symcodetime != NULL );
430 
431  /* init */
432  *nperms = 0;
433  *nmaxperms = 0;
434  *perms = NULL;
435  *log10groupsize = 0;
436  *symcodetime = 0.0;
437 
438  /* create bliss graph */
439  bliss::Graph G(0);
440 
441  /* add nodes for variables
442  *
443  * Variable nodes come first to easily extract the variable permutation.
444  * For signed permutations, the first nsymvars nodes correspond to original
445  * variables, and the second nsymvars nodes to their negations.
446  */
447  int nsymvars = SCIPgetSymgraphNVars(graph);
449  switch ( symtype )
450  {
451  case SYM_SYMTYPE_PERM:
452  nvarnodestoadd = nsymvars;
453  break;
454  default:
455  assert( symtype == SYM_SYMTYPE_SIGNPERM );
456  nvarnodestoadd = 2 * nsymvars;
457  }
458 
459  for (int v = 0; v < nvarnodestoadd; ++v)
460  {
461  const int color = SCIPgetSymgraphVarnodeColor(graph, v);
462 
463 #ifndef NDEBUG
464  int node = (int) G.add_vertex((unsigned) color);
465  assert( node == v );
466 #else
467  (void) G.add_vertex((unsigned) color);
468 #endif
469 
470  ++nnodes;
471  }
472 
473  /* add nodes for non-variable nodes */
474  int nsymnodes = SCIPgetSymgraphNNodes(graph);
475  for (int v = 0; v < nsymnodes; ++v)
476  {
477  const int color = SCIPgetSymgraphNodeColor(graph, v);
478 
479 #ifndef NDEBUG
480  int node = (int) G.add_vertex((unsigned) color);
481  assert( node == nvarnodestoadd + v );
482 #else
483  (void) G.add_vertex((unsigned) color);
484 #endif
485 
486  ++nnodes;
487  }
488 
489  /* add edges to bliss graph
490  *
491  * Edges containing neither a variable or constraint node are added immediately.
492  * Remaining edges are collected and we group these edges based on their weight.
493  */
494  const bool groupByConstraints = SCIPgetSymgraphNConsnodes(graph) < SCIPgetSymgraphNVars(graph);
495  int nsymedges = SCIPgetSymgraphNEdges(graph);
496  int* groupfirsts = NULL;
497  int* groupseconds = NULL;
498  int* groupcolors = NULL;
499  int ngroupedges = 0;
500 
501  SCIP_CALL( SCIPallocBufferArray(scip, &groupfirsts, nsymedges) );
502  SCIP_CALL( SCIPallocBufferArray(scip, &groupseconds, nsymedges) );
503  SCIP_CALL( SCIPallocBufferArray(scip, &groupcolors, nsymedges) );
504 
505  for (int e = 0; e < nsymedges; ++e)
506  {
507  first = SCIPgetSymgraphEdgeFirst(graph, e);
508  second = SCIPgetSymgraphEdgeSecond(graph, e);
509 
510  if ( first < 0 )
511  first = -first - 1;
512  else
513  first += nvarnodestoadd;
514  if ( second < 0 )
515  second = -second - 1;
516  else
517  second += nvarnodestoadd;
518  assert(first >= 0);
519  assert(second >= 0);
520 
521  /* check whether edge is used for grouping */
522  if ( ! SCIPhasGraphUniqueEdgetype(graph) && isEdgeGroupable(graph, e, groupByConstraints) )
523  {
524  /* store edge, first becomes the cons or var node */
525  SYM_NODETYPE comparetype = groupByConstraints ? SYM_NODETYPE_CONS : SYM_NODETYPE_VAR;
526 
527  if ( SCIPgetSymgraphNodeType(graph, SCIPgetSymgraphEdgeFirst(graph, e)) == comparetype )
528  {
529  groupfirsts[ngroupedges] = first;
530  groupseconds[ngroupedges] = second;
531  }
532  else
533  {
534  groupfirsts[ngroupedges] = second;
535  groupseconds[ngroupedges] = first;
536  }
537  groupcolors[ngroupedges++] = SCIPgetSymgraphEdgeColor(graph, e);
538  }
539  else
540  {
541  /* immediately add edge */
542  assert(0 <= first && first < nnodes);
543  assert(0 <= second && second < nnodes);
544 
545  /* possibly split edge if it is colored */
546  if ( ! SCIPhasGraphUniqueEdgetype(graph) && SCIPisSymgraphEdgeColored(graph, e) )
547  {
548  const int color = SCIPgetSymgraphEdgeColor(graph, e);
549 
550  int inter = G.add_vertex((unsigned) color);
551 
552  G.add_edge(first, inter);
553  G.add_edge(second, inter);
554 
555  ++nnodes;
556  ++nedges;
557  }
558  else
559  G.add_edge(first, second);
560  ++nedges;
561  }
562  }
563 
564  /* possibly add groupable edges */
565  if ( ngroupedges > 0 )
566  {
567  /* sort edges according to their first nodes */
568  SCIPsortIntIntInt(groupfirsts, groupseconds, groupcolors, ngroupedges);
569 
570  int firstidx = 0;
571  int firstnodeidx = groupfirsts[0];
572  int naddednodes;
573  int naddededges;
574 
575  for (int i = 1; i < ngroupedges; ++i)
576  {
577  /* if a new first node has been found, group the edges of the previous first node; ignoring the last group */
578  if ( groupfirsts[i] != firstnodeidx )
579  {
580  SCIP_CALL( addGroupedEdges(&G, firstnodeidx, &groupseconds[firstidx],
581  &groupcolors[firstidx], i - firstidx, &naddednodes, &naddededges) );
582 
583  firstidx = i;
584  firstnodeidx = groupfirsts[i];
585 
586  nnodes += naddednodes;
587  nedges += naddededges;
588  }
589  }
590 
591  /* process the last group */
592  SCIP_CALL( addGroupedEdges(&G, firstnodeidx, &groupseconds[firstidx],
593  &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );
594 
595  nnodes += naddednodes;
596  nedges += naddededges;
597  }
598 
599  SCIPfreeBufferArray(scip, &groupcolors);
600  SCIPfreeBufferArray(scip, &groupseconds);
601  SCIPfreeBufferArray(scip, &groupfirsts);
602 
603  /* for signed permutation, also add edges connecting a variable and its negation */
604  switch ( SCIPgetSymgraphSymtype(graph) )
605  {
607  for (int v = 0; v < nsymvars; ++v)
608  G.add_edge(v, v + nsymvars);
609  nedges += nsymvars;
610  break;
611  default:
612  assert( SCIPgetSymgraphSymtype(graph) == SYM_SYMTYPE_PERM );
613  }
614 
615  assert( (int) G.get_nof_vertices() == nnodes );
616  assert( nedges >= SCIPgetSymgraphNEdges(graph) );
617  SCIPdebugMsg(scip, "Symmetry detection graph has %d nodes and %d edges.\n", nnodes, nedges);
618 
619  /* compute automorphisms */
620  SCIP_CALL( computeAutomorphisms(scip, symtype, &G, nsymvars, maxgenerators,
621  perms, nperms, nmaxperms, log10groupsize, TRUE, symcodetime) );
622 
623  return SCIP_OKAY;
624 }
625 
626 /** returns whether two given graphs are identical */
628  SCIP* scip, /**< SCIP pointer */
629  SYM_SYMTYPE symtype, /**< type of symmetries to be checked */
630  SYM_GRAPH* G1, /**< first graph */
631  SYM_GRAPH* G2 /**< second graph */
632  )
633 {
634  int* nvarused1 = NULL;
635  int* nvarused2 = NULL;
636  int* varlabel = NULL;
637  int nusedvars = 0;
638  int nvars;
639  int i;
640 
641  assert( scip != NULL );
642  assert( G1 != NULL );
643  assert( G2 != NULL );
644 
645  /* some simple checks */
646  if ( G1->nnodes != G2->nnodes || G1->nopnodes != G2->nopnodes || G1->nvalnodes != G2->nvalnodes
647  || G1->nconsnodes != G2->nconsnodes || G1->nedges != G2->nedges )
648  return FALSE;
649 
650  /* check whether the variables used in G1 are the same as in G2 */
651  switch ( symtype )
652  {
653  case SYM_SYMTYPE_PERM:
654  nvars = G1->nsymvars;
655  break;
656  default:
657  assert( symtype == SYM_SYMTYPE_SIGNPERM );
658  nvars = 2 * G1->nsymvars;
659  }
660  SCIP_CALL_ABORT( SCIPallocClearBufferArray(scip, &nvarused1, nvars) );
661  SCIP_CALL_ABORT( SCIPallocClearBufferArray(scip, &nvarused2, nvars) );
662  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &varlabel, nvars) );
663 
664  for (i = 0; i < G1->nedges; ++i)
665  {
666  if ( G1->edgefirst[i] < 0 )
667  nvarused1[-G1->edgefirst[i] - 1] += 1;
668  if ( G2->edgefirst[i] < 0 )
669  nvarused2[-G2->edgefirst[i] - 1] += 1;
670  if ( G1->edgesecond[i] < 0 )
671  nvarused1[-G1->edgesecond[i] - 1] += 1;
672  if ( G2->edgesecond[i] < 0 )
673  nvarused2[-G2->edgesecond[i] - 1] += 1;
674  }
675 
676  for (i = 0; i < nvars; ++i)
677  {
678  if ( nvarused1[i] != nvarused2[i] )
679  {
680  SCIPfreeBufferArray(scip, &varlabel);
681  SCIPfreeBufferArray(scip, &nvarused2);
682  SCIPfreeBufferArray(scip, &nvarused1);
683 
684  return FALSE;
685  }
686 
687  /* relabel variables by restricting to variables used in constraint (or their negation) */
688  if ( nvarused1[i] > 0 || nvarused1[i % G1->nsymvars] > 0 )
689  varlabel[i] = nusedvars++;
690  else
691  varlabel[i] = -1;
692  }
693 
694  /* construct bliss graph containing the (disjoint) union of the two graphs */
695  bliss::Graph G(0);
696 
697  /* copy of G1 */
698  for (i = 0; i < nusedvars; ++i)
699  G.add_vertex(i);
700 
701  for (i = 0; i < G1->nnodes; ++i)
702  G.add_vertex(nusedvars + SCIPgetSymgraphNodeColor(G1, i));
703 
704  for (i = 0; i < G1->nedges; ++i)
705  {
706  int first = G1->edgefirst[i];
707  int second = G1->edgesecond[i];
708 
709  if ( first < 0 )
710  first = varlabel[-first - 1];
711  else
712  first = nusedvars + first;
713  assert( first >= 0 );
714 
715  if ( second < 0 )
716  second = varlabel[-second - 1];
717  else
718  second = nusedvars + second;
719  assert( second >= 0 );
720 
721  if ( SCIPisSymgraphEdgeColored(G1, i) )
722  {
723  int inter = G.add_vertex(nusedvars + SCIPgetSymgraphEdgeColor(G1, i));
724  G.add_edge(first, inter);
725  G.add_edge(second, inter);
726  }
727  else
728  G.add_edge(first, second);
729  }
730 
731  /* in case of signed permutations, also connect variables with their negation */
732  switch ( symtype )
733  {
735  for (i = 0; i < G1->nsymvars; ++i)
736  {
737  if ( nvarused1[i] > 0 || nvarused1[i + G1->nsymvars])
738  G.add_edge(varlabel[i], varlabel[i + G1->nsymvars]);
739  }
740  break;
741  default:
742  assert( symtype == SYM_SYMTYPE_PERM );
743  }
744 
745  /* copy of G2 */
746  int nodeshift = G.get_nof_vertices();
747  for (i = 0; i < nusedvars; ++i)
748  G.add_vertex(i);
749 
750  for (i = 0; i < G2->nnodes; ++i)
751  G.add_vertex(nusedvars + SCIPgetSymgraphNodeColor(G2, i));
752 
753  for (i = 0; i < G2->nedges; ++i)
754  {
755  int first = G2->edgefirst[i];
756  int second = G2->edgesecond[i];
757 
758  if ( first < 0 )
759  first = nodeshift + varlabel[-first - 1];
760  else
761  first = nodeshift + nusedvars + first;
762  assert( first >= 0 );
763 
764  if ( second < 0 )
765  second = nodeshift + varlabel[-second - 1];
766  else
767  second = nodeshift + nusedvars + second;
768  assert( second >= 0 );
769 
770  if ( SCIPisSymgraphEdgeColored(G2, i) )
771  {
772  int inter = G.add_vertex(nusedvars + SCIPgetSymgraphEdgeColor(G2, i));
773  G.add_edge(first, inter);
774  G.add_edge(second, inter);
775  }
776  else
777  G.add_edge(first, second);
778  }
779 
780  /* in case of signed permutations, also connect variables with their negation */
781  switch ( symtype )
782  {
784  for (i = 0; i < G2->nsymvars; ++i)
785  {
786  if ( nvarused2[i] > 0 || nvarused2[i + G2->nsymvars])
787  G.add_edge(nodeshift + varlabel[i], nodeshift + varlabel[i + G2->nsymvars]);
788  }
789  break;
790  default:
791  assert( symtype == SYM_SYMTYPE_PERM );
792  }
793 
794  /* compute automorphisms */
795  int** perms;
796  int nperms;
797  int nmaxperms;
798  SCIP_Real log10groupsize;
799  int n = G.get_nof_vertices();
800  int nnodesfromG1 = nusedvars + G1->nnodes;
801  SCIP_Real symcodetime = 0.0;
802 
803  SCIP_CALL_ABORT( computeAutomorphisms(scip, symtype, &G, n, 0,
804  &perms, &nperms, &nmaxperms, &log10groupsize, FALSE, &symcodetime) );
805 
806  /* since G1 and G2 are connected and disjoint, they are isomorphic iff there is a permutation
807  * mapping a node from G1 to a node of G2
808  */
809  SCIP_Bool success = FALSE;
810  for (int p = 0; p < nperms && ! success; ++p)
811  {
812  for (i = 0; i < nnodesfromG1; ++i)
813  {
814  if ( perms[p][i] >= nnodesfromG1 )
815  {
816  success = TRUE;
817  break;
818  }
819  }
820  }
821 
822  for (int p = 0; p < nperms; ++p)
823  {
824  SCIPfreeBlockMemoryArray(scip, &perms[p], n);
825  }
826  SCIPfreeBlockMemoryArrayNull(scip, &perms, nmaxperms);
827 
828  SCIPfreeBufferArray(scip, &varlabel);
829  SCIPfreeBufferArray(scip, &nvarused2);
830  SCIPfreeBufferArray(scip, &nvarused1);
831 
832  return success;
833 }
#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
#define NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_GRAPH *graph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
#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)
const char * SYMsymmetryGetName(void)
private functions to work with algebraic expressions
#define FALSE
Definition: def.h:94
int * edgesecond
int SCIPgetSymgraphNEdges(SYM_GRAPH *graph)
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
const char * SYMsymmetryGetDesc(void)
SCIP_Bool SYMcanComputeSymmetry(void)
SCIP_Bool SCIPhasGraphUniqueEdgetype(SYM_GRAPH *graph)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
variable expression handler
#define SCIPdebugMsg
Definition: scip_message.h:78
interface for symmetry computations
static void blisshook(void *user_param, unsigned int n, const unsigned int *aut)
methods for dealing with symmetry detection graphs
int SCIPgetSymgraphEdgeFirst(SYM_GRAPH *graph, int edgeidx)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_Bool SCIPisSymgraphEdgeColored(SYM_GRAPH *graph, int edgeidx)
static SCIP_RETCODE addGroupedEdges(bliss::Graph *G, int commonnodeidx, int *neighbors, int *colors, int nneighbors, int *naddednodes, int *naddededges)
power and signed power expression handlers
#define SCIP_CALL(x)
Definition: def.h:380
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIP_Bool
Definition: def.h:91
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 isEdgeGroupable(SYM_GRAPH *graph, int edgeidx, SCIP_Bool groupbycons)
methods for handling symmetries
int SCIPgetSymgraphNConsnodes(SYM_GRAPH *graph)
#define SCIP_Real
Definition: def.h:173
SYM_NODETYPE SCIPgetSymgraphNodeType(SYM_GRAPH *graph, int nodeidx)
const char * SYMsymmetryGetAddDesc(void)
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
sum expression handler
int * edgefirst
#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
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)
static SCIP_RETCODE computeAutomorphisms(SCIP *scip, SYM_SYMTYPE symtype, bliss::Graph *G, int nsymvars, int maxgenerators, int ***perms, int *nperms, int *nmaxperms, SCIP_Real *log10groupsize, SCIP_Bool restricttovars, SCIP_Real *symcodetime)
const char * SYMsymmetryGetAddName(void)