compute_symmetry_bliss.cpp File Reference

Detailed Description

interface for symmetry computations to bliss

Author

Marc Pfetsch

Thomas Rehn

Fabian Wegscheider

Definition in file compute_symmetry_bliss.cpp.

#include "compute_symmetry.h"
#include <bliss/defs.hh>
#include <bliss/graph.hh>
#include <string.h>
#include <vector>
#include <list>
#include <math.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/symmetry.h"
#include "scip/symmetry_graph.h"

Go to the source code of this file.

Data Structures
struct	BLISS_Data

Functions
static void	blisshook (void *user_param, unsigned int n, const unsigned int *aut)
SCIP_Bool	SYMcanComputeSymmetry (void)
const char *	SYMsymmetryGetName (void)
const char *	SYMsymmetryGetDesc (void)
const char *	SYMsymmetryGetAddName (void)
const char *	SYMsymmetryGetAddDesc (void)
SCIP_Bool	isEdgeGroupable (SYM_GRAPH *graph, int edgeidx, SCIP_Bool groupbycons)
static SCIP_RETCODE	addGroupedEdges (bliss::Graph *G, int commonnodeidx, int *neighbors, int *colors, int nneighbors, int *naddednodes, int *naddededges)
static SCIP_RETCODE	computeAutomorphisms (SCIP *scip, SYM_SYMTYPE symtype, bliss::Graph *G, int nsymvars, int maxgenerators, int ***perms, int *nperms, int *nmaxperms, SCIP_Real *log10groupsize, SCIP_Bool restricttovars, SCIP_Real *symcodetime)
SCIP_RETCODE	SYMcomputeSymmetryGenerators (SCIP *scip, int maxgenerators, SYM_GRAPH *graph, 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)

Function Documentation

blisshook()

static void blisshook ( void *  user_param, unsigned int  n, const unsigned int *  aut  )

static

callback function for bliss

Parameters

user_param	parameter supplied at call to bliss
n	size of aut vector
aut	automorphism

Definition at line 72 of file compute_symmetry_bliss.cpp.

References BLISS_Data::maxgenerators, BLISS_Data::nmaxperms, BLISS_Data::nperms, BLISS_Data::npermvars, NULL, BLISS_Data::perms, BLISS_Data::restricttovars, BLISS_Data::scip, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPreallocBlockMemoryArray, SYM_SYMTYPE_PERM, and BLISS_Data::symtype.

Referenced by computeAutomorphisms().

SYMcanComputeSymmetry()

SCIP_Bool SYMcanComputeSymmetry

(

void

)

return whether symmetry can be computed

Definition at line 148 of file compute_symmetry_bliss.cpp.

SYMsymmetryGetName()

const char * SYMsymmetryGetName

(

void

)

return name of external program used to compute generators

Definition at line 154 of file compute_symmetry_bliss.cpp.

SYMsymmetryGetDesc()

const char * SYMsymmetryGetDesc

(

void

)

return description of external program used to compute generators

Definition at line 164 of file compute_symmetry_bliss.cpp.

SYMsymmetryGetAddName()

const char * SYMsymmetryGetAddName

(

void

)

return name of additional external program used for computing symmetries

Definition at line 170 of file compute_symmetry_bliss.cpp.

SYMsymmetryGetAddDesc()

const char * SYMsymmetryGetAddDesc

(

void

)

return description of additional external program used to compute symmetries

Definition at line 176 of file compute_symmetry_bliss.cpp.

isEdgeGroupable()

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

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 182 of file compute_symmetry_bliss.cpp.

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

Referenced by SYMcomputeSymmetryGenerators().

addGroupedEdges()

static SCIP_RETCODE addGroupedEdges ( bliss::Graph *  G, 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

G	pointer to graph which gets extended
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 240 of file compute_symmetry_bliss.cpp.

References NULL, SCIP_OKAY, and SCIPsortIntInt().

Referenced by SYMcomputeSymmetryGenerators().

computeAutomorphisms()

static SCIP_RETCODE computeAutomorphisms ( SCIP *  scip, SYM_SYMTYPE  symtype, bliss::Graph *  G, int  nsymvars, int  maxgenerators, int ***  perms, int *  nperms, int *  nmaxperms, SCIP_Real *  log10groupsize, SCIP_Bool  restricttovars, SCIP_Real *  symcodetime  )

static

computes autormorphisms of a graph

Parameters

scip	SCIP pointer
symtype	type of symmetries that need to be computed
G	pointer to graph for that automorphisms are computed
nsymvars	number of variables encoded in graph
maxgenerators	maximum number of generators to be constructed (=0 if unlimited)
perms	pointer to store generators as (nperms x npermvars) matrix
nperms	pointer to store number of permutations
nmaxperms	pointer to store maximal number of permutations (needed for freeing storage)
log10groupsize	pointer to store log10 of size of group
restricttovars	whether permutations shall be restricted to variables
symcodetime	pointer to store the time for symmetry code

Definition at line 297 of file compute_symmetry_bliss.cpp.

References blisshook(), BLISS_Data::maxgenerators, BLISS_Data::nmaxperms, BLISS_Data::nperms, BLISS_Data::npermvars, NULL, BLISS_Data::perms, BLISS_Data::restricttovars, BLISS_Data::scip, SCIP_OKAY, SCIP_Real, SCIPgetSolvingTime(), and BLISS_Data::symtype.

Referenced by SYMcheckGraphsAreIdentical(), and SYMcomputeSymmetryGenerators().

SYMcomputeSymmetryGenerators()

SCIP_RETCODE SYMcomputeSymmetryGenerators	(	SCIP *	scip,
		int	maxgenerators,
		SYM_GRAPH *	graph,
		int *	nperms,
		int *	nmaxperms,
		int ***	perms,
		SCIP_Real *	log10groupsize,
		SCIP_Real *	symcodetime
	)

compute generators of symmetry group

Parameters

scip	SCIP pointer
maxgenerators	maximal number of generators constructed (= 0 if unlimited)
graph	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 generators as (nperms x npermvars) matrix
log10groupsize	pointer to store log10 of size of group
symcodetime	pointer to store the time for symmetry code

Definition at line 405 of file compute_symmetry_bliss.cpp.

SYMcheckGraphsAreIdentical()

SCIP_Bool SYMcheckGraphsAreIdentical	(	SCIP *	scip,
		SYM_SYMTYPE	symtype,
		SYM_GRAPH *	G1,
		SYM_GRAPH *	G2
	)

returns whether two given graphs are identical

Parameters

scip	SCIP pointer
symtype	type of symmetries to be checked
G1	first graph
G2	second graph

Definition at line 627 of file compute_symmetry_bliss.cpp.