SCIP Doxygen Documentation
Loading...
Searching...
No Matches
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
struct  NAUTY_Data

Macros

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

Functions

static void sassyhook (void *user_param, int n, const int *aut, int nsupp, const int *suppa)
static void nautyterminationhook (graph *g, int *lab, int *ptn, int level, int numcells, int tc, int code, int m, int n)
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_Bool canterminateearly)
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 struct NAUTY_Data nautydata_
static const char nautyname [] = {'N', 'a', 'u', 't', 'y', ' ', NAUTYVERSIONID/10000 + '0', '.', (NAUTYVERSIONID%10000)/1000 + '0', '.', (NAUTYVERSIONID%1000)/10 + '0', '\0'}

Macro Definition Documentation

◆ NAUTY

#define NAUTY

Definition at line 38 of file compute_symmetry_sassy_nauty.cpp.

◆ STR

#define STR ( x)
Value:
#x

Definition at line 289 of file compute_symmetry_sassy_nauty.cpp.

◆ XSTR

#define XSTR ( x)
Value:
SCIP_VAR ** x
#define STR(x)
Definition lpi_msk.c:754

Definition at line 290 of file compute_symmetry_sassy_nauty.cpp.

Referenced by SYMsymmetryGetAddName().

Function Documentation

◆ sassyhook()

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 128 of file compute_symmetry_sassy_nauty.cpp.

References assert(), 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().

◆ nautyterminationhook()

void nautyterminationhook ( graph * g,
int * lab,
int * ptn,
int level,
int numcells,
int tc,
int code,
int m,
int n )
static

callback function for nauty to terminate early

Parameters
gsparse graph for nauty
lablabels of node
ptnarray indicating change of set in node parition of graph
levellevel of current node in nauty's tree
numcellsnumber of cells in current partition
tcindex of target cells in lab if children need to be explored
codecode produced by refinement and vertex-invariant procedures
mnumber of edges in the graph
nnumber of nodes in the graph

Definition at line 214 of file compute_symmetry_sassy_nauty.cpp.

References FALSE, nautydata_, NULL, SCIP_Bool, SCIP_VERBLEVEL_MINIMAL, SCIPverbMessage(), and TRUE.

◆ SYMcanComputeSymmetry()

SCIP_Bool SYMcanComputeSymmetry ( void )

return whether symmetry can be computed

Definition at line 261 of file compute_symmetry_sassy_nauty.cpp.

References SCIP_Bool, and TRUE.

Referenced by determineSymmetry(), and SCIPincludePropSymmetry().

◆ SYMsymmetryGetName()

const char * SYMsymmetryGetName ( void )

return name of external program used to compute generators

Definition at line 274 of file compute_symmetry_sassy_nauty.cpp.

References nautyname.

Referenced by SCIPincludePropSymmetry().

◆ SYMsymmetryGetDesc()

const char * SYMsymmetryGetDesc ( void )

return description of external program used to compute generators

Definition at line 280 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 293 of file compute_symmetry_sassy_nauty.cpp.

References NULL, and XSTR.

Referenced by SCIPincludePropSymmetry().

◆ SYMsymmetryGetAddDesc()

const char * SYMsymmetryGetAddDesc ( void )

return description of additional external program used to compute symmetries

Definition at line 299 of file compute_symmetry_sassy_nauty.cpp.

References NULL.

Referenced by SCIPincludePropSymmetry().

◆ computeAutomorphisms()

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_Bool canterminateearly )
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
canterminateearlywhether we allow to interrupt symmetry detection early (e.g., because of iteration limits)

Definition at line 306 of file compute_symmetry_sassy_nauty.cpp.

References assert(), FALSE, NAUTY_Data::maxgenerators, SYMMETRY_Data::maxgenerators, nautydata_, nautyterminationhook(), NAUTY_Data::nmaxperms, SYMMETRY_Data::nmaxperms, NAUTY_Data::nperms, SYMMETRY_Data::nperms, SYMMETRY_Data::npermvars, NULL, NAUTY_Data::perms, SYMMETRY_Data::perms, SYMMETRY_Data::restricttovars, sassyhook(), SYMMETRY_Data::scip, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetIntParam(), 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 442 of file compute_symmetry_sassy_nauty.cpp.

References addGroupedEdges(), assert(), computeAutomorphisms(), computeAutomorphisms(), FALSE, i, isEdgeGroupable(), SYMMETRY_Data::maxgenerators, SYMMETRY_Data::nmaxperms, nnodes, SYMMETRY_Data::nperms, NULL, SYMMETRY_Data::perms, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, 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, SYMbuildSassyGraph(), and TRUE.

Referenced by computeSymmetryGroup().

◆ SYMcheckGraphsAreIdentical()

Variable Documentation

◆ nautydata_

struct NAUTY_Data nautydata_
static

static data for nauty callback

Definition at line 119 of file compute_symmetry_sassy_nauty.cpp.

Referenced by computeAutomorphisms(), and nautyterminationhook().

◆ nautyname

const char nautyname[] = {'N', 'a', 'u', 't', 'y', ' ', NAUTYVERSIONID/10000 + '0', '.', (NAUTYVERSIONID%10000)/1000 + '0', '.', (NAUTYVERSIONID%1000)/10 + '0', '\0'}
static

nauty/traces version string

Definition at line 268 of file compute_symmetry_sassy_nauty.cpp.