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/symmetry_graph.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 "tinycthread/tinycthread.h"

Go to the source code of this file.

Data Structures
struct	NAUTY_Data

Macros
#define	NAUTY

Typedefs
typedef struct NAUTY_Data	NAUTY_DATA

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

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

static SCIP_Bool	isEdgeGroupable (SYM_GRAPH *symgraph, int edgeidx, SCIP_Bool groupbycons)

static SCIP_RETCODE	addOrDetermineEffectOfGroupedEdges (SCIP scip, sparsegraph SG, int edgestartpos, SCIP_Bool determinesize, int internodeid, int *degrees, int maxdegrees, int *colorstostore, int ncolorstostore, int nnodes, int nedges, int commonnodeidx, int neighbors, int colors, int nneighbors, int naddednodes, int naddededges)

static SCIP_RETCODE	createOrDetermineSizeGraph (SCIP scip, SYM_GRAPH symgraph, SCIP_Bool determinesize, sparsegraph SG, int nnodes, int nedges, int degrees, int maxdegrees, int *colors, int ncolors, SCIP_Bool *success)

static SCIP_RETCODE	createOrDetermineSizeGraphCheck (SCIP scip, SYM_GRAPH graph1, SYM_GRAPH graph2, SCIP_Bool determinesize, sparsegraph SG, int nnodes, int nedges, int *degrees, int maxdegrees, int *colors, int ncolors, int nusedvars, int nnodesfromgraph1, SCIP_Bool *success)

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_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 NAUTY_DATA	data_

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 35 of file compute_symmetry_nauty.c.

Typedef Documentation

◆ NAUTY_DATA

typedef struct NAUTY_Data NAUTY_DATA

Definition at line 77 of file compute_symmetry_nauty.c.

Function Documentation

◆ 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 92 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::restricttovars, NAUTY_Data::scip, SCIP_Bool, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPduplicateBlockMemoryArray, SCIPreallocBlockMemoryArray, SYM_SYMTYPE_PERM, NAUTY_Data::symtype, and TRUE.

Referenced by SYMcheckGraphsAreIdentical(), and SYMcomputeSymmetryGenerators().

◆ 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 169 of file compute_symmetry_nauty.c.

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

Referenced by SYMcomputeSymmetryGenerators().

◆ isEdgeGroupable()

static SCIP_Bool isEdgeGroupable	(	SYM_GRAPH *	symgraph,
		int	edgeidx,
		SCIP_Bool	groupbycons
	)

static

returns whether an edge is considered in grouping process

Parameters

symgraph	symmetry detection graph
edgeidx	index of edge to be checked
groupbycons	whether edges are grouped by constraints

Definition at line 274 of file compute_symmetry_nauty.c.

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

Referenced by createOrDetermineSizeGraph(), and createOrDetermineSizeGraphCheck().

◆ addOrDetermineEffectOfGroupedEdges()

static SCIP_RETCODE addOrDetermineEffectOfGroupedEdges	(	SCIP *	scip,
		sparsegraph *	SG,
		int *	edgestartpos,
		SCIP_Bool	determinesize,
		int *	internodeid,
		int **	degrees,
		int *	maxdegrees,
		int **	colorstostore,
		int *	ncolorstostore,
		int *	nnodes,
		int *	nedges,
		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

scip	SCIP pointer
SG	graph to be constructed
edgestartpos	initialized array of starting positions of new edges for each node
determinesize	whether only the effect of grouping on the graph shall be checked
internodeid	(initialized) pointer to store the ID of the next intermediate node
degrees	pointer to array of degrees for nodes in G
maxdegrees	(initialized) pointer to maximum number of entries degrees can hold
colorstostore	pointer to array of colors of graph to be constructed
ncolorstostore	(initialized) pointer to maximum number of entries in colorstostore
nnodes	(initialized) pointer to store the number of
nedges	(initialized) pointer to store the number of
commonnodeidx	index of common node in G
neighbors	neighbors of common node
colors	colors of edges to neighbors
nneighbors	number of neighbors
naddednodes	pointer to store number of nodes added to G
naddededges	pointer to store number of edges added to G

Definition at line 335 of file compute_symmetry_nauty.c.

References nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPensureBlockMemoryArray, and SCIPsortIntInt().

Referenced by createOrDetermineSizeGraph(), and createOrDetermineSizeGraphCheck().

◆ createOrDetermineSizeGraph()

static SCIP_RETCODE createOrDetermineSizeGraph	(	SCIP *	scip,
		SYM_GRAPH *	symgraph,
		SCIP_Bool	determinesize,
		sparsegraph *	SG,
		int *	nnodes,
		int *	nedges,
		int **	degrees,
		int *	maxdegrees,
		int **	colors,
		int *	ncolors,
		SCIP_Bool *	success
	)

static

either creates a graph or determines its size

Parameters

scip	SCIP instance
symgraph	symmetry detection graph
determinesize	whether only the size of the graph shall be determined
SG	graph to be constructed
nnodes	pointer to store the total number of nodes in graph
nedges	pointer to store the total number of edges in graph
degrees	pointer to store the degrees of the nodes
maxdegrees	pointer to store the maximal size of the degree array
colors	pointer to store the colors of the nodes
ncolors	pointer to store number of different colors in graph
success	pointer to store whether the construction was successful

Definition at line 460 of file compute_symmetry_nauty.c.

References addOrDetermineEffectOfGroupedEdges(), isEdgeGroupable(), nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPdebugMsg, SCIPensureBlockMemoryArray, SCIPfreeBlockMemoryArray, 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, NAUTY_Data::symtype, and TRUE.

Referenced by SYMcomputeSymmetryGenerators().

◆ createOrDetermineSizeGraphCheck()

static SCIP_RETCODE createOrDetermineSizeGraphCheck	(	SCIP *	scip,
		SYM_GRAPH *	graph1,
		SYM_GRAPH *	graph2,
		SCIP_Bool	determinesize,
		sparsegraph *	SG,
		int *	nnodes,
		int *	nedges,
		int **	degrees,
		int *	maxdegrees,
		int **	colors,
		int *	ncolors,
		int *	nusedvars,
		int *	nnodesfromgraph1,
		SCIP_Bool *	success
	)

static

either creates a graph for checking symmetries or determines its size

The input are two graphs and the graph to be constructed consists of copies of the two input graphs, in which non-variable nodes are colored according to the colors used in symmetry detection. Each variable gets a unique color. Finally, a dummy node is introduced that is adjacent with all remaining nodes.

Parameters

scip	SCIP instance
graph1	first symmetry detection graph
graph2	second symmetry detection graph
determinesize	whether only the size of the graph shall be determined
SG	graph to be constructed
nnodes	pointer to store the total number of nodes in graph
nedges	pointer to store the total number of edges in graph
degrees	pointer to store the degrees of the nodes
maxdegrees	pointer to store the maximal size of the degree array
colors	pointer to store the colors of the nodes
ncolors	pointer to store number of different colors in graph
nusedvars	pointer to store number of variables used in one graph
nnodesfromgraph1	pointer to store number of nodes arising from graph1 (or NULL)
success	pointer to store whether the graph could be built

Definition at line 759 of file compute_symmetry_nauty.c.

References addOrDetermineEffectOfGroupedEdges(), FALSE, isEdgeGroupable(), nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPensureBlockMemoryArray, SCIPfreeBlockMemoryArray, 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, NAUTY_Data::symtype, and TRUE.

Referenced by SYMcheckGraphsAreIdentical().

◆ SYMcanComputeSymmetry()

SCIP_Bool SYMcanComputeSymmetry ( void )

return whether symmetry can be computed

Definition at line 1176 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 1189 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 1195 of file compute_symmetry_nauty.c.

◆ SYMsymmetryGetAddName()

const char * SYMsymmetryGetAddName ( void )

return name of additional external program used for computing symmetries

Definition at line 1205 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 1211 of file compute_symmetry_nauty.c.

References NULL.

◆ 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 size of group
symcodetime	pointer to store the time for symmetry code

Definition at line 1217 of file compute_symmetry_nauty.c.

References createOrDetermineSizeGraph(), data_, FALSE, NAUTY_Data::maxgenerators, NAUTY_Data::maxlevel, nautyhook(), nautyterminationhook(), NAUTY_Data::nmaxperms, nnodes, NAUTY_Data::nperms, NAUTY_Data::npermvars, NULL, NAUTY_Data::perms, NAUTY_Data::restricttovars, NAUTY_Data::scip, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_MINIMAL, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetIntParam(), SCIPgetSolvingTime(), SCIPgetSymgraphNVars(), SCIPgetSymgraphSymtype(), SCIPsortIntInt(), SCIPverbMessage(), NAUTY_Data::symtype, and TRUE.

◆ 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 1373 of file compute_symmetry_nauty.c.

References createOrDetermineSizeGraphCheck(), data_, FALSE, NAUTY_Data::maxgenerators, NAUTY_Data::maxlevel, nautyhook(), SYM_Graph::nconsnodes, SYM_Graph::nedges, NAUTY_Data::nmaxperms, nnodes, SYM_Graph::nnodes, SYM_Graph::nopnodes, NAUTY_Data::nperms, NAUTY_Data::npermvars, NULL, SYM_Graph::nvalnodes, NAUTY_Data::perms, NAUTY_Data::restricttovars, NAUTY_Data::scip, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPgetIntParam(), SCIPgetSymgraphNVars(), SCIPinfoMessage(), SCIPsortIntInt(), NAUTY_Data::symtype, TRUE, and w.

Variable Documentation

◆ data_

_Thread_local NAUTY_DATA data_

static

static data for nauty callback

Definition at line 81 of file compute_symmetry_nauty.c.

Referenced by nautyhook(), nautyterminationhook(), SYMcheckGraphsAreIdentical(), and SYMcomputeSymmetryGenerators().

◆ 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 1183 of file compute_symmetry_nauty.c.

Referenced by SYMsymmetryGetName().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ NAUTY

Typedef Documentation

◆ NAUTY_DATA

Function Documentation

◆ nautyhook()

◆ nautyterminationhook()

◆ isEdgeGroupable()

◆ addOrDetermineEffectOfGroupedEdges()

◆ createOrDetermineSizeGraph()

◆ createOrDetermineSizeGraphCheck()

◆ SYMcanComputeSymmetry()

◆ SYMsymmetryGetName()

◆ SYMsymmetryGetDesc()

◆ SYMsymmetryGetAddName()

◆ SYMsymmetryGetAddDesc()

◆ SYMcomputeSymmetryGenerators()

◆ SYMcheckGraphsAreIdentical()

Variable Documentation

◆ data_

◆ nautyname