Detailed Description

interface for symmetry computations to nauty/traces

Author: Marc Pfetsch

Definition in file compute_symmetry_nauty.c.

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

Go to the source code of this file.

Data Structures
struct	NAUTY_Data

Macros
#define	NAUTY

Functions
static	SCIP_DECL_HASHGETKEY (SYMhashGetKeyOptype)

static	SCIP_DECL_HASHKEYEQ (SYMhashKeyEQOptype)

static	SCIP_DECL_HASHKEYVAL (SYMhashKeyValOptype)

static	SCIP_DECL_HASHGETKEY (SYMhashGetKeyConsttype)

static	SCIP_DECL_HASHKEYEQ (SYMhashKeyEQConsttype)

static	SCIP_DECL_HASHKEYVAL (SYMhashKeyValConsttype)

static	SCIP_DECL_HASHGETKEY (SYMhashGetKeyRhstype)

static	SCIP_DECL_HASHKEYEQ (SYMhashKeyEQRhstype)

static	SCIP_DECL_HASHKEYVAL (SYMhashKeyValRhstype)

static void	nautyhook (int count, int p, int orbits, int numorbits, int stabvertex, int n)

static SCIP_RETCODE	determineGraphSize (SCIP scip, SYM_MATRIXDATA matrixdata, SYM_EXPRDATA exprdata, int nnodes, int nedges, int nlinearnodes, int nnonlinearnodes, int nlinearedges, int nnonlinearedges, int degrees, int maxdegrees, SCIP_Bool *success)

static SCIP_RETCODE	fillGraphByConss (SCIP scip, sparsegraph SG, SYM_MATRIXDATA matrixdata, SYM_EXPRDATA exprdata, int nnodes, int nedges, int nlinearnodes, int nnonlinearnodes, int nlinearedges, int nnonlinearedges, int degrees, int colors, int *nusedcolors)

SCIP_Bool	SYMcanComputeSymmetry (void)

const char *	SYMsymmetryGetName (void)

const char *	SYMsymmetryGetDesc (void)

const char *	SYMsymmetryGetAddName (void)

const char *	SYMsymmetryGetAddDesc (void)

SCIP_RETCODE	SYMcomputeSymmetryGenerators (SCIP scip, int maxgenerators, SYM_MATRIXDATA matrixdata, SYM_EXPRDATA exprdata, int nperms, int nmaxperms, int *perms, SCIP_Real log10groupsize, SCIP_Real *symcodetime)

Variables
static struct NAUTY_Data	data_

static const char	nautyname [] = "Nauty "NAUTYVERSION

Macro Definition Documentation

◆ NAUTY

#define NAUTY

Definition at line 35 of file compute_symmetry_nauty.c.

Function Documentation

◆ SCIP_DECL_HASHGETKEY() [1/3]

static SCIP_DECL_HASHGETKEY ( SYMhashGetKeyOptype )

static

gets the key of the given element

Definition at line 82 of file compute_symmetry_nauty.c.

◆ SCIP_DECL_HASHKEYEQ() [1/3]

static SCIP_DECL_HASHKEYEQ ( SYMhashKeyEQOptype )

static

returns TRUE iff both keys are equal

Compare the types of two operators according to their name, level and, in case of power, exponent.

Definition at line 92 of file compute_symmetry_nauty.c.

References SYM_Optype::expr, FALSE, SYM_Optype::level, SCIPexprGetHdlr(), SCIPgetExponentExprPow(), SCIPisExprPower(), and TRUE.

◆ SCIP_DECL_HASHKEYVAL() [1/3]

static SCIP_DECL_HASHKEYVAL ( SYMhashKeyValOptype )

static

returns the hash value of the key

Definition at line 118 of file compute_symmetry_nauty.c.

References SYM_Optype::expr, SYM_Optype::level, NULL, SCIP_Real, SCIPexprGetHdlr(), SCIPexprhdlrGetName(), SCIPgetExponentExprPow(), SCIPhashThree, SCIPisExprPower(), and SCIPrealHashCode().

◆ SCIP_DECL_HASHGETKEY() [2/3]

static SCIP_DECL_HASHGETKEY ( SYMhashGetKeyConsttype )

static

gets the key of the given element

Definition at line 140 of file compute_symmetry_nauty.c.

◆ SCIP_DECL_HASHKEYEQ() [2/3]

static SCIP_DECL_HASHKEYEQ ( SYMhashKeyEQConsttype )

static

returns TRUE iff both keys are equal

Compare two constants according to their values.

Definition at line 150 of file compute_symmetry_nauty.c.

References SCIP_Bool, and SYM_Consttype::value.

◆ SCIP_DECL_HASHKEYVAL() [2/3]

static SCIP_DECL_HASHKEYVAL ( SYMhashKeyValConsttype )

static

returns the hash value of the key

Definition at line 163 of file compute_symmetry_nauty.c.

References SCIPrealHashCode(), and SYM_Consttype::value.

◆ SCIP_DECL_HASHGETKEY() [3/3]

static SCIP_DECL_HASHGETKEY ( SYMhashGetKeyRhstype )

static

gets the key of the given element

Definition at line 176 of file compute_symmetry_nauty.c.

◆ SCIP_DECL_HASHKEYEQ() [3/3]

static SCIP_DECL_HASHKEYEQ ( SYMhashKeyEQRhstype )

static

returns TRUE iff both keys are equal

Compare two constraint sides according to lhs and rhs.

Definition at line 186 of file compute_symmetry_nauty.c.

References FALSE, SYM_Rhstype::lhs, SYM_Rhstype::rhs, and SCIP_Bool.

◆ SCIP_DECL_HASHKEYVAL() [3/3]

static SCIP_DECL_HASHKEYVAL ( SYMhashKeyValRhstype )

static

returns the hash value of the key

Definition at line 202 of file compute_symmetry_nauty.c.

References SYM_Rhstype::lhs, SYM_Rhstype::rhs, SCIPhashTwo, and SCIPrealHashCode().

◆ nautyhook()

static void nautyhook	(	int	count,
		int *	p,
		int *	orbits,
		int	numorbits,
		int	stabvertex,
		int	n
	)

static

callback function for nauty

Parameters

count	ID of this generator
p	generator (permutation) that nauty found
orbits	orbits generated by the group found so far
numorbits	number of orbits
stabvertex	stabilizing node
n	number of nodes in the graph

Definition at line 218 of file compute_symmetry_nauty.c.

References data_, FALSE, NAUTY_Data::maxgenerators, NAUTY_Data::nmaxperms, NAUTY_Data::nperms, NAUTY_Data::npermvars, NULL, NAUTY_Data::perms, NAUTY_Data::scip, SCIP_Bool, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPduplicateBlockMemoryArray, SCIPreallocBlockMemoryArray, and TRUE.

Referenced by SYMcomputeSymmetryGenerators().

◆ determineGraphSize()

static SCIP_RETCODE determineGraphSize	(	SCIP *	scip,
		SYM_MATRIXDATA *	matrixdata,
		SYM_EXPRDATA *	exprdata,
		int *	nnodes,
		int *	nedges,
		int *	nlinearnodes,
		int *	nnonlinearnodes,
		int *	nlinearedges,
		int *	nnonlinearedges,
		int **	degrees,
		int *	maxdegrees,
		SCIP_Bool *	success
	)

static

determine number of nodes and edges

Parameters

scip	SCIP instance
matrixdata	data for MIP matrix
exprdata	data for nonlinear constraints
nnodes	pointer to store the total number of nodes in graph
nedges	pointer to store the total number of edges in graph
nlinearnodes	pointer to store the number of internal nodes for linear constraints
nnonlinearnodes	pointer to store the number of internal nodes for nonlinear constraints
nlinearedges	pointer to store the number of edges for linear constraints
nnonlinearedges	pointer to store the number of edges for nonlinear constraints
degrees	pointer to store the degrees of the nodes
maxdegrees	pointer to store the maximal size of the degree array
success	pointer to store whether the construction was successful

Definition at line 356 of file compute_symmetry_nauty.c.

References FALSE, SYM_Matrixdata::matcoef, SYM_Matrixdata::matcoefcolors, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, nnodes, NAUTY_Data::npermvars, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, NULL, SYM_Exprdata::nuniquecoefs, SYM_Exprdata::nuniqueconstants, SYM_Matrixdata::nuniquemat, SYM_Exprdata::nuniqueoperators, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_EXPRITER_LEAVEEXPR, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPensureBlockMemoryArray, SCIPexprGetNChildren(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterGetParentDFS(), SCIPexpriterGetStageDFS(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPgetConstantExprSum(), SCIPgetExprNonlinear(), SCIPgetNVars(), SCIPgetProbvarLinearSum(), SCIPgetVarExprVar(), SCIPisEQ(), SCIPisExprSum(), SCIPisExprVar(), SCIPvarGetProbindex(), SCIPvarIsActive(), and TRUE.

Referenced by SYMcomputeSymmetryGenerators().

◆ fillGraphByConss()

static SCIP_RETCODE fillGraphByConss	(	SCIP *	scip,
		sparsegraph *	SG,
		SYM_MATRIXDATA *	matrixdata,
		SYM_EXPRDATA *	exprdata,
		int	nnodes,
		int	nedges,
		int	nlinearnodes,
		int	nnonlinearnodes,
		int	nlinearedges,
		int	nnonlinearedges,
		int *	degrees,
		int *	colors,
		int *	nusedcolors
	)

static

Construct linear and nonlinear part of colored graph for symmetry computations

Construct linear graph:

Each variable gets a different node.
Each constraint gets a different node.
Each matrix coefficient gets a different node that is connected to the two nodes corresponding to the respective constraint and variable.
Each different variable, rhs, matrix coefficient gets a different color that is attached to the corresponding entries.

Construct nonlinear graph:
Each node of the expression trees gets a different node.
Each coefficient of a sum expression gets its own node connected to the node of the corresponding child.
Each constraint (with lhs and (!) rhs) gets its own node connected to the corresponding node of the root expression.

Note: : In contrast to the linear part, lhs and rhs are treated together here, so that each unique combination of lhs and rhs gets its own node. This makes the implementation a lot simpler with the small downside, that different formulations of the same constraints would not be detected as equivalent, e.g. for 0 <= x1 + x2 <= 1 0 <= x3 + x4 x3 + x4 <= 1 there would be no symmetry between (x1,x2) and (x3,x4) detected.

Each different constraint (sides), sum-expression coefficient, constant and operator type gets a different color that is attached to the corresponding entries.

Parameters

scip	SCIP instance
SG	graph to be constructed
matrixdata	data for MIP matrix
exprdata	data for nonlinear constraints
nnodes	total number of nodes in graph
nedges	total number of edges in graph
nlinearnodes	number of intermediate nodes for linear constraints
nnonlinearnodes	number of intermediate nodes for nonlinear constraints
nlinearedges	number of intermediate edges for linear constraints
nnonlinearedges	number of intermediate edges for nonlinear constraints
degrees	array with the degrees of the nodes
colors	array with colors of nodes on output
nusedcolors	pointer to store number of used colors in the graph so far

Definition at line 866 of file compute_symmetry_nauty.c.

References SYM_Optype::expr, FALSE, SYM_Optype::level, SYM_Rhstype::lhs, SYM_Matrixdata::matcoef, SYM_Matrixdata::matcoefcolors, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, nnodes, NAUTY_Data::npermvars, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, NULL, SYM_Exprdata::nuniquecoefs, SYM_Exprdata::nuniqueconstants, SYM_Matrixdata::nuniquemat, SYM_Exprdata::nuniqueoperators, SYM_Matrixdata::nuniquerhs, SYM_Matrixdata::nuniquevars, SYM_Matrixdata::permvarcolors, SYM_Rhstype::rhs, SYM_Matrixdata::rhscoefcolors, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_EXPRITER_LEAVEEXPR, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPensureBlockMemoryArray, SCIPexprGetNChildren(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterGetParentDFS(), SCIPexpriterGetStageDFS(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPfindConshdlr(), SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetExprNonlinear(), SCIPgetLhsNonlinear(), SCIPgetNVars(), SCIPgetProbvarLinearSum(), SCIPgetRhsNonlinear(), SCIPgetValueExprValue(), SCIPgetVarExprVar(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPisEQ(), SCIPisExprSum(), SCIPisExprValue(), SCIPisExprVar(), SCIPvarGetProbindex(), SCIPvarIsActive(), TRUE, and SYM_Consttype::value.

Referenced by SYMcomputeSymmetryGenerators().

◆ SYMcanComputeSymmetry()

SCIP_Bool SYMcanComputeSymmetry ( void )

return whether symmetry can be computed

Definition at line 1557 of file compute_symmetry_nauty.c.

References TRUE.

◆ SYMsymmetryGetName()

const char* SYMsymmetryGetName ( void )

return name of external program used to compute generators

Definition at line 1570 of file compute_symmetry_nauty.c.

References nautyname.

◆ SYMsymmetryGetDesc()

const char* SYMsymmetryGetDesc ( void )

return description of external program used to compute generators

Definition at line 1576 of file compute_symmetry_nauty.c.

◆ SYMsymmetryGetAddName()

const char* SYMsymmetryGetAddName ( void )

return name of additional external program used for computing symmetries

Definition at line 1586 of file compute_symmetry_nauty.c.

References NULL.

◆ SYMsymmetryGetAddDesc()

const char* SYMsymmetryGetAddDesc ( void )

return description of additional external program used to compute symmetries

Definition at line 1592 of file compute_symmetry_nauty.c.

References NULL.

◆ SYMcomputeSymmetryGenerators()

SCIP_RETCODE SYMcomputeSymmetryGenerators	(	SCIP *	scip,
		int	maxgenerators,
		SYM_MATRIXDATA *	matrixdata,
		SYM_EXPRDATA *	exprdata,
		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)
matrixdata	data for MIP matrix
exprdata	data for nonlinear constraints
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 size of group
symcodetime	pointer to store the time for symmetry code

Definition at line 1598 of file compute_symmetry_nauty.c.

References data_, determineGraphSize(), FALSE, fillGraphByConss(), NAUTY_Data::maxgenerators, nautyhook(), NAUTY_Data::nmaxperms, nnodes, NAUTY_Data::nperms, NAUTY_Data::npermvars, SYM_Matrixdata::npermvars, NULL, NAUTY_Data::perms, NAUTY_Data::scip, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_MINIMAL, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetSolvingTime(), SCIPsortIntInt(), and SCIPverbMessage().

Variable Documentation

◆ data_

struct NAUTY_Data data_

static

Definition at line 75 of file compute_symmetry_nauty.c.

Referenced by nautyhook(), and SYMcomputeSymmetryGenerators().

◆ nautyname

const char nautyname[] = "Nauty "NAUTYVERSION

static

static variable for holding the name of name

Definition at line 1564 of file compute_symmetry_nauty.c.

Referenced by SYMsymmetryGetName().

SCIP

Detailed Description

Data Structures

Macros

Functions

Variables

Macro Definition Documentation

◆ NAUTY

Function Documentation

◆ SCIP_DECL_HASHGETKEY() [1/3]

◆ SCIP_DECL_HASHKEYEQ() [1/3]

◆ SCIP_DECL_HASHKEYVAL() [1/3]

◆ SCIP_DECL_HASHGETKEY() [2/3]

◆ SCIP_DECL_HASHKEYEQ() [2/3]

◆ SCIP_DECL_HASHKEYVAL() [2/3]

◆ SCIP_DECL_HASHGETKEY() [3/3]

◆ SCIP_DECL_HASHKEYEQ() [3/3]

◆ SCIP_DECL_HASHKEYVAL() [3/3]

◆ nautyhook()

◆ determineGraphSize()

◆ fillGraphByConss()

◆ SYMcanComputeSymmetry()

◆ SYMsymmetryGetName()

◆ SYMsymmetryGetDesc()

◆ SYMsymmetryGetAddName()

◆ SYMsymmetryGetAddDesc()

◆ SYMcomputeSymmetryGenerators()

Variable Documentation

◆ data_

◆ nautyname