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 */
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 */
78static struct NAUTY_Data data_;
79
80/* ------------------- hook functions ------------------- */
81
82#ifdef NAUTY
83
84/** callback function for nauty */ /*lint -e{715}*/
85static
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 {
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 */
164static
165void 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 {
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 */
241static
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 */
302static
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 */
427static
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);
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 {
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 {
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 */
726static
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);
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 {
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 }
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 */
1150static TLS_ATTR char nautyname[20];
1151
1152/** return name of external program used to compute generators */
1153const 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 */
1165const 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 */
1175const char* SYMsymmetryGetAddName(void)
1176{
1177 return NULL;
1178}
1179
1180/** return description of additional external program used to compute symmetries */
1181const 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 */
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;
1294 data_.nperms = 0;
1295 data_.nmaxperms = 0;
1297 data_.perms = NULL;
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);
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;
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 */
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;
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);
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 {
1521 }
1523
1524 SG_FREE(SG); /*lint !e774*/
1525
1526 return success;
1527}
SCIP_VAR * w
Definition: circlepacking.c:67
interface for symmetry computations
SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
const char * SYMsymmetryGetName(void)
static void nautyhook(int count, int *p, int *orbits, int numorbits, int stabvertex, int n)
const char * SYMsymmetryGetAddName(void)
static struct NAUTY_Data data_
SCIP_Bool SYMcanComputeSymmetry(void)
const char * SYMsymmetryGetDesc(void)
static TLS_ATTR char nautyname[20]
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)
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)
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)
static SCIP_Bool isEdgeGroupable(SYM_GRAPH *symgraph, int edgeidx, SCIP_Bool groupbycons)
const char * SYMsymmetryGetAddDesc(void)
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_GRAPH *symgraph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
Constraint handler for linear constraints in their most general form, .
constraint handler for nonlinear constraints specified by algebraic expressions
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL_ABORT(x)
Definition: def.h:353
#define SCIP_CALL(x)
Definition: def.h:374
private functions to work with algebraic expressions
power and signed power expression handlers
sum expression handler
variable expression handler
#define nnodes
Definition: gastrans.c:74
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
Definition: scip_mem.h:107
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SYM_NODETYPE SCIPgetSymgraphNodeType(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphEdgeFirst(SYM_GRAPH *graph, int edgeidx)
SCIP_Bool SCIPhasGraphUniqueEdgetype(SYM_GRAPH *graph)
int SCIPgetSymgraphVarnodeColor(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphNEdges(SYM_GRAPH *graph)
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
int SCIPgetSymgraphEdgeSecond(SYM_GRAPH *graph, int edgeidx)
int SCIPgetSymgraphNConsnodes(SYM_GRAPH *graph)
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
SCIP_Bool SCIPisSymgraphEdgeColored(SYM_GRAPH *graph, int edgeidx)
int SCIPgetSymgraphNodeColor(SYM_GRAPH *graph, int nodeidx)
int SCIPgetSymgraphEdgeColor(SYM_GRAPH *graph, int edgeidx)
int SCIPgetSymgraphNNodes(SYM_GRAPH *graph)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
public methods for memory management
SYM_SYMTYPE symtype
SCIP_Bool restricttovars
methods for dealing with symmetry detection graphs
@ SCIP_VERBLEVEL_MINIMAL
Definition: type_message.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
enum SYM_Nodetype SYM_NODETYPE
Definition: type_symmetry.h:74
@ SYM_NODETYPE_CONS
Definition: type_symmetry.h:71
@ SYM_NODETYPE_VAR
Definition: type_symmetry.h:72
@ SYM_SYMTYPE_SIGNPERM
Definition: type_symmetry.h:62
@ SYM_SYMTYPE_PERM
Definition: type_symmetry.h:61