SCIP
Solving Constraint Integer Programs
build_sassy_graph.cpp File Reference
Detailed Description
methods to build sassy graph for symmetry detection
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()
returns whether an edge is considered in grouping process
- Parameters
-
graph symmetry detection graph edgeidx index of edge to be checked groupbycons whether 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 |
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 G graph which gets extended 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 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 108 of file build_sassy_graph.cpp.
References nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPensureBlockMemoryArray, and SCIPsortIntInt().
Referenced by createOrDetermineSizeGraph(), and createOrDetermineSizeGraphCheck().
◆ createOrDetermineSizeGraph()
|
static |
either creates a graph or determines its size
- Parameters
-
scip SCIP instance graph symmetry detection graph determinesize whether only the size of the graph shall be determined G 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 success pointer 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 |
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
-
scip SCIP instance graph1 first symmetry detection graph graph2 second symmetry detection graph determinesize whether only the size of the graph shall be determined G 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 nnodesfromG1 pointer to store number of nodes in sassy graph arising from G1 (or NULL) success pointer 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
-
scip SCIP pointer sassygraph pointer to hold sassy graph being created graph symmetry detection graph success pointer 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
-
scip SCIP pointer sassygraph pointer to hold sassy graph being created G1 first graph G2 second graph nnodes pointer to store number of nodes in sassy graph nnodesfromG1 pointer to store number of nodes in sassy graph arising from G1 success pointer 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().