Scippy

SCIP

Solving Constraint Integer Programs

compute_symmetry_nauty.c File Reference

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"

Go to the source code of this file.

Data Structures

struct  NAUTY_Data
 

Macros

#define NAUTY
 

Functions

static void nautyhook (int count, int *p, int *orbits, int numorbits, int stabvertex, 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 struct NAUTY_Data data_
 
static TLS_ATTR char nautyname [20]
 

Macro Definition Documentation

◆ NAUTY

#define NAUTY

Definition at line 35 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
countID of this generator
pgenerator (permutation) that nauty found
orbitsorbits generated by the group found so far
numorbitsnumber of orbits
stabvertexstabilizing node
nnumber of nodes in the graph

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

◆ isEdgeGroupable()

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

returns whether an edge is considered in grouping process

Parameters
symgraphsymmetry detection graph
edgeidxindex of edge to be checked
groupbyconswhether edges are grouped by constraints

Definition at line 242 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
scipSCIP pointer
SGgraph to be constructed
edgestartposinitialized array of starting positions of new edges for each node
determinesizewhether only the effect of grouping on the graph shall be checked
internodeid(initialized) pointer to store the ID of the next intermediate node
degreespointer to array of degrees for nodes in G
maxdegrees(initialized) pointer to maximum number of entries degrees can hold
colorstostorepointer 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
commonnodeidxindex of common node in G
neighborsneighbors of common node
colorscolors of edges to neighbors
nneighborsnumber of neighbors
naddednodespointer to store number of nodes added to G
naddededgespointer to store number of edges added to G

Definition at line 303 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
scipSCIP instance
symgraphsymmetry detection graph
determinesizewhether only the size of the graph shall be determined
SGgraph to be constructed
nnodespointer to store the total number of nodes in graph
nedgespointer to store the total number of edges in graph
degreespointer to store the degrees of the nodes
maxdegreespointer to store the maximal size of the degree array
colorspointer to store the colors of the nodes
ncolorspointer to store number of different colors in graph
successpointer to store whether the construction was successful

Definition at line 428 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
scipSCIP instance
graph1first symmetry detection graph
graph2second symmetry detection graph
determinesizewhether only the size of the graph shall be determined
SGgraph to be constructed
nnodespointer to store the total number of nodes in graph
nedgespointer to store the total number of edges in graph
degreespointer to store the degrees of the nodes
maxdegreespointer to store the maximal size of the degree array
colorspointer to store the colors of the nodes
ncolorspointer to store number of different colors in graph
nusedvarspointer to store number of variables used in one graph
nnodesfromgraph1pointer to store number of nodes arising from graph1 (or NULL)
successpointer to store whether the graph could be built

Definition at line 727 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 1144 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 1153 of file compute_symmetry_nauty.c.

References nautyname, and SCIPsnprintf().

◆ SYMsymmetryGetDesc()

const char * SYMsymmetryGetDesc ( void  )

return description of external program used to compute generators

Definition at line 1165 of file compute_symmetry_nauty.c.

◆ SYMsymmetryGetAddName()

const char * SYMsymmetryGetAddName ( void  )

return name of additional external program used for computing symmetries

Definition at line 1175 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 1181 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
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 size of group
symcodetimepointer to store the time for symmetry code

Definition at line 1187 of file compute_symmetry_nauty.c.

References createOrDetermineSizeGraph(), data_, FALSE, NAUTY_Data::maxgenerators, nautyhook(), 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, SCIPgetSolvingTime(), SCIPgetSymgraphNVars(), SCIPgetSymgraphSymtype(), SCIPsortIntInt(), SCIPverbMessage(), NAUTY_Data::symtype, and TRUE.

◆ SYMcheckGraphsAreIdentical()

Variable Documentation

◆ data_

struct NAUTY_Data data_
static

◆ nautyname

TLS_ATTR char nautyname[20]
static

static variable for holding the name of nauty

Definition at line 1150 of file compute_symmetry_nauty.c.

Referenced by SYMsymmetryGetName().