Scippy

SCIP

Solving Constraint Integer Programs

compute_symmetry_sassy_nauty.cpp File Reference

Detailed Description

interface for symmetry computations to sassy as a preprocessor to nauty

Author
Marc Pfetsch
Gioni Mexi
Christopher Hojny

Definition in file compute_symmetry_sassy_nauty.cpp.

#include "build_sassy_graph.h"
#include "compute_symmetry.h"
#include "nauty/nauty.h"
#include "nauty/nausparse.h"
#include <sassy/preprocessor.h>
#include "sassy/tools/nauty_converter.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/scip_mem.h"
#include "scip/symmetry_graph.h"

Go to the source code of this file.

Data Structures

struct  SYMMETRY_Data
 

Macros

#define NAUTY
 
#define STR(x)   #x
 
#define XSTR(x)   STR(x)
 

Functions

static void sassyhook (void *user_param, int n, const int *aut, int nsupp, const int *suppa)
 
SCIP_Bool SYMcanComputeSymmetry (void)
 
const char * SYMsymmetryGetName (void)
 
const char * SYMsymmetryGetDesc (void)
 
const char * SYMsymmetryGetAddName (void)
 
const char * SYMsymmetryGetAddDesc (void)
 
static SCIP_RETCODE computeAutomorphisms (SCIP *scip, SYM_SYMTYPE symtype, sassy::static_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 *symgraph, 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)
 

Variables

static TLS_ATTR char nautyname [20]
 

Macro Definition Documentation

◆ NAUTY

#define NAUTY

Definition at line 38 of file compute_symmetry_sassy_nauty.cpp.

◆ STR

#define STR (   x)    #x

Definition at line 225 of file compute_symmetry_sassy_nauty.cpp.

◆ XSTR

#define XSTR (   x)    STR(x)

Definition at line 226 of file compute_symmetry_sassy_nauty.cpp.

Referenced by SYMsymmetryGetAddName().

Function Documentation

◆ sassyhook()

static void sassyhook ( void *  user_param,
int  n,
const int *  aut,
int  nsupp,
const int *  suppa 
)
static

callback function for sassy

Parameters
user_paramparameter supplied at call to sassy
ndimension of permutations
autpermutation
nsuppsupport size
suppasupport list

Definition at line 111 of file compute_symmetry_sassy_nauty.cpp.

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

Referenced by computeAutomorphisms().

◆ SYMcanComputeSymmetry()

SCIP_Bool SYMcanComputeSymmetry ( void  )

return whether symmetry can be computed

Definition at line 195 of file compute_symmetry_sassy_nauty.cpp.

References TRUE.

Referenced by determineSymmetry(), and SCIPincludePropSymmetry().

◆ SYMsymmetryGetName()

const char* SYMsymmetryGetName ( void  )

return name of external program used to compute generators

Definition at line 204 of file compute_symmetry_sassy_nauty.cpp.

References nautyname, and SCIPsnprintf().

Referenced by SCIPincludePropSymmetry().

◆ SYMsymmetryGetDesc()

const char* SYMsymmetryGetDesc ( void  )

return description of external program used to compute generators

Definition at line 216 of file compute_symmetry_sassy_nauty.cpp.

Referenced by SCIPincludePropSymmetry().

◆ SYMsymmetryGetAddName()

const char* SYMsymmetryGetAddName ( void  )

return name of additional external program used for computing symmetries

Definition at line 229 of file compute_symmetry_sassy_nauty.cpp.

References XSTR.

Referenced by SCIPincludePropSymmetry().

◆ SYMsymmetryGetAddDesc()

const char* SYMsymmetryGetAddDesc ( void  )

return description of additional external program used to compute symmetries

Definition at line 235 of file compute_symmetry_sassy_nauty.cpp.

Referenced by SCIPincludePropSymmetry().

◆ computeAutomorphisms()

static SCIP_RETCODE computeAutomorphisms ( SCIP scip,
SYM_SYMTYPE  symtype,
sassy::static_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 242 of file compute_symmetry_sassy_nauty.cpp.

References FALSE, SYMMETRY_Data::maxgenerators, SYMMETRY_Data::nmaxperms, SYMMETRY_Data::nperms, SYMMETRY_Data::npermvars, NULL, SYMMETRY_Data::perms, SYMMETRY_Data::restricttovars, sassyhook(), SYMMETRY_Data::scip, SCIP_OKAY, SCIP_Real, SCIPgetSolvingTime(), and SYMMETRY_Data::symtype.

Referenced by SYMcheckGraphsAreIdentical(), and SYMcomputeSymmetryGenerators().

◆ SYMcomputeSymmetryGenerators()

SCIP_RETCODE SYMcomputeSymmetryGenerators ( SCIP scip,
int  maxgenerators,
SYM_GRAPH symgraph,
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)
symgraphsymmetry detection graph
npermspointer to store number of permutations
nmaxpermspointer to store maximal number of permutations (needed for freeing storage)
permspointer to store permutation 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 367 of file compute_symmetry_sassy_nauty.cpp.

References computeAutomorphisms(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPgetSymgraphNVars(), SCIPgetSymgraphSymtype(), SYMbuildSassyGraph(), and TRUE.

Referenced by computeSymmetryGroup().

◆ SYMcheckGraphsAreIdentical()

SCIP_Bool SYMcheckGraphsAreIdentical ( SCIP scip,
SYM_SYMTYPE  symtype,
SYM_GRAPH G1,
SYM_GRAPH G2 
)

returns whether two given graphs are identical

Parameters
scipSCIP pointer
symtypetype of symmetries to be checked
G1first graph
G2second graph

Definition at line 409 of file compute_symmetry_sassy_nauty.cpp.

References computeAutomorphisms(), FALSE, SYMMETRY_Data::nmaxperms, nnodes, SYMMETRY_Data::nperms, SYMMETRY_Data::perms, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_Real, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetSymgraphSymtype(), SYMbuildSassyGraphCheck(), and TRUE.

Referenced by checkSymmetriesAreSymmetries().

Variable Documentation

◆ nautyname

TLS_ATTR char nautyname[20]
static

static variable for holding the name of nauty

Definition at line 201 of file compute_symmetry_sassy_nauty.cpp.

Referenced by SYMsymmetryGetName().