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