SCIP Doxygen Documentation
Loading...
Searching...
No Matches
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()

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

◆ 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
graphsymmetry detection graph
edgeidxindex of edge to be checked
groupbyconswhether edges are grouped by constraints

Definition at line 182 of file compute_symmetry_bliss.cpp.

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

Referenced by SYMcomputeSymmetryGenerators().

◆ addGroupedEdges()

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

References assert(), NULL, SCIP_OKAY, and SCIPsortIntInt().

Referenced by SYMcomputeSymmetryGenerators().

◆ computeAutomorphisms()

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
scipSCIP pointer
symtypetype of symmetries that need to be computed
Gpointer to graph for that automorphisms are computed
nsymvarsnumber of variables encoded in graph
maxgeneratorsmaximum number of generators to be constructed (=0 if unlimited)
permspointer to store generators as (nperms x npermvars) matrix
npermspointer to store number of permutations
nmaxpermspointer to store maximal number of permutations (needed for freeing storage)
log10groupsizepointer to store log10 of size of group
restricttovarswhether permutations shall be restricted to variables
symcodetimepointer to store the time for symmetry code

Definition at line 297 of file compute_symmetry_bliss.cpp.

References assert(), blisshook(), BLISS_Data::maxgenerators, BLISS_Data::nmaxperms, BLISS_Data::nperms, BLISS_Data::npermvars, NULL, BLISS_Data::perms, BLISS_Data::restricttovars, BLISS_Data::scip, SCIP_Bool, 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
scipSCIP pointer
maxgeneratorsmaximal number of generators constructed (= 0 if unlimited)
graphsymmetry detection graph
npermspointer to store number of permutations
nmaxpermspointer to store maximal number of permutations (needed for freeing storage)
permspointer to store generators as (nperms x npermvars) matrix
log10groupsizepointer to store log10 of size of group
symcodetimepointer 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
scipSCIP pointer
symtypetype of symmetries to be checked
G1first graph
G2second graph

Definition at line 627 of file compute_symmetry_bliss.cpp.