build_sassy_graph.cpp File Reference

#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

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 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

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 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

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(), 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

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 480 of file build_sassy_graph.cpp.

References addOrDetermineEffectOfGroupedEdges(), FALSE, isEdgeGroupable(), 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 831 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 874 of file build_sassy_graph.cpp.

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

Referenced by SYMcheckGraphsAreIdentical().