39#pragma GCC diagnostic ignored "-Wunused-variable"
40#pragma GCC diagnostic ignored "-Wredundant-decls"
41#pragma GCC diagnostic ignored "-Wpedantic"
44#include "nauty/nauty.h"
45#include "nauty/nausparse.h"
47#include "nauty/traces.h"
50#pragma GCC diagnostic warning "-Wunused-variable"
51#pragma GCC diagnostic warning "-Wredundant-decls"
52#pragma GCC diagnostic warning "-Wpedantic"
62#include "tinycthread/tinycthread.h"
82#if defined(_Thread_local)
113 nauty_kill_request = 1;
118 if (
data_.restricttovars )
121 permlen =
data_.npermvars;
123 permlen = 2 *
data_.npermvars;
129 for (
int j = 0; j < permlen; ++j)
131 if ( (
int) p[j] != j )
140 if (
data_.nmaxperms <= 0 )
142 if (
data_.maxgenerators == 0 )
143 data_.nmaxperms = 100;
161 data_.nmaxperms = newsize;
187 if ( numcells >=
data_.maxncells )
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");
196 else if (
data_.ntreenodes >=
data_.maxnnodes )
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");
210 nauty_kill_request = 1;
236 nauty_kill_request = 1;
241 if (
data_.restricttovars )
244 permlen =
data_.npermvars;
246 permlen = 2 *
data_.npermvars;
252 for (j = 0; j < permlen; ++j)
254 if ( (
int) p[j] != j )
263 if (
data_.nmaxperms <= 0 )
265 if (
data_.maxgenerators == 0 )
266 data_.nmaxperms = 100;
284 data_.nmaxperms = newsize;
315 if ( first < 0 && second < 0 )
321 if ( first < 0 || second < 0 )
327 if ( first >= 0 && second >= 0 )
335 else if ( first >= 0 )
384 assert( *internodeid >= 0 );
387 assert( *maxdegrees > 0 );
394 assert( commonnodeidx <= *internodeid );
403 curcolor = colors[0];
405 for (e = 1; e < nneighbors; ++e)
408 if ( colors[e] != curcolor )
414 (*degrees)[*internodeid] = 1;
415 ++(*degrees)[commonnodeidx];
416 (*colorstostore)[*internodeid] = curcolor;
418 for (f = curstart; f < e; ++f)
420 assert( neighbors[f] <= *internodeid );
421 ++(*degrees)[*internodeid];
422 ++(*degrees)[neighbors[f]];
427 SG->e[edgestartpos[commonnodeidx]++] = *internodeid;
428 SG->e[edgestartpos[*internodeid]++] = commonnodeidx;
430 for (f = curstart; f < e; ++f)
432 SG->e[edgestartpos[neighbors[f]]++] = *internodeid;
433 SG->e[edgestartpos[*internodeid]++] = neighbors[f];
437 *naddededges += e - curstart + 1;
440 curcolor = colors[e];
451 (*degrees)[*internodeid] = 1;
452 ++(*degrees)[commonnodeidx];
453 (*colorstostore)[*internodeid] = curcolor;
455 for (f = curstart; f < nneighbors; ++f)
457 assert( neighbors[f] <= *internodeid );
458 ++(*degrees)[*internodeid];
459 ++(*degrees)[neighbors[f]];
464 SG->e[edgestartpos[commonnodeidx]++] = *internodeid;
465 SG->e[edgestartpos[*internodeid]++] = commonnodeidx;
467 for (f = curstart; f < nneighbors; ++f)
469 SG->e[edgestartpos[*internodeid]++] = neighbors[f];
470 SG->e[edgestartpos[neighbors[f]]++] = *internodeid;
474 *naddededges += nneighbors - curstart + 1;
499 int* groupfirsts =
NULL;
500 int* groupseconds =
NULL;
501 int* groupcolors =
NULL;
503 int edgebegincnt = 0;
533 nvarnodestoadd = nsymvars;
537 nvarnodestoadd = 2 * nsymvars;
553 for (j = 0; j < *
nnodes; ++j)
560 for (j = 0; j < nvarnodestoadd; ++j)
570 for (j = 0; j < *
nnodes; ++j)
572 SG->d[j] = (*degrees)[j];
573 SG->v[j] = (size_t) (
unsigned) edgebegincnt;
574 pos[j] = edgebegincnt;
575 edgebegincnt += (*degrees)[j];
599 first += nvarnodestoadd;
601 second = -second - 1;
603 second += nvarnodestoadd;
615 groupfirsts[ngroupedges] = first;
616 groupseconds[ngroupedges] = second;
620 groupfirsts[ngroupedges] = second;
621 groupseconds[ngroupedges] = first;
639 ++(*degrees)[second];
640 (*degrees)[internodeid] = 2;
651 SG->e[pos[first]++] = internodeid;
652 SG->e[pos[internodeid]++] = first;
653 SG->e[pos[second]++] = internodeid;
654 SG->e[pos[internodeid]++] = second;
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] );
668 ++(*degrees)[second];
674 SG->e[pos[first]++] = second;
675 SG->e[pos[second]++] = first;
677 assert( first == *
nnodes - 1 || pos[first] <= (
int) SG->v[first+1] );
678 assert( second == *
nnodes - 1 || pos[second] <= (
int) SG->v[second+1] );
685 if ( ngroupedges > 0 )
694 firstnodeidx = groupfirsts[0];
696 for (j = 1; j < ngroupedges; ++j)
699 if ( groupfirsts[j] != firstnodeidx )
702 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx, &groupseconds[firstidx],
703 &groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );
706 firstnodeidx = groupfirsts[j];
711 *nedges += naddededges;
718 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx, &groupseconds[firstidx],
719 &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );
724 *nedges += naddededges;
738 for (j = 0; j < nvarnodestoadd; ++j)
744 for (j = 0; j < nsymvars; ++j)
746 SG->e[pos[j]++] = j + nsymvars;
747 SG->e[pos[j + nsymvars]++] = j;
749 assert( pos[j] <= (
int) SG->v[j+1] );
750 assert( j + nsymvars == *
nnodes - 1 || pos[j+nsymvars] <= (
int) SG->v[j+nsymvars+1] );
794 int* nnodesfromgraph1,
802 int* nvarused1 =
NULL;
803 int* nvarused2 =
NULL;
804 int* varlabel =
NULL;
805 int* groupfirsts =
NULL;
806 int* groupseconds =
NULL;
807 int* groupcolors =
NULL;
810 int edgebegincnt = 0;
836 assert( ! determinesize || nnodesfromgraph1 !=
NULL );
860 nvarnodestoadd = nsymvars;
864 nvarnodestoadd = 2 * nsymvars;
872 for (e = 0; e < nsymedges; ++e)
877 nvarused1[-first - 1] += 1;
879 nvarused1[-second - 1] += 1;
884 nvarused2[-first - 1] += 1;
886 nvarused2[-second - 1] += 1;
889 for (j = 0; j < nvarnodestoadd; ++j)
892 if ( nvarused1[j] != nvarused2[j] )
903 varlabel[j] = nusdvars++;
924 for (j = 0; j < *
nnodes; ++j)
926 SG->d[j] = (*degrees)[j];
927 SG->v[j] = (size_t) (
unsigned) edgebegincnt;
928 pos[j] = edgebegincnt;
929 edgebegincnt += (*degrees)[j];
943 for (
i = 0;
i < 2; ++
i)
946 symgraph =
i == 0 ? graph1 : graph2;
953 for (j = 0; j < nvarnodestoadd; ++j)
955 if ( varlabel[j] >= 0 )
958 (*degrees)[nodeshift + varlabel[j]] = 0;
969 (*degrees)[nodeshift + nusdvars + j] = 0;
978 for (j = 0; j < nvarnodestoadd; ++j)
980 if ( varlabel[j] >= 0 )
987 internodeid = nodeshift + curnnodes;
988 for (e = 0; e < nsymedges; ++e)
995 first = varlabel[-first - 1];
997 first = nusdvars + first;
999 second = varlabel[-second - 1];
1001 second = nusdvars + second;
1011 groupfirsts[ngroupedges] = nodeshift + first;
1012 groupseconds[ngroupedges] = nodeshift + second;
1016 groupfirsts[ngroupedges] = nodeshift + second;
1017 groupseconds[ngroupedges] = nodeshift + first;
1030 if ( determinesize )
1035 ++(*degrees)[nodeshift + first];
1036 ++(*degrees)[nodeshift + second];
1037 (*degrees)[internodeid] = 2;
1040 (*colors)[internodeid] = nusdvars + color;
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;
1055 || pos[internodeid] <= (
int) SG->v[internodeid+1] );
1057 || pos[nodeshift + first] <= (
int) SG->v[nodeshift+first+1] );
1059 pos[nodeshift + second] <= (
int) SG->v[nodeshift+second+1] );
1066 if ( determinesize )
1068 ++(*degrees)[nodeshift + first];
1069 ++(*degrees)[nodeshift + second];
1074 SG->e[pos[nodeshift + first]++] = nodeshift + second;
1075 SG->e[pos[nodeshift + second]++] = nodeshift + first;
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] );
1085 if ( ngroupedges > 0 )
1094 firstnodeidx = groupfirsts[0];
1096 for (j = 1; j < ngroupedges; ++j)
1099 if ( groupfirsts[j] != firstnodeidx )
1102 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx,
1103 &groupseconds[firstidx], &groupcolors[firstidx], j - firstidx, &naddednodes, &naddededges) );
1106 firstnodeidx = groupfirsts[j];
1108 if ( determinesize )
1111 *nedges += naddededges;
1113 curnnodes += naddednodes;
1119 degrees, maxdegrees, colors, ncolors,
nnodes, nedges, firstnodeidx,
1120 &groupseconds[firstidx], &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );
1122 if ( determinesize )
1125 *nedges += naddededges;
1127 curnnodes += naddednodes;
1133 if ( determinesize )
1135 for (j = 0; j < nusdvars; ++j)
1136 ++(*degrees)[nodeshift + j];
1137 (*nedges) += nusdvars / 2;
1141 for (j = 0; j < nusdvars/2; ++j)
1143 SG->e[pos[nodeshift+j]++] = nodeshift + j + nusdvars/2;
1144 SG->e[pos[nodeshift + j + nusdvars/2]++] = nodeshift + j;
1146 assert( pos[nodeshift+j] <= (
int) SG->v[nodeshift+j+1] );
1148 || pos[nodeshift+j+nusdvars/2] <= (
int) SG->v[nodeshift+j+nusdvars/2+1] );
1152 nodeshift = curnnodes;
1155 if ( determinesize &&
i == 0 )
1156 *nnodesfromgraph1 = *
nnodes;
1160 if ( determinesize )
1166 for (j = 0; j < *
nnodes - 1; ++j)
1169 (*nedges) += *
nnodes - 1;
1170 (*colors)[*
nnodes - 1] = 8;
1174 for (j = 0; j < *
nnodes - 1; ++j)
1176 SG->e[pos[j]++] = *
nnodes - 1;
1177 SG->e[pos[*
nnodes-1]++] = j;
1191 if ( determinesize )
1192 *nusedvars = nusdvars;
1205static const char nautyname[] = {
'N',
'a',
'u',
't',
'y',
' ', NAUTYVERSIONID/10000 +
'0',
'.', (NAUTYVERSIONID%10000)/1000 +
'0',
'.', (NAUTYVERSIONID%1000)/10 +
'0',
'\0'};
1207static const char nautyname[] = {
'T',
'r',
'a',
'c',
'e',
's',
' ', NAUTYVERSIONID/10000 +
'0',
'.', (NAUTYVERSIONID%10000)/1000 +
'0',
'.', (NAUTYVERSIONID%1000)/10 +
'0',
'\0'};
1220 return "Computing Graph Automorphism Groups by Brendan D. McKay (https://users.cecs.anu.edu.au/~bdm/nauty/)";
1222 return "Computing Graph Automorphism Groups by Adolfo Piperno (https://pallini.di.uniroma1.it/)";
1267 DEFAULTOPTIONS_SPARSEGRAPH(options);
1270 static DEFAULTOPTIONS_TRACES(options);
1278 *log10groupsize = 0;
1284 options.writeautoms =
FALSE;
1286 options.defaultptn =
FALSE;
1290 options.writeautoms =
FALSE;
1291 options.userautomproc = traceshook;
1292 options.defaultptn =
FALSE;
1299 °rees, &maxdegrees, &colors, &ncolors, &success) );
1304 "Stopped symmetry computation: Symmetry graph would become too large.\n");
1311 SG_ALLOC(SG, (
size_t)
nnodes, 2 * (
size_t)(
unsigned) nedges,
"malloc");
1314 SG.nde = (size_t) (
unsigned) (2 * nedges);
1318 °rees, &maxdegrees, &colors, &ncolors, &success) );
1328 for (v = 0; v <
nnodes; ++v)
1335 for (v = 0; v <
nnodes; ++v)
1337 if ( v <
nnodes-1 && colors[v] == colors[v+1] )
1348 data_.nmaxperms = 0;
1353 data_.ntreenodes = 0;
1359 sparsenauty(&SG, lab, ptn, orbits, &options, &stats,
NULL);
1361 Traces(&SG, lab, ptn, orbits, &options, &stats,
NULL);
1374 if (
data_.nperms > 0 )
1391 *log10groupsize = (
SCIP_Real) stats.grpsize2;
1425 &colors, &ncolors, &nusedvars, &nnodesfromG1, &success) );
1442 DEFAULTOPTIONS_SPARSEGRAPH(options);
1445 static DEFAULTOPTIONS_TRACES(options);
1452 options.writeautoms =
FALSE;
1454 options.defaultptn =
FALSE;
1457 options.writeautoms =
FALSE;
1458 options.userautomproc = traceshook;
1459 options.defaultptn =
FALSE;
1465 SG_ALLOC(SG, (
size_t)
nnodes, 2 * (
size_t)(
unsigned) nedges,
"malloc");
1468 SG.nde = (size_t) (
unsigned) (2 * nedges);
1472 &colors, &ncolors, &nusedvars,
NULL, &success) );
1477#ifdef SCIP_DISABLED_CODE
1482 for (v = 0; v < SG.nv; ++v)
1487 for (v = 0; v < SG.nv; ++v)
1492 for (v = 0; v < SG.nv; ++v)
1494 for (
int w = 0;
w < SG.d[v]; ++
w)
1507 for (v = 0; v <
nnodes; ++v)
1514 for (v = 0; v <
nnodes; ++v)
1516 if ( v <
nnodes-1 && colors[v] == colors[v+1] )
1522#ifdef SCIP_DISABLED_CODE
1525 for (v = 0; v < SG.nv; ++v)
1535 data_.nmaxperms = 0;
1536 data_.maxgenerators = 0;
1540 data_.ntreenodes = 0;
1546 sparsenauty(&SG, lab, ptn, orbits, &options, &stats,
NULL);
1548 Traces(&SG, lab, ptn, orbits, &options, &stats,
NULL);
1560 if (
data_.nperms == 0 )
1564 for (
int p = 0; p <
data_.nperms; ++p)
1566 for (
int i = 0;
i < nnodesfromG1; ++
i)
1568 if (
data_.perms[p][
i] >= nnodesfromG1 )
1577 for (
int p = 0; p <
data_.nperms; ++p)
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)
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)
struct NAUTY_Data NAUTY_DATA
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 SCIP_CALL_ABORT(x)
private functions to work with algebraic expressions
power and signed power expression handlers
variable expression handler
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPensureBlockMemoryArray(scip, ptr, arraysizeptr, minsize)
#define SCIPallocClearBufferArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
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)
assert(minobj< SCIPgetCutoffbound(scip))
public methods for memory management
methods for dealing with symmetry detection graphs
struct SYM_Graph SYM_GRAPH
enum SCIP_Retcode SCIP_RETCODE
enum SYM_Symtype SYM_SYMTYPE
enum SYM_Nodetype SYM_NODETYPE