37#include <bliss/defs.hh>
38#include <bliss/graph.hh>
75 const unsigned int* aut
90 bool isIdentity =
true;
104 for (
int j = 0; j < permlen; ++j)
106 if ( (
int) aut[j] != j )
118 for (
int j = 0; j < permlen; ++j)
156#ifdef BLISS_PATCH_PRESENT
157 return "bliss " BLISS_VERSION
"p";
159 return "bliss " BLISS_VERSION;
166 return "Computing Graph Automorphism Groups by T. Junttila and P. Kaski (users.aalto.fi/~tjunttil/bliss)";
185 SCIP_Bool groupbycons
198 if ( first < 0 && second < 0 )
204 if ( first < 0 || second < 0 )
210 if ( first >= 0 && second >= 0 )
218 else if ( first >= 0 )
263 int curcolor = colors[0];
265 for (
int e = 1; e < nneighbors; ++e)
268 if ( colors[e] != curcolor )
270 int internode = (*G).add_vertex(curcolor);
271 (*G).add_edge(commonnodeidx, internode);
274 for (
int f = curstart; f < e; ++f)
275 (*G).add_edge(internode, neighbors[f]);
276 *naddededges += e - curstart + 1;
278 curcolor = colors[e];
284 int internode = (*G).add_vertex(curcolor);
285 (*G).add_edge(commonnodeidx, internode);
288 for (
int f = curstart; f < nneighbors; ++f)
289 (*G).add_edge(internode, neighbors[f]);
290 *naddededges += nneighbors - curstart + 1;
307 SCIP_Real* log10groupsize,
308 SCIP_Bool restricttovars,
309 SCIP_Real* symcodetime
320 assert( maxgenerators >= 0 );
344 G->set_splitting_heuristic(bliss::Graph::shs_f);
346 G->set_component_recursion(
false);
349#if BLISS_VERSION_MAJOR >= 1 || BLISS_VERSION_MINOR >= 76
351 auto reportglue = [&](
unsigned int n,
const unsigned int* aut) {
357 return (maxgenerators != 0 && data.
nperms >= maxgenerators);
361 G->find_automorphisms(stats, reportglue, term);
365#ifdef BLISS_PATCH_PRESENT
369 G->set_search_limits(0, (
unsigned) maxgenerators);
373 G->find_automorphisms(stats,
blisshook, (
void*) &data);
378 (void) stats.print(stdout);
399 *log10groupsize = (
SCIP_Real) log10l(stats.get_group_size_approx());
413 SCIP_Real* log10groupsize,
414 SCIP_Real* symcodetime
452 nvarnodestoadd = nsymvars;
456 nvarnodestoadd = 2 * nsymvars;
459 for (
int v = 0; v < nvarnodestoadd; ++v)
464 int node = (int) G.add_vertex((
unsigned) color);
467 (void) G.add_vertex((
unsigned) color);
475 for (
int v = 0; v < nsymnodes; ++v)
480 int node = (int) G.add_vertex((
unsigned) color);
481 assert( node == nvarnodestoadd + v );
483 (void) G.add_vertex((
unsigned) color);
496 int* groupfirsts =
NULL;
497 int* groupseconds =
NULL;
498 int* groupcolors =
NULL;
505 for (
int e = 0; e < nsymedges; ++e)
513 first += nvarnodestoadd;
515 second = -second - 1;
517 second += nvarnodestoadd;
529 groupfirsts[ngroupedges] = first;
530 groupseconds[ngroupedges] = second;
534 groupfirsts[ngroupedges] = second;
535 groupseconds[ngroupedges] = first;
550 int inter = G.add_vertex((
unsigned) color);
552 G.add_edge(first, inter);
553 G.add_edge(second, inter);
559 G.add_edge(first, second);
565 if ( ngroupedges > 0 )
571 int firstnodeidx = groupfirsts[0];
575 for (
int i = 1;
i < ngroupedges; ++
i)
578 if ( groupfirsts[
i] != firstnodeidx )
581 &groupcolors[firstidx],
i - firstidx, &naddednodes, &naddededges) );
584 firstnodeidx = groupfirsts[
i];
587 nedges += naddededges;
593 &groupcolors[firstidx], ngroupedges - firstidx, &naddednodes, &naddededges) );
596 nedges += naddededges;
607 for (
int v = 0; v < nsymvars; ++v)
608 G.add_edge(v, v + nsymvars);
621 perms, nperms, nmaxperms, log10groupsize,
TRUE, symcodetime) );
634 int* nvarused1 =
NULL;
635 int* nvarused2 =
NULL;
636 int* varlabel =
NULL;
678 if ( nvarused1[
i] != nvarused2[
i] )
688 if ( nvarused1[
i] > 0 || nvarused1[
i % G1->
nsymvars] > 0 )
689 varlabel[
i] = nusedvars++;
698 for (
i = 0;
i < nusedvars; ++
i)
710 first = varlabel[-first - 1];
712 first = nusedvars + first;
716 second = varlabel[-second - 1];
718 second = nusedvars + second;
724 G.add_edge(first, inter);
725 G.add_edge(second, inter);
728 G.add_edge(first, second);
737 if ( nvarused1[
i] > 0 || nvarused1[
i + G1->
nsymvars])
738 G.add_edge(varlabel[
i], varlabel[
i + G1->
nsymvars]);
746 int nodeshift = G.get_nof_vertices();
747 for (
i = 0;
i < nusedvars; ++
i)
759 first = nodeshift + varlabel[-first - 1];
761 first = nodeshift + nusedvars + first;
765 second = nodeshift + varlabel[-second - 1];
767 second = nodeshift + nusedvars + second;
773 G.add_edge(first, inter);
774 G.add_edge(second, inter);
777 G.add_edge(first, second);
786 if ( nvarused2[
i] > 0 || nvarused2[
i + G2->
nsymvars])
787 G.add_edge(nodeshift + varlabel[
i], nodeshift + varlabel[
i + G2->
nsymvars]);
798 SCIP_Real log10groupsize;
799 int n = G.get_nof_vertices();
800 int nnodesfromG1 = nusedvars + G1->
nnodes;
801 SCIP_Real symcodetime = 0.0;
804 &perms, &nperms, &nmaxperms, &log10groupsize,
FALSE, &symcodetime) );
809 SCIP_Bool success =
FALSE;
810 for (
int p = 0; p < nperms && ! success; ++p)
812 for (
i = 0;
i < nnodesfromG1; ++
i)
814 if ( perms[p][
i] >= nnodesfromG1 )
822 for (
int p = 0; p < nperms; ++p)
interface for symmetry computations
SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
const char * SYMsymmetryGetName(void)
const char * SYMsymmetryGetAddName(void)
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_GRAPH *graph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
static SCIP_RETCODE computeAutomorphisms(SCIP *scip, SYM_SYMTYPE symtype, bliss::Graph *G, int nsymvars, int maxgenerators, int ***perms, int *nperms, int *nmaxperms, SCIP_Real *log10groupsize, SCIP_Bool restricttovars, SCIP_Real *symcodetime)
SCIP_Bool SYMcanComputeSymmetry(void)
static void blisshook(void *user_param, unsigned int n, const unsigned int *aut)
static SCIP_RETCODE addGroupedEdges(bliss::Graph *G, int commonnodeidx, int *neighbors, int *colors, int nneighbors, int *naddednodes, int *naddededges)
const char * SYMsymmetryGetDesc(void)
SCIP_Bool isEdgeGroupable(SYM_GRAPH *graph, int edgeidx, SCIP_Bool groupbycons)
const char * SYMsymmetryGetAddDesc(void)
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
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#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)
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))
methods for handling symmetries
methods for dealing with symmetry detection graphs
enum SCIP_Retcode SCIP_RETCODE
enum SYM_Symtype SYM_SYMTYPE
enum SYM_Nodetype SYM_NODETYPE