27 #include <bliss/defs.hh> 28 #include <bliss/graph.hh> 51 const unsigned int* aut
54 assert( aut != NULL );
55 assert( user_param != NULL );
58 assert( data->
scip != NULL );
59 assert( data->
perms != NULL );
78 bool isIdentity =
true;
122 SCIPdebugMsg(scip,
"Building graph with colored coefficient nodes.\n");
129 for (
int v = 0; v < matrixdata->
npermvars; ++v)
132 assert( 0 <= color && color < matrixdata->nuniquevars );
135 int node = (int) G->add_vertex((
unsigned) color);
138 (void) G->add_vertex((
unsigned) color);
143 assert( (
int) G->get_nof_vertices() == matrixdata->
npermvars );
146 for (
int c = 0; c < matrixdata->
nrhscoef; ++c)
149 assert( 0 <= color && color < matrixdata->nuniquerhs );
152 int node = (int) G->add_vertex((
unsigned) (matrixdata->
nuniquevars + color));
153 assert( node == matrixdata->
npermvars + c );
155 (void) G->add_vertex((
unsigned) (matrixdata->
nuniquevars + color));
160 assert( (
int) G->get_nof_vertices() == matrixdata->
npermvars + matrixdata->
nrhscoef );
168 if ( groupByConstraints )
169 SCIPdebugMsg(scip,
"Group intermediate nodes by constraints.\n");
171 SCIPdebugMsg(scip,
"Group intermediate nodes by variables.\n");
177 if ( groupByConstraints )
182 int* internodes = NULL;
184 for (
int l = 0; l < ninternodes; ++l)
195 int firstcolornodenumber = -1;
196 for (
int j = 0; j < matrixdata->
nmatcoef; ++j)
198 int idx = matrixdata->
matidx[j];
199 assert( 0 <= idx && idx < matrixdata->nmatcoef );
203 assert( 0 <= color && color < matrixdata->nuniquemat );
209 const int varnode = matrixdata->
matvaridx[idx];
211 assert( rhsnode < (
int) G->get_nof_vertices() );
212 assert( varnode < (
int) G->get_nof_vertices() );
217 G->add_edge((
unsigned) varnode, (
unsigned) rhsnode);
223 if ( color != oldcolor )
227 firstcolornodenumber =
nnodes;
229 oldcoef = matrixdata->
matcoef[idx];
236 if ( groupByConstraints )
240 assert( 0 <= varrhsidx && varrhsidx < ninternodes );
242 if ( internodes[varrhsidx] < firstcolornodenumber )
244 internodes[varrhsidx] = (int) G->add_vertex((
unsigned) (nusedcolors + color));
248 assert( internodes[varrhsidx] >= firstcolornodenumber );
251 if ( nnodes >= INT_MAX/2 )
257 G->add_edge((
unsigned) varnode, (
unsigned) internodes[varrhsidx]);
258 G->add_edge((
unsigned) rhsnode, (
unsigned) internodes[varrhsidx]);
282 #ifdef BLISS_PATCH_PRESENT 283 sprintf(
blissname,
"bliss %sp", bliss::version);
285 sprintf(
blissname,
"bliss %s", bliss::version);
293 return "Computing Graph Automorphism Groups by T. Junttila and P. Kaski (http://www.tcs.hut.fi/Software/bliss/)";
307 assert( scip != NULL );
308 assert( matrixdata != NULL );
309 assert( nperms != NULL );
310 assert( nmaxperms != NULL );
311 assert( perms != NULL );
312 assert( log10groupsize != NULL );
313 assert( maxgenerators >= 0 );
336 G.write_dot(
"debug.dot");
339 SCIPdebugMsg(scip,
"Symmetry detection graph has %u nodes.\n", G.get_nof_vertices());
355 G.set_splitting_heuristic(bliss::Graph::shs_f);
357 G.set_component_recursion(
false);
360 #ifdef BLISS_PATCH_PRESENT 361 G.set_search_limits(0, (
unsigned) maxgenerators);
365 G.find_automorphisms(stats,
blisshook, (
void*) &data);
367 (void) stats.print(stdout);
372 *nperms = data.nperms;
373 *nmaxperms = data.nmaxperms;
376 *log10groupsize = (
SCIP_Real) log10l(stats.get_group_size_approx());
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
const char * SYMsymmetryGetName(void)
enum SCIP_Retcode SCIP_RETCODE
const char * SYMsymmetryGetDesc(void)
SCIP_Bool SYMcanComputeSymmetry(void)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
interface for symmetry computations
static void blisshook(void *user_param, unsigned int n, const unsigned int *aut)
static char blissname[100]
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_MATRIXDATA *matrixdata, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize)
static SCIP_RETCODE fillGraphByColoredCoefficients(SCIP *scip, bliss::Graph *G, SYM_MATRIXDATA *matrixdata, int &nnodes, int &nedges, SCIP_Bool &success)