Scippy

SCIP

Solving Constraint Integer Programs

build_sassy_graph.cpp File Reference

Detailed Description

methods to build sassy graph for symmetry detection

Author
Christopher Hojny

Definition in file build_sassy_graph.cpp.

#include "build_sassy_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 "scip/symmetry_graph.h"

Go to the source code of this file.

Functions

static SCIP_Bool isEdgeGroupable (SYM_GRAPH *graph, int edgeidx, SCIP_Bool groupbycons)
 
static SCIP_RETCODE addOrDetermineEffectOfGroupedEdges (SCIP *scip, sassy::static_graph *G, SCIP_Bool determinesize, int *internodeid, int **degrees, int *maxdegrees, int *nnodes, int *nedges, int commonnodeidx, int *neighbors, int *colors, int nneighbors, int *naddednodes, int *naddededges)
 
static SCIP_RETCODE createOrDetermineSizeGraph (SCIP *scip, SYM_GRAPH *graph, SCIP_Bool determinesize, sassy::static_graph *G, int *nnodes, int *nedges, int **degrees, int *maxdegrees, SCIP_Bool *success)
 
static SCIP_RETCODE createOrDetermineSizeGraphCheck (SCIP *scip, SYM_GRAPH *graph1, SYM_GRAPH *graph2, SCIP_Bool determinesize, sassy::static_graph *G, int *nnodes, int *nedges, int **degrees, int *maxdegrees, int *nnodesfromG1, SCIP_Bool *success)
 
SCIP_RETCODE SYMbuildSassyGraph (SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *graph, SCIP_Bool *success)
 
SCIP_RETCODE SYMbuildSassyGraphCheck (SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *G1, SYM_GRAPH *G2, int *nnodes, int *nnodesfromG1, SCIP_Bool *success)
 

Function Documentation

◆ isEdgeGroupable()

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

returns whether an edge is considered in grouping process

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

Definition at line 47 of file build_sassy_graph.cpp.

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

Referenced by createOrDetermineSizeGraph(), and createOrDetermineSizeGraphCheck().

◆ addOrDetermineEffectOfGroupedEdges()

static SCIP_RETCODE addOrDetermineEffectOfGroupedEdges ( SCIP scip,
sassy::static_graph *  G,
SCIP_Bool  determinesize,
int *  internodeid,
int **  degrees,
int *  maxdegrees,
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
Ggraph which gets extended
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
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 108 of file build_sassy_graph.cpp.

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

Referenced by createOrDetermineSizeGraph(), and createOrDetermineSizeGraphCheck().

◆ createOrDetermineSizeGraph()

static SCIP_RETCODE createOrDetermineSizeGraph ( SCIP scip,
SYM_GRAPH graph,
SCIP_Bool  determinesize,
sassy::static_graph *  G,
int *  nnodes,
int *  nedges,
int **  degrees,
int *  maxdegrees,
SCIP_Bool success 
)
static

either creates a graph or determines its size

Parameters
scipSCIP instance
graphsymmetry detection graph
determinesizewhether only the size of the graph shall be determined
Ggraph 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
successpointer to store whether the construction was successful

Definition at line 220 of file build_sassy_graph.cpp.

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

Referenced by SYMbuildSassyGraph().

◆ createOrDetermineSizeGraphCheck()

static SCIP_RETCODE createOrDetermineSizeGraphCheck ( SCIP scip,
SYM_GRAPH graph1,
SYM_GRAPH graph2,
SCIP_Bool  determinesize,
sassy::static_graph *  G,
int *  nnodes,
int *  nedges,
int **  degrees,
int *  maxdegrees,
int *  nnodesfromG1,
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.

Parameters
scipSCIP instance
graph1first symmetry detection graph
graph2second symmetry detection graph
determinesizewhether only the size of the graph shall be determined
Ggraph 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
nnodesfromG1pointer to store number of nodes in sassy graph arising from G1 (or NULL)
successpointer to store whether the graph could be built

Definition at line 488 of file build_sassy_graph.cpp.

References addOrDetermineEffectOfGroupedEdges(), FALSE, isEdgeGroupable(), nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPensureBlockMemoryArray, SCIPfreeBufferArray, SCIPgetSymgraphEdgeColor(), SCIPgetSymgraphEdgeFirst(), SCIPgetSymgraphEdgeSecond(), SCIPgetSymgraphNConsnodes(), SCIPgetSymgraphNEdges(), SCIPgetSymgraphNNodes(), SCIPgetSymgraphNodeColor(), SCIPgetSymgraphNodeType(), SCIPgetSymgraphNVars(), SCIPgetSymgraphSymtype(), SCIPhasGraphUniqueEdgetype(), SCIPisSymgraphEdgeColored(), SCIPsortIntIntInt(), SYM_NODETYPE_CONS, SYM_NODETYPE_VAR, SYM_SYMTYPE_PERM, SYM_SYMTYPE_SIGNPERM, and TRUE.

Referenced by SYMbuildSassyGraphCheck().

◆ SYMbuildSassyGraph()

SCIP_RETCODE SYMbuildSassyGraph ( SCIP scip,
sassy::static_graph *  sassygraph,
SYM_GRAPH graph,
SCIP_Bool success 
)

compute generators of symmetry group

Parameters
scipSCIP pointer
sassygraphpointer to hold sassy graph being created
graphsymmetry detection graph
successpointer to store whether sassygraph could be built

Definition at line 849 of file build_sassy_graph.cpp.

References createOrDetermineSizeGraph(), FALSE, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_MINIMAL, SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIPverbMessage(), and TRUE.

Referenced by SYMcomputeSymmetryGenerators().

◆ SYMbuildSassyGraphCheck()

SCIP_RETCODE SYMbuildSassyGraphCheck ( SCIP scip,
sassy::static_graph *  sassygraph,
SYM_GRAPH G1,
SYM_GRAPH G2,
int *  nnodes,
int *  nnodesfromG1,
SCIP_Bool success 
)

returns whether two given graphs are identical

Parameters
scipSCIP pointer
sassygraphpointer to hold sassy graph being created
G1first graph
G2second graph
nnodespointer to store number of nodes in sassy graph
nnodesfromG1pointer to store number of nodes in sassy graph arising from G1
successpointer to store whether sassygraph could be built

Definition at line 892 of file build_sassy_graph.cpp.

References createOrDetermineSizeGraphCheck(), FALSE, SYM_Graph::nconsnodes, SYM_Graph::nedges, nnodes, SYM_Graph::nnodes, SYM_Graph::nopnodes, NULL, SYM_Graph::nvalnodes, SCIP_CALL_ABORT, SCIP_OKAY, SCIPfreeBlockMemoryArray, and TRUE.

Referenced by SYMcheckGraphsAreIdentical().