interface for symmetry computations to nauty/traces
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 |
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 NAUTY_DATA | data_ |
static const char | nautyname [] = {'N', 'a', 'u', 't', 'y', ' ', NAUTYVERSIONID/10000 + '0', '.', (NAUTYVERSIONID%10000)/1000 + '0', '.', (NAUTYVERSIONID%1000)/10 + '0', '\0'} |
#define NAUTY |
Definition at line 35 of file compute_symmetry_nauty.c.
typedef struct NAUTY_Data NAUTY_DATA |
Definition at line 79 of file compute_symmetry_nauty.c.
|
static |
callback function for nauty
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 94 of file compute_symmetry_nauty.c.
References assert(), data_, FALSE, NULL, SCIP_Bool, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPduplicateBlockMemoryArray, SCIPreallocBlockMemoryArray, SYM_SYMTYPE_PERM, and TRUE.
Referenced by SYMcheckGraphsAreIdentical(), and SYMcomputeSymmetryGenerators().
|
static |
callback function for nauty to terminate early
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 171 of file compute_symmetry_nauty.c.
References data_, FALSE, NULL, SCIP_Bool, SCIP_VERBLEVEL_MINIMAL, SCIPverbMessage(), and TRUE.
Referenced by computeAutomorphisms(), and SYMcomputeSymmetryGenerators().
returns whether an edge is considered in grouping process
symgraph | symmetry detection graph |
edgeidx | index of edge to be checked |
groupbycons | whether edges are grouped by constraints |
Definition at line 296 of file compute_symmetry_nauty.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIPgetSymgraphEdgeFirst(), SCIPgetSymgraphEdgeSecond(), SCIPgetSymgraphNodeType(), SCIPisSymgraphEdgeColored(), SYM_NODETYPE_CONS, and TRUE.
Referenced by createOrDetermineSizeGraph(), and createOrDetermineSizeGraphCheck().
|
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.
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 357 of file compute_symmetry_nauty.c.
References assert(), nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPensureBlockMemoryArray, and SCIPsortIntInt().
Referenced by createOrDetermineSizeGraph(), and createOrDetermineSizeGraphCheck().
|
static |
either creates a graph or determines its size
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 482 of file compute_symmetry_nauty.c.
References addOrDetermineEffectOfGroupedEdges(), assert(), 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().
|
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.
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 781 of file compute_symmetry_nauty.c.
References addOrDetermineEffectOfGroupedEdges(), assert(), FALSE, i, 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().
SCIP_Bool SYMcanComputeSymmetry | ( | void | ) |
return whether symmetry can be computed
Definition at line 1198 of file compute_symmetry_nauty.c.
const char * SYMsymmetryGetName | ( | void | ) |
return name of external program used to compute generators
Definition at line 1211 of file compute_symmetry_nauty.c.
References nautyname.
const char * SYMsymmetryGetDesc | ( | void | ) |
return description of external program used to compute generators
Definition at line 1217 of file compute_symmetry_nauty.c.
const char * SYMsymmetryGetAddName | ( | void | ) |
return name of additional external program used for computing symmetries
Definition at line 1227 of file compute_symmetry_nauty.c.
References NULL.
const char * SYMsymmetryGetAddDesc | ( | void | ) |
return description of additional external program used to compute symmetries
Definition at line 1233 of file compute_symmetry_nauty.c.
References NULL.
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
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 1239 of file compute_symmetry_nauty.c.
References assert(), createOrDetermineSizeGraph(), data_, FALSE, NAUTY_Data::maxgenerators, nautyhook(), nautyterminationhook(), NAUTY_Data::nmaxperms, nnodes, NAUTY_Data::nperms, NULL, NAUTY_Data::perms, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_MINIMAL, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIPfreeBufferArray, SCIPgetIntParam(), SCIPgetSolvingTime(), SCIPgetSymgraphNVars(), SCIPgetSymgraphSymtype(), SCIPsortIntInt(), SCIPverbMessage(), and TRUE.
SCIP_Bool SYMcheckGraphsAreIdentical | ( | SCIP * | scip, |
SYM_SYMTYPE | symtype, | ||
SYM_GRAPH * | G1, | ||
SYM_GRAPH * | G2 ) |
returns whether two given graphs are identical
scip | SCIP pointer |
symtype | type of symmetries to be checked |
G1 | first graph |
G2 | second graph |
Definition at line 1397 of file compute_symmetry_nauty.c.
References assert(), createOrDetermineSizeGraphCheck(), data_, FALSE, i, nautyhook(), SYM_Graph::nconsnodes, SYM_Graph::nedges, nnodes, SYM_Graph::nnodes, SYM_Graph::nopnodes, NULL, SYM_Graph::nvalnodes, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPgetIntParam(), SCIPgetSymgraphNVars(), SCIPinfoMessage(), SCIPsortIntInt(), NAUTY_Data::symtype, TRUE, and w.
|
static |
static data for nauty callback
Definition at line 85 of file compute_symmetry_nauty.c.
Referenced by nautyhook(), nautyterminationhook(), SYMcheckGraphsAreIdentical(), and SYMcomputeSymmetryGenerators().
|
static |
nauty/traces version string
Definition at line 1205 of file compute_symmetry_nauty.c.
Referenced by SYMsymmetryGetName().