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 "compute_symmetry.h"
#include "nauty/nauty.h"
#include "nauty/nausparse.h"
#include "build_dejavu_graph.h"
#include "dejavu/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"
#include "tinycthread/tinycthread.h"

Go to the source code of this file.

Data Structures
struct	SYMMETRY_Data

struct	NAUTY_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)

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, dejavu::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 _Thread_local 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 37 of file compute_symmetry_sassy_nauty.cpp.

◆ STR

#define STR ( x ) #x

Definition at line 256 of file compute_symmetry_sassy_nauty.cpp.

◆ XSTR

#define XSTR ( x ) STR(x)

Definition at line 257 of file compute_symmetry_sassy_nauty.cpp.

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_param	parameter supplied at call to sassy
n	dimension of permutations
aut	permutation
nsupp	support size
suppa	support list

Definition at line 115 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().

◆ nautyterminationhook()

static 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

g	sparse graph for nauty
lab	labels of node
ptn	array indicating change of set in node parition of graph
level	level of current node in nauty's tree
numcells	number of cells in current partition
tc	index of target cells in lab if children need to be explored
code	code produced by refinement and vertex-invariant procedures
m	number of edges in the graph
n	number of nodes in the graph

Definition at line 201 of file compute_symmetry_sassy_nauty.cpp.

References NAUTY_Data::maxlevel, nautydata_, NULL, NAUTY_Data::scip, SCIP_VERBLEVEL_MINIMAL, and SCIPverbMessage().

Referenced by computeAutomorphisms().

◆ SYMcanComputeSymmetry()

SCIP_Bool SYMcanComputeSymmetry ( void )

return whether symmetry can be computed

Definition at line 228 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 241 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 247 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 260 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 266 of file compute_symmetry_sassy_nauty.cpp.

References NULL.

Referenced by SCIPincludePropSymmetry().

◆ computeAutomorphisms()

static SCIP_RETCODE computeAutomorphisms	(	SCIP *	scip,
		SYM_SYMTYPE	symtype,
		dejavu::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

scip	SCIP pointer
symtype	type of symmetries that need to be computed
G	pointer to graph for that automorphisms are computed
nsymvars	number of variables encoded in graph
maxgenerators	maximum number of generators to be constructed (=0 if unlimited)
perms	pointer to store generators as (nperms x npermvars) matrix
nperms	pointer to store number of permutations
nmaxperms	pointer to store maximal number of permutations (needed for freeing storage)
log10groupsize	pointer to store log10 of size of group
restricttovars	whether permutations shall be restricted to variables
symcodetime	pointer to store the time for symmetry code
canterminateearly	whether we allow to interrupt symmetry detection early (e.g., because of iteration limits)

Definition at line 273 of file compute_symmetry_sassy_nauty.cpp.

References FALSE, SYMMETRY_Data::maxgenerators, NAUTY_Data::maxgenerators, NAUTY_Data::maxlevel, nautydata_, nautyterminationhook(), SYMMETRY_Data::nmaxperms, NAUTY_Data::nmaxperms, SYMMETRY_Data::nperms, NAUTY_Data::nperms, SYMMETRY_Data::npermvars, NULL, SYMMETRY_Data::perms, NAUTY_Data::perms, SYMMETRY_Data::restricttovars, sassyhook(), SYMMETRY_Data::scip, NAUTY_Data::scip, 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

scip	SCIP pointer
maxgenerators	maximal number of generators constructed (= 0 if unlimited)
symgraph	symmetry detection graph
nperms	pointer to store number of permutations
nmaxperms	pointer to store maximal number of permutations (needed for freeing storage)
perms	pointer to store permutation generators as (nperms x npermvars) matrix
log10groupsize	pointer to store log10 of size of group
symcodetime	pointer to store the time for symmetry code

Definition at line 410 of file compute_symmetry_sassy_nauty.cpp.

References addGroupedEdges(), computeAutomorphisms(), FALSE, isEdgeGroupable(), SYMMETRY_Data::maxgenerators, SYMMETRY_Data::nmaxperms, nnodes, SYMMETRY_Data::nperms, NULL, SYMMETRY_Data::perms, SCIP_Bool, 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, SYMbuildDejavuGraph(), 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

scip	SCIP pointer
symtype	type of symmetries to be checked
G1	first graph
G2	second graph

Definition at line 452 of file compute_symmetry_sassy_nauty.cpp.

References computeAutomorphisms(), SYM_Graph::edgefirst, SYM_Graph::edgesecond, FALSE, SYM_Graph::nconsnodes, SYM_Graph::nedges, SYMMETRY_Data::nmaxperms, nnodes, SYM_Graph::nnodes, SYM_Graph::nopnodes, SYMMETRY_Data::nperms, SYM_Graph::nsymvars, NULL, SYM_Graph::nvalnodes, SYMMETRY_Data::perms, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_Real, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPgetSymgraphEdgeColor(), SCIPgetSymgraphNodeColor(), SCIPgetSymgraphSymtype(), SCIPisSymgraphEdgeColored(), SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, SYMbuildDejavuGraphCheck(), and TRUE.

Referenced by checkSymmetriesAreSymmetries().

Variable Documentation

◆ nautydata_

_Thread_local struct NAUTY_Data nautydata_

static

static data for nauty callback

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

Referenced by SYMsymmetryGetName().

SCIP

Detailed Description

Data Structures

Macros

Functions

Variables

Macro Definition Documentation

◆ NAUTY

◆ STR

◆ XSTR

Function Documentation

◆ sassyhook()

◆ nautyterminationhook()

◆ SYMcanComputeSymmetry()

◆ SYMsymmetryGetName()

◆ SYMsymmetryGetDesc()

◆ SYMsymmetryGetAddName()

◆ SYMsymmetryGetAddDesc()

◆ computeAutomorphisms()

◆ SYMcomputeSymmetryGenerators()

◆ SYMcheckGraphsAreIdentical()

Variable Documentation

◆ nautydata_

◆ nautyname