Scippy

SCIP

Solving Constraint Integer Programs

compute_symmetry_bliss.cpp File Reference

Detailed Description

interface for symmetry computations to bliss

Author
Marc Pfetsch
Thomas Rehn
Fabian Wegscheider

Definition in file compute_symmetry_bliss.cpp.

#include "compute_symmetry.h"
#include <bliss/defs.hh>
#include <bliss/graph.hh>
#include <string.h>
#include <vector>
#include <list>
#include <math.h>
#include "scip/expr_var.h"
#include "scip/expr_sum.h"
#include "scip/expr_pow.h"
#include "scip/expr.h"
#include "scip/cons_nonlinear.h"
#include "scip/cons_linear.h"
#include "scip/symmetry.h"
#include "scip/symmetry_graph.h"

Go to the source code of this file.

Data Structures

struct  BLISS_Data
 

Functions

static void blisshook (void *user_param, unsigned int n, const unsigned int *aut)
 
SCIP_Bool SYMcanComputeSymmetry (void)
 
const char * SYMsymmetryGetName (void)
 
const char * SYMsymmetryGetDesc (void)
 
const char * SYMsymmetryGetAddName (void)
 
const char * SYMsymmetryGetAddDesc (void)
 
SCIP_Bool isEdgeGroupable (SYM_GRAPH *graph, int edgeidx, SCIP_Bool groupbycons)
 
static SCIP_RETCODE addGroupedEdges (bliss::Graph *G, int commonnodeidx, int *neighbors, int *colors, int nneighbors, int *naddednodes, int *naddededges)
 
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_RETCODE SYMcomputeSymmetryGenerators (SCIP *scip, int maxgenerators, SYM_GRAPH *graph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
 
SCIP_Bool SYMcheckGraphsAreIdentical (SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
 

Function Documentation

◆ blisshook()

static void blisshook ( void *  user_param,
unsigned int  n,
const unsigned int *  aut 
)
static

callback function for bliss

Parameters
user_paramparameter supplied at call to bliss
nsize of aut vector
autautomorphism

Definition at line 72 of file compute_symmetry_bliss.cpp.

References BLISS_Data::maxgenerators, BLISS_Data::nmaxperms, BLISS_Data::nperms, BLISS_Data::npermvars, NULL, BLISS_Data::perms, BLISS_Data::restricttovars, BLISS_Data::scip, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPreallocBlockMemoryArray, SYM_SYMTYPE_PERM, and BLISS_Data::symtype.

Referenced by computeAutomorphisms().

◆ SYMcanComputeSymmetry()

SCIP_Bool SYMcanComputeSymmetry ( void  )

return whether symmetry can be computed

Definition at line 148 of file compute_symmetry_bliss.cpp.

References TRUE.

◆ SYMsymmetryGetName()

const char* SYMsymmetryGetName ( void  )

return name of external program used to compute generators

Definition at line 154 of file compute_symmetry_bliss.cpp.

◆ SYMsymmetryGetDesc()

const char* SYMsymmetryGetDesc ( void  )

return description of external program used to compute generators

Definition at line 164 of file compute_symmetry_bliss.cpp.

◆ SYMsymmetryGetAddName()

const char* SYMsymmetryGetAddName ( void  )

return name of additional external program used for computing symmetries

Definition at line 170 of file compute_symmetry_bliss.cpp.

References NULL.

◆ SYMsymmetryGetAddDesc()

const char* SYMsymmetryGetAddDesc ( void  )

return description of additional external program used to compute symmetries

Definition at line 176 of file compute_symmetry_bliss.cpp.

References NULL.

◆ isEdgeGroupable()

SCIP_Bool isEdgeGroupable ( SYM_GRAPH graph,
int  edgeidx,
SCIP_Bool  groupbycons 
)

returns whether an edge is considered in grouping process

Parameters
graphsymmetry detection graph
edgeidxindex of edge to be checked
groupbyconswhether edges are grouped by constraints

Definition at line 182 of file compute_symmetry_bliss.cpp.

References FALSE, NULL, SCIPgetSymgraphEdgeFirst(), SCIPgetSymgraphEdgeSecond(), SCIPgetSymgraphNodeType(), SCIPisSymgraphEdgeColored(), SYM_NODETYPE_CONS, and TRUE.

Referenced by SYMcomputeSymmetryGenerators().

◆ addGroupedEdges()

static SCIP_RETCODE addGroupedEdges ( bliss::Graph *  G,
int  commonnodeidx,
int *  neighbors,
int *  colors,
int  nneighbors,
int *  naddednodes,
int *  naddededges 
)
static

adds grouped edges all of which have one common endpoint to a graph

The grouping mechanism works by sorting the edges according to their color. If two edges have the same color, they share the same intermediate node, which is connected to the common node and the other endpoints of equivalent edges.

Parameters
Gpointer to graph which gets extended
commonnodeidxindex of common node in G
neighborsneighbors of common node
colorscolors of edges to neighbors
nneighborsnumber of neighbors
naddednodespointer to store number of nodes added to G
naddededgespointer to store number of edges added to G

Definition at line 240 of file compute_symmetry_bliss.cpp.

References NULL, SCIP_OKAY, and SCIPsortIntInt().

Referenced by SYMcomputeSymmetryGenerators().

◆ computeAutomorphisms()

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 
)
static

computes autormorphisms of a graph

Parameters
scipSCIP pointer
symtypetype of symmetries that need to be computed
Gpointer to graph for that automorphisms are computed
nsymvarsnumber of variables encoded in graph
maxgeneratorsmaximum number of generators to be constructed (=0 if unlimited)
permspointer to store generators as (nperms x npermvars) matrix
npermspointer to store number of permutations
nmaxpermspointer to store maximal number of permutations (needed for freeing storage)
log10groupsizepointer to store log10 of size of group
restricttovarswhether permutations shall be restricted to variables
symcodetimepointer to store the time for symmetry code

Definition at line 297 of file compute_symmetry_bliss.cpp.

References blisshook(), BLISS_Data::maxgenerators, BLISS_Data::nmaxperms, BLISS_Data::nperms, BLISS_Data::npermvars, NULL, BLISS_Data::perms, BLISS_Data::restricttovars, BLISS_Data::scip, SCIP_OKAY, SCIP_Real, SCIPgetSolvingTime(), and BLISS_Data::symtype.

Referenced by SYMcheckGraphsAreIdentical(), and SYMcomputeSymmetryGenerators().

◆ SYMcomputeSymmetryGenerators()

SCIP_RETCODE SYMcomputeSymmetryGenerators ( SCIP scip,
int  maxgenerators,
SYM_GRAPH graph,
int *  nperms,
int *  nmaxperms,
int ***  perms,
SCIP_Real log10groupsize,
SCIP_Real symcodetime 
)

compute generators of symmetry group

Parameters
scipSCIP pointer
maxgeneratorsmaximal number of generators constructed (= 0 if unlimited)
graphsymmetry detection graph
npermspointer to store number of permutations
nmaxpermspointer to store maximal number of permutations (needed for freeing storage)
permspointer to store generators as (nperms x npermvars) matrix
log10groupsizepointer to store log10 of size of group
symcodetimepointer to store the time for symmetry code

Definition at line 405 of file compute_symmetry_bliss.cpp.

References addGroupedEdges(), computeAutomorphisms(), isEdgeGroupable(), nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSymgraphEdgeColor(), SCIPgetSymgraphEdgeFirst(), SCIPgetSymgraphEdgeSecond(), SCIPgetSymgraphNConsnodes(), SCIPgetSymgraphNEdges(), SCIPgetSymgraphNNodes(), SCIPgetSymgraphNodeColor(), SCIPgetSymgraphNodeType(), SCIPgetSymgraphNVars(), SCIPgetSymgraphSymtype(), SCIPgetSymgraphVarnodeColor(), SCIPhasGraphUniqueEdgetype(), SCIPisSymgraphEdgeColored(), SCIPsortIntIntInt(), SYM_NODETYPE_CONS, SYM_NODETYPE_VAR, SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, BLISS_Data::symtype, and TRUE.

◆ SYMcheckGraphsAreIdentical()