SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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 */
106 return;
107 }
108
109 /* copy first part of automorphism */
110 if ( data_.restricttovars )
111 {
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 )
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
148 assert( data_.maxgenerators == 0 );
149
151 return;
152
154 }
155
157 return;
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 */
183 return;
184 }
185
186 /* copy first part of automorphism */
187 if ( data_.restricttovars )
188 {
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 )
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
225 assert( data_.maxgenerators == 0 );
226
228 return;
229
231 }
232
234 return;
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
255
256 /* uncolored edges are not grouped */
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 {
279 return TRUE;
280 }
281 else if ( first >= 0 )
282 {
284 return TRUE;
285 }
286 else
287 {
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 );
341
342 *naddednodes = 0;
343 *naddededges = 0;
344
345 /* sort edges according to color */
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 {
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 {
375
376 for (f = curstart; f < e; ++f)
377 {
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 {
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 {
412
413 for (f = curstart; f < nneighbors; ++f)
414 {
417 }
418 }
419 *naddednodes += 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*/
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:
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 */
493 *nedges = 0;
494
495 /* possibly allocate memory for degrees (will grow dynamically) */
496 *degrees = NULL;
497 *maxdegrees = 0;
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;
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 */
527
528 /* allocate arrays to collect edges to be grouped */
533
534 /* loop through all edges of the symmetry detection graph and either get degrees of nodes or add edges */
536 for (e = 0; e < SCIPgetSymgraphNEdges(symgraph); ++e)
537 {
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
550 assert(first >= 0);
551 assert(second >= 0);
552
553 /* check whether edge is used for grouping */
555 {
556 /* store edge, first becomes the cons or var node */
558
560 {
561 groupfirsts[ngroupedges] = first;
563 }
564 else
565 {
567 groupseconds[ngroupedges] = first;
568 }
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 */
579 {
580 if ( determinesize )
581 {
584 ++(*degrees)[first];
585 ++(*degrees)[second];
586 (*degrees)[internodeid] = 2;
587 ++(*nnodes);
588 *nedges += 2;
590 ++internodeid;
591 }
592 else
593 {
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 */
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 {
648 degrees, maxdegrees, colors, ncolors, nnodes, nedges, firstnodeidx, &groupseconds[firstidx],
649 &groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );
650
651 firstidx = j;
653
654 if ( determinesize )
655 {
657 *nedges += naddededges;
658 }
659 }
660 }
661
662 /* process the last group */
664 degrees, maxdegrees, colors, ncolors, nnodes, nedges, firstnodeidx, &groupseconds[firstidx],
665 &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );
666
667 if ( determinesize )
668 {
670 *nedges += naddededges;
671 }
672 }
673
677
678 /* for signed permutation, also add edges connecting a variable and its negation */
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:
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{
746 SCIP_Bool groupByConstraints;
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 );
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 */
797 return SCIP_OKAY;
798
799 /* collect basic information from symmetry detection graph */
800 nsymvars = SCIPgetSymgraphNVars(graph1);
803 switch ( symtype )
804 {
805 case SYM_SYMTYPE_PERM:
806 nvarnodestoadd = nsymvars;
807 break;
808 default:
810 nvarnodestoadd = 2 * nsymvars;
811 } /*lint !e788*/
812
813 /* find the variables that are contained in an edge */
817
818 for (e = 0; e < nsymedges; ++e)
819 {
822 if ( first < 0 )
823 nvarused1[-first - 1] += 1;
824 if ( second < 0 )
825 nvarused1[-second - 1] += 1;
826
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 {
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 {
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 */
881
882 /* allocate arrays to collect edges to be grouped */
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 {
904 (*degrees)[nodeshift + varlabel[j]] = 0;
906 ++(*nnodes);
907 ++curnnodes;
908 }
909 }
910
911 /* add nodes for remaining nodes of graph */
912 for (j = 0; j < SCIPgetSymgraphNNodes(symgraph); ++j)
913 {
915 (*degrees)[nodeshift + nusdvars + j] = 0;
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 }
930 }
931
932 /* loop through all edges of the symmetry detection graph and either get degrees of nodes or add edges */
934 for (e = 0; e < nsymedges; ++e)
935 {
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
948
949 /* check whether edge is used for grouping */
951 {
952 /* store edge, first becomes the cons or var node */
954
956 {
959 }
960 else
961 {
964 }
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 */
975 {
976 if ( determinesize )
977 {
980
981 ++(*degrees)[nodeshift + first];
982 ++(*degrees)[nodeshift + second];
983 (*degrees)[internodeid] = 2;
984
986 (*colors)[internodeid] = nusdvars + color;
987
988 ++(*nnodes);
989 *nedges += 2;
990 }
991 else
992 {
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 */
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 {
1048 degrees, maxdegrees, colors, ncolors, nnodes, nedges, firstnodeidx,
1049 &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );
1050
1051 firstidx = j;
1053
1054 if ( determinesize )
1055 {
1056 *nnodes += naddednodes;
1057 *nedges += naddededges;
1058 }
1060 }
1061 }
1062
1063 /* process the last group */
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 }
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 }
1099
1100 /* possibly store number of nodes arising from first graph */
1101 if ( determinesize && i == 0 )
1103 }
1104
1105 /* add dummy node */
1106 if ( determinesize )
1107 {
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
1131
1135
1136 *success = TRUE;
1137 if ( determinesize )
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 name */
1150#ifdef NAUTY
1151static const char nautyname[] = "Nauty "NAUTYVERSION;
1152#else
1153static const char nautyname[] = "Traces "NAUTYVERSION;
1154#endif
1155
1156/** return name of external program used to compute generators */
1157const char* SYMsymmetryGetName(void)
1158{
1159 return nautyname;
1160}
1161
1162/** return description of external program used to compute generators */
1163const char* SYMsymmetryGetDesc(void)
1164{
1165#ifdef NAUTY
1166 return "Computing Graph Automorphism Groups by Brendan D. McKay (https://users.cecs.anu.edu.au/~bdm/nauty/)";
1167#else
1168 return "Computing Graph Automorphism Groups by Adolfo Piperno (https://pallini.di.uniroma1.it/)";
1169#endif
1170}
1171
1172/** return name of additional external program used for computing symmetries */
1173const char* SYMsymmetryGetAddName(void)
1174{
1175 return NULL;
1176}
1177
1178/** return description of additional external program used to compute symmetries */
1179const char* SYMsymmetryGetAddDesc(void)
1180{
1181 return NULL;
1182}
1183
1184/** compute generators of symmetry group */
1186 SCIP* scip, /**< SCIP pointer */
1187 int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
1188 SYM_GRAPH* symgraph, /**< symmetry detection graph */
1189 int* nperms, /**< pointer to store number of permutations */
1190 int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
1191 int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
1192 SCIP_Real* log10groupsize, /**< pointer to store size of group */
1193 SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
1194 )
1195{
1196 SCIP_Real oldtime;
1197 int nnodes;
1198 int nedges;
1199 int* degrees;
1200 int maxdegrees;
1201 int* colors;
1202 int ncolors;
1203 SCIP_Bool success;
1204 int v;
1205
1206 /* nauty data structures */
1208 int* lab;
1209 int* ptn;
1210 int* orbits;
1211
1212#ifdef NAUTY
1214 statsblk stats;
1215#else
1217 TracesStats stats;
1218#endif
1219
1220 /* init */
1221 *nperms = 0;
1222 *nmaxperms = 0;
1223 *perms = NULL;
1224 *log10groupsize = 0;
1225 *symcodetime = 0.0;
1226
1227 /* init options */
1228#ifdef NAUTY
1229 /* init callback functions for nauty (accumulate the group generators found by nauty) */
1230 options.writeautoms = FALSE;
1231 options.userautomproc = nautyhook;
1232 options.defaultptn = FALSE; /* use color classes */
1233#else
1234 /* init callback functions for traces (accumulate the group generators found by traces) */
1235 options.writeautoms = FALSE;
1236 options.userautomproc = traceshook;
1237 options.defaultptn = FALSE; /* use color classes */
1238#endif
1239
1241
1242 /* determine the number of nodes and edges */
1244 &degrees, &maxdegrees, &colors, &ncolors, &success) );
1245
1246 if ( ! success )
1247 {
1249 "Stopped symmetry computation: Symmetry graph would become too large.\n");
1250 return SCIP_OKAY;
1251 }
1252
1253 /* init graph */
1254 SG_INIT(SG);
1255
1256 SG_ALLOC(SG, (size_t) nnodes, 2 * (size_t)(unsigned) nedges, "malloc"); /*lint !e647*//*lint !e774*//*lint !e571*/
1257
1258 SG.nv = nnodes; /* number of nodes */
1259 SG.nde = (size_t) (unsigned) (2 * nedges); /* number of directed edges */
1260
1261 /* add the nodes for linear and nonlinear constraints to the graph */
1263 &degrees, &maxdegrees, &colors, &ncolors, &success) );
1264
1266
1267 /* memory allocation for nauty/traces */
1271
1272 /* fill in array with colors for variables */
1273 for (v = 0; v < nnodes; ++v)
1274 lab[v] = v;
1275
1276 /* sort nodes according to colors */
1277 SCIPsortIntInt(colors, lab, nnodes);
1278
1279 /* set up ptn marking new colors */
1280 for (v = 0; v < nnodes; ++v)
1281 {
1282 if ( v < nnodes-1 && colors[v] == colors[v+1] )
1283 ptn[v] = 1; /* color class does not end */
1284 else
1285 ptn[v] = 0; /* color class ends */
1286 }
1287
1288 SCIPdebugMsg(scip, "Symmetry detection graph has %d nodes.\n", nnodes);
1289
1290 data_.scip = scip;
1292 data_.nperms = 0;
1293 data_.nmaxperms = 0;
1295 data_.perms = NULL;
1298
1299 /* call nauty/traces */
1300#ifdef NAUTY
1301 sparsenauty(&SG, lab, ptn, orbits, &options, &stats, NULL);
1302#else
1303 Traces(&SG, lab, ptn, orbits, &options, &stats, NULL);
1304#endif
1306
1307 SCIPfreeBufferArray(scip, &orbits);
1310
1312
1313 SG_FREE(SG); /*lint !e774*/
1314
1315 /* prepare return values */
1316 if ( data_.nperms > 0 )
1317 {
1318 *perms = data_.perms;
1319 *nperms = data_.nperms;
1321 }
1322 else
1323 {
1324 assert( data_.perms == NULL );
1325 assert( data_.nmaxperms == 0 );
1326
1327 *perms = NULL;
1328 *nperms = 0;
1329 *nmaxperms = 0;
1330 }
1331
1332 /* determine log10 of symmetry group size */
1333 *log10groupsize = (SCIP_Real) stats.grpsize2;
1334
1335 return SCIP_OKAY;
1336}
1337
1338/** returns whether two given graphs are identical */
1340 SCIP* scip, /**< SCIP pointer */
1341 SYM_SYMTYPE symtype, /**< type of symmetries to be checked */
1342 SYM_GRAPH* G1, /**< first graph */
1343 SYM_GRAPH* G2 /**< second graph */
1344 )
1345{
1346 int nnodes;
1347 int nedges;
1348 int* degrees;
1349 int maxdegrees;
1350 int* colors;
1351 int ncolors;
1352 int nusedvars;
1353 SCIP_Bool success;
1354 int v;
1355 int nnodesfromG1;
1356
1357 assert( scip != NULL );
1358 assert( G1 != NULL );
1359 assert( G2 != NULL );
1360
1361 /* some simple checks */
1362 if ( G1->nnodes != G2->nnodes || G1->nopnodes != G2->nopnodes || G1->nvalnodes != G2->nvalnodes
1363 || G1->nconsnodes != G2->nconsnodes || G1->nedges != G2->nedges )
1364 return FALSE;
1365
1367 &colors, &ncolors, &nusedvars, &nnodesfromG1, &success) );
1368
1369 if ( ! success )
1370 {
1373
1374 return FALSE;
1375 }
1376
1377 /* nauty data structures */
1379 int* lab;
1380 int* ptn;
1381 int* orbits;
1382
1383#ifdef NAUTY
1385 statsblk stats;
1386#else
1388 TracesStats stats;
1389#endif
1390
1391 /* init options */
1392#ifdef NAUTY
1393 /* init callback functions for nauty (accumulate the group generators found by nauty) */
1394 options.writeautoms = FALSE;
1395 options.userautomproc = nautyhook;
1396 options.defaultptn = FALSE; /* use color classes */
1397#else
1398 /* init callback functions for traces (accumulate the group generators found by traces) */
1399 options.writeautoms = FALSE;
1400 options.userautomproc = traceshook;
1401 options.defaultptn = FALSE; /* use color classes */
1402#endif
1403
1404 /* init graph */
1405 SG_INIT(SG);
1406
1407 SG_ALLOC(SG, (size_t) nnodes, 2 * (size_t)(unsigned) nedges, "malloc"); /*lint !e647*//*lint !e774*//*lint !e571*/
1408
1409 SG.nv = nnodes; /* number of nodes */
1410 SG.nde = (size_t) (unsigned) (2 * nedges); /* number of directed edges */
1411
1412 /* add the nodes for linear and nonlinear constraints to the graph */
1414 &colors, &ncolors, &nusedvars, NULL, &success) );
1415 assert( success );
1416
1418
1419#ifdef SCIP_DISABLED_CODE
1420 /* print information about sparsegraph */
1421 SCIPinfoMessage(scip, NULL, "number of nodes: %d\n", SG.nv);
1422 SCIPinfoMessage(scip, NULL, "number of (directed) edges: %lu\n", SG.nde);
1423 SCIPinfoMessage(scip, NULL, "degrees\n");
1424 for (v = 0; v < SG.nv; ++v)
1425 {
1426 SCIPinfoMessage(scip, NULL, "node %d: %d\n", v, SG.d[v]);
1427 }
1428 SCIPinfoMessage(scip, NULL, "colors\n");
1429 for (v = 0; v < SG.nv; ++v)
1430 {
1431 SCIPinfoMessage(scip, NULL, "node %d: %d\n", v, colors[v]);
1432 }
1433 SCIPinfoMessage(scip, NULL, "edges\n");
1434 for (v = 0; v < SG.nv; ++v)
1435 {
1436 for (int w = 0; w < SG.d[v]; ++w)
1437 {
1438 SCIPinfoMessage(scip, NULL, "(%d,%d)\n", v, SG.e[SG.v[v] + w]);
1439 }
1440 }
1441#endif
1442
1443 /* memory allocation for nauty/traces */
1447
1448 /* fill in array with colors for variables */
1449 for (v = 0; v < nnodes; ++v)
1450 lab[v] = v;
1451
1452 /* sort nodes according to colors */
1453 SCIPsortIntInt(colors, lab, nnodes);
1454
1455 /* set up ptn marking new colors */
1456 for (v = 0; v < nnodes; ++v)
1457 {
1458 if ( v < nnodes-1 && colors[v] == colors[v+1] )
1459 ptn[v] = 1; /* color class does not end */
1460 else
1461 ptn[v] = 0; /* color class ends */
1462 }
1463
1464#ifdef SCIP_DISABLED_CODE
1465 /* print further information about sparsegraph */
1466 SCIPinfoMessage(scip, NULL, "lab (and ptn):\n");
1467 for (v = 0; v < SG.nv; ++v)
1468 {
1469 SCIPinfoMessage(scip, NULL, "%d (%d)\n", lab[v], ptn[v]);
1470 }
1471#endif
1472
1473 /* compute automorphisms */
1474 data_.scip = scip;
1476 data_.nperms = 0;
1477 data_.nmaxperms = 0;
1478 data_.maxgenerators = 0;
1479 data_.perms = NULL;
1482
1483 /* call nauty/traces */
1484#ifdef NAUTY
1485 sparsenauty(&SG, lab, ptn, orbits, &options, &stats, NULL);
1486#else
1487 Traces(&SG, lab, ptn, orbits, &options, &stats, NULL);
1488#endif
1489
1490 SCIPfreeBufferArray(scip, &orbits);
1493
1495
1496 SG_FREE(SG); /*lint !e774*/
1497
1498 /* G1 and G2 cannot be isomorphic */
1499 if ( data_.nperms == 0 )
1500 return FALSE;
1501
1502 success = FALSE;
1503 for (int p = 0; p < data_.nperms; ++p)
1504 {
1505 for (int i = 0; i < nnodesfromG1; ++i)
1506 {
1507 if ( data_.perms[p][i] >= nnodesfromG1 )
1508 {
1509 success = TRUE;
1510 break;
1511 }
1512 }
1513 }
1514
1515 /* free memory */
1516 for (int p = 0; p < data_.nperms; ++p)
1517 {
1519 }
1521
1522 SG_FREE(SG); /*lint !e774*/
1523
1524 return success;
1525}
SCIP_VAR * w
interface for symmetry computations
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)
static struct NAUTY_Data data_
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 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_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,...)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
#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)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntIntInt(int *intarray1, int *intarray2, int *intarray3, int len)
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
public methods for memory management
methods for dealing with symmetry detection graphs
@ SCIP_VERBLEVEL_MINIMAL
enum SCIP_Retcode SCIP_RETCODE
enum SYM_Symtype SYM_SYMTYPE
enum SYM_Nodetype SYM_NODETYPE
@ SYM_NODETYPE_CONS
@ SYM_NODETYPE_VAR
@ SYM_SYMTYPE_SIGNPERM
@ SYM_SYMTYPE_PERM