Detailed Description

methods to build dejavu graph for symmetry detection

Author: Christopher Hojny; Marc Pfetsch

Definition in file build_dejavu_graph.cpp.

#include <string>
#include "build_dejavu_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, dejavu::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, dejavu::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, dejavu::static_graph G, int nnodes, int nedges, int *degrees, int maxdegrees, int nnodesfromG1, SCIP_Bool success)
SCIP_RETCODE	SYMbuildDejavuGraph (SCIP scip, dejavu::static_graph dejavugraph, SYM_GRAPH graph, SCIP_Bool success)
SCIP_RETCODE	SYMbuildDejavuGraphCheck (SCIP scip, dejavu::static_graph dejavugraph, SYM_GRAPH G1, SYM_GRAPH G2, int nnodes, int nnodesfromG1, SCIP_Bool *success)

Function Documentation

◆ isEdgeGroupable()

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 49 of file build_dejavu_graph.cpp.

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

Referenced by createOrDetermineSizeGraph(), and createOrDetermineSizeGraphCheck().

◆ addOrDetermineEffectOfGroupedEdges()

SCIP_RETCODE addOrDetermineEffectOfGroupedEdges	(	SCIP *	scip,
		dejavu::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 110 of file build_dejavu_graph.cpp.

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

Referenced by createOrDetermineSizeGraph(), and createOrDetermineSizeGraphCheck().

◆ createOrDetermineSizeGraph()

SCIP_RETCODE createOrDetermineSizeGraph	(	SCIP *	scip,
		SYM_GRAPH *	graph,
		SCIP_Bool	determinesize,
		dejavu::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 222 of file build_dejavu_graph.cpp.

References addOrDetermineEffectOfGroupedEdges(), assert(), 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 SYMbuildDejavuGraph().

◆ createOrDetermineSizeGraphCheck()

SCIP_RETCODE createOrDetermineSizeGraphCheck	(	SCIP *	scip,
		SYM_GRAPH *	graph1,
		SYM_GRAPH *	graph2,
		SCIP_Bool	determinesize,
		dejavu::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 dejavu graph arising from G1 (or NULL)
success	pointer to store whether the graph could be built

Definition at line 490 of file build_dejavu_graph.cpp.

References addOrDetermineEffectOfGroupedEdges(), assert(), FALSE, i, 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 SYMbuildDejavuGraphCheck().

◆ SYMbuildDejavuGraph()

SCIP_RETCODE SYMbuildDejavuGraph	(	SCIP *	scip,
		dejavu::static_graph *	dejavugraph,
		SYM_GRAPH *	graph,
		SCIP_Bool *	success )

compute generators of symmetry group

Parameters

scip	SCIP pointer
dejavugraph	pointer to hold dejavu graph being created
graph	symmetry detection graph
success	pointer to store whether dejavugraph could be built

Definition at line 851 of file build_dejavu_graph.cpp.

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

Referenced by SYMcomputeSymmetryGenerators(), and SYMcomputeSymmetryGenerators().

◆ SYMbuildDejavuGraphCheck()

SCIP_RETCODE SYMbuildDejavuGraphCheck	(	SCIP *	scip,
		dejavu::static_graph *	dejavugraph,
		SYM_GRAPH *	G1,
		SYM_GRAPH *	G2,
		int *	nnodes,
		int *	nnodesfromG1,
		SCIP_Bool *	success )

returns whether two given graphs are identical

Parameters

scip	SCIP pointer
dejavugraph	pointer to hold dejavu graph being created
G1	first graph
G2	second graph
nnodes	pointer to store number of nodes in dejavu graph
nnodesfromG1	pointer to store number of nodes in dejavu graph arising from G1
success	pointer to store whether dejavugraph could be built

Definition at line 894 of file build_dejavu_graph.cpp.

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

Referenced by SYMcheckGraphsAreIdentical().

Detailed Description

Functions

Function Documentation

◆ isEdgeGroupable()

◆ addOrDetermineEffectOfGroupedEdges()

◆ createOrDetermineSizeGraph()

◆ createOrDetermineSizeGraphCheck()

◆ SYMbuildDejavuGraph()

◆ SYMbuildDejavuGraphCheck()