bliss_automorph.cpp File Reference

Detailed Description

automorphism recognition of SCIPs

Author

Daniel Peters

Martin Bergner

Jonas Witt

Michael Bastubbe

Definition in file bliss_automorph.cpp.

#include "bliss/graph.hh"
#include "bliss_automorph.h"
#include "scip_misc.h"
#include "scip/scip.h"
#include "gcg.h"
#include "scip/cons_linear.h"
#include "pub_bliss.h"
#include "class_partialdecomp.h"
#include "class_detprobdata.h"
#include "cons_decomp.hpp"
#include <cstring>

Go to the source code of this file.

Data Structures
struct	AUT_HOOK2

Functions
static void	fhook (void *user_param, unsigned int N, const unsigned int *aut)
static SCIP_RETCODE	testScipVars (SCIP *scip1, SCIP *scip2, SCIP_RESULT *result)
static SCIP_RETCODE	testScipCons (SCIP *scip1, SCIP *scip2, SCIP_RESULT *result)
static SCIP_RETCODE	allocMemory (SCIP *scip, AUT_COLOR *colorinfo, int nconss, int nvars)
static SCIP_RETCODE	allocMemoryNewDetection (SCIP *scip, gcg::DETPROBDATA *detprobdata, AUT_COLOR *colorinfo, int nconss, int nvars, int ncoeffs)
static SCIP_RETCODE	reallocMemory (SCIP *scip, AUT_COLOR *colorinfo, int nconss, int nvars)
static SCIP_RETCODE	freeMemory (SCIP *scip, AUT_COLOR *colorinfo)
static SCIP_RETCODE	setuparrays (SCIP *origscip, SCIP **scips, int nscips, AUT_COLOR *colorinfo, SCIP_RESULT *result)
static SCIP_RETCODE	setuparraysnewdetection (SCIP *scip, gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec, int nblocks, std::vector< int > blocks, AUT_COLOR *colorinfo, SCIP_RESULT *result)
static SCIP_RETCODE	createGraph (SCIP *origscip, SCIP **scips, int nscips, int *pricingindices, AUT_COLOR colorinfo, bliss::Graph *graph, int *pricingnodes, SCIP_RESULT *result)
static SCIP_RETCODE	createGraphNewDetection (SCIP *scip, gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec, int nblocks, std::vector< int > blocks, AUT_COLOR colorinfo, bliss::Graph *graph, int *pricingnodes, SCIP_RESULT *result)
SCIP_RETCODE	cmpGraphPair (SCIP *origscip, SCIP *scip1, SCIP *scip2, int prob1, int prob2, SCIP_RESULT *result, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, unsigned int searchnodelimit, unsigned int generatorlimit)
SCIP_RETCODE	cmpGraphPair (SCIP *scip, gcg::PARTIALDECOMP *partialdec, int block1, int block2, SCIP_RESULT *result, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, unsigned int searchnodelimit, unsigned int generatorlimit)

Function Documentation

fhook()

static void fhook ( void *  user_param, unsigned int  N, const unsigned int *  aut  )

static

hook function to save the permutation of the graph; fhook() is called by metis for every generator, AUT_HOOK* hook stores a combined mapping in nodemapping that is filled generator-wise

Parameters

user_param	data structure to save hashmaps with permutation
N	number of permutations
aut	array of permutations

Definition at line 201 of file bliss_automorph.cpp.

References AUT_HOOK2::blocks, AUT_HOOK2::detprobdata, AUT_HOOK2::getBool(), gcg::DETPROBDATA::getCons(), AUT_HOOK2::getConsHash(), gcg::PARTIALDECOMP::getConssForBlock(), gcg::PARTIALDECOMP::getNConssForBlock(), AUT_HOOK2::getNNodes(), gcg::PARTIALDECOMP::getNVarsForBlock(), gcg::DETPROBDATA::getScip(), AUT_HOOK2::getScips(), gcg::DETPROBDATA::getVar(), AUT_HOOK2::getVarHash(), gcg::PARTIALDECOMP::getVarsForBlock(), AUT_HOOK2::ncalls, AUT_HOOK2::nodemap, AUT_HOOK2::partialdec, and AUT_HOOK2::setBool().

Referenced by cmpGraphPair().

testScipVars()

static SCIP_RETCODE testScipVars ( SCIP *  scip1, SCIP *  scip2, SCIP_RESULT *  result  )

static

tests if two scips have the same number of variables

Parameters

scip1	first SCIP data structure
scip2	second SCIP data structure
result	result pointer to indicate success or failure

Definition at line 371 of file bliss_automorph.cpp.

Referenced by cmpGraphPair().

testScipCons()

static SCIP_RETCODE testScipCons ( SCIP *  scip1, SCIP *  scip2, SCIP_RESULT *  result  )

static

tests if two scips have the same number of constraints

Parameters

scip1	first SCIP data structure
scip2	second SCIP data structure
result	result pointer to indicate success or failure

Definition at line 387 of file bliss_automorph.cpp.

Referenced by cmpGraphPair().

allocMemory()

static SCIP_RETCODE allocMemory ( SCIP *  scip, AUT_COLOR *  colorinfo, int  nconss, int  nvars  )

static

constructor for colorinfo arrays

Parameters

scip	SCIP data structure
colorinfo	struct to save intermediate information
nconss	number of constraints
nvars	number of variables

Definition at line 402 of file bliss_automorph.cpp.

Referenced by setuparrays().

allocMemoryNewDetection()

static SCIP_RETCODE allocMemoryNewDetection ( SCIP *  scip, gcg::DETPROBDATA *  detprobdata, AUT_COLOR *  colorinfo, int  nconss, int  nvars, int  ncoeffs  )

static

constructor for colorinfo arrays

Parameters

scip	SCIP data structure
detprobdata	SCIP data structure
colorinfo	struct to save intermediate information
nconss	number of constraints
nvars	number of variables
ncoeffs	number of coefficients

Definition at line 417 of file bliss_automorph.cpp.

Referenced by cmpGraphPair().

reallocMemory()

static SCIP_RETCODE reallocMemory ( SCIP *  scip, AUT_COLOR *  colorinfo, int  nconss, int  nvars  )

static

reallocate colorinfo arrays with new size

Parameters

scip	problem information
colorinfo	struct to save intermediate information
nconss	number of constraints
nvars	number of variables

Definition at line 436 of file bliss_automorph.cpp.

Referenced by setuparrays().

freeMemory()

static SCIP_RETCODE freeMemory ( SCIP *  scip, AUT_COLOR *  colorinfo  )

static

destructor for colorinfoarrays

Parameters

scip	SCIP data structure
colorinfo	struct to save intermediate information

Definition at line 453 of file bliss_automorph.cpp.

Referenced by cmpGraphPair().

setuparrays()

static SCIP_RETCODE setuparrays ( SCIP *  origscip, SCIP **  scips, int  nscips, AUT_COLOR *  colorinfo, SCIP_RESULT *  result  )

static

set up a help structure for graph creation

Parameters

origscip	SCIP data structure
scips	SCIPs to compare
nscips	number of SCIPs
colorinfo	data structure to save intermediate data
result	result pointer to indicate success or failure

Definition at line 481 of file bliss_automorph.cpp.

References allocMemory(), GCGconsGetNVars(), GCGconsGetVals(), GCGgetNMasterConss(), GCGgetOrigMasterConss(), and reallocMemory().

Referenced by cmpGraphPair().

setuparraysnewdetection()

static SCIP_RETCODE setuparraysnewdetection ( SCIP *  scip, gcg::DETPROBDATA *  detprobdata, gcg::PARTIALDECOMP *  partialdec, int  nblocks, std::vector< int >  blocks, AUT_COLOR *  colorinfo, SCIP_RESULT *  result  )

static

set up a help structure for graph creation for new detection loop

Parameters

scip	SCIP data structure
detprobdata	detprobdata corresponing to presolved or unpresolved problem
partialdec	partial decomp the symmetry for two blocks is checked for
nblocks	number of blocks the symmetry should be checked for
blocks	vectors of block indices the symmetry be checked for
colorinfo	data structure to save intermediate data
result	result pointer to indicate success or failure

Definition at line 629 of file bliss_automorph.cpp.

References gcg::DETPROBDATA::getCons(), gcg::PARTIALDECOMP::getConssForBlock(), gcg::PARTIALDECOMP::getMasterconss(), gcg::PARTIALDECOMP::getNConssForBlock(), gcg::PARTIALDECOMP::getNMasterconss(), gcg::PARTIALDECOMP::getNVarsForBlock(), gcg::DETPROBDATA::getNVarsForCons(), gcg::DETPROBDATA::getVal(), gcg::DETPROBDATA::getVar(), gcg::PARTIALDECOMP::getVarsForBlock(), and gcg::DETPROBDATA::getVarsForCons().

Referenced by cmpGraphPair().

createGraph()

static SCIP_RETCODE createGraph ( SCIP *  origscip, SCIP **  scips, int  nscips, int *  pricingindices, AUT_COLOR  colorinfo, bliss::Graph *  graph, int *  pricingnodes, SCIP_RESULT *  result  )

static

create a graph out of an array of scips

Parameters

origscip	SCIP data structure
scips	SCIPs to compare
nscips	number of SCIPs
pricingindices	indices of the given pricing problems
colorinfo	data structure to save coloring information for conss, vars, and coeffs
graph	graph needed for discovering isomorphism
pricingnodes	number of pricing nodes without master
result	result pointer to indicate success or failure

Definition at line 772 of file bliss_automorph.cpp.

References GCGconsGetNVars(), GCGconsGetVals(), GCGconsGetVars(), GCGgetNMasterConss(), GCGgetOrigMasterConss(), GCGoriginalVarGetPricingVar(), GCGoriginalVarIsLinking(), and GCGvarGetBlock().

Referenced by cmpGraphPair().

createGraphNewDetection()

static SCIP_RETCODE createGraphNewDetection ( SCIP *  scip, gcg::DETPROBDATA *  detprobdata, gcg::PARTIALDECOMP *  partialdec, int  nblocks, std::vector< int >  blocks, AUT_COLOR  colorinfo, bliss::Graph *  graph, int *  pricingnodes, SCIP_RESULT *  result  )

static

create a graph out of an array of scips

experimental

Parameters

scip	SCIP data structure
detprobdata	detection process information and data
partialdec	partial decomposition
nblocks	number of blocks the symmetry should be checked for
blocks	vectors of block indices the symmetry be checked for
colorinfo	data structure to save intermediate data
graph	graph needed for discovering isomorphism
pricingnodes	number of pricing nodes without master
result	result pointer to indicate success or failure

Definition at line 1032 of file bliss_automorph.cpp.

References gcg::DETPROBDATA::getCons(), gcg::PARTIALDECOMP::getConssForBlock(), gcg::PARTIALDECOMP::getMasterconss(), gcg::PARTIALDECOMP::getNConssForBlock(), gcg::PARTIALDECOMP::getNMasterconss(), gcg::PARTIALDECOMP::getNVarsForBlock(), gcg::DETPROBDATA::getNVarsForCons(), gcg::DETPROBDATA::getScip(), gcg::DETPROBDATA::getVal(), gcg::DETPROBDATA::getVar(), gcg::PARTIALDECOMP::getVarProbindexForBlock(), gcg::PARTIALDECOMP::getVarsForBlock(), gcg::DETPROBDATA::getVarsForCons(), and gcg::PARTIALDECOMP::isVarBlockvarOfBlock().

Referenced by cmpGraphPair().

cmpGraphPair() [1/2]

SCIP_RETCODE cmpGraphPair	(	SCIP *	origscip,
		SCIP *	scip1,
		SCIP *	scip2,
		int	prob1,
		int	prob2,
		SCIP_RESULT *	result,
		SCIP_HASHMAP *	varmap,
		SCIP_HASHMAP *	consmap,
		unsigned int	searchnodelimit,
		unsigned int	generatorlimit
	)

compare two graphs w.r.t. automorphism

Parameters

origscip	SCIP data structure
scip1	first SCIP data structure to compare
scip2	second SCIP data structure to compare
prob1	index of first pricing prob
prob2	index of second pricing prob
result	result pointer to indicate success or failure
varmap	hashmap to save permutation of variables
consmap	hashmap to save permutation of constraints
searchnodelimit	bliss search node limit (requires patched bliss version)
generatorlimit	bliss generator limit (requires patched bliss version)

Definition at line 1334 of file bliss_automorph.cpp.

References createGraph(), fhook(), freeMemory(), AUT_HOOK2::getBool(), AUT_HOOK2::ncalls, setuparrays(), testScipCons(), and testScipVars().

Referenced by pricingprobsAreIdentical().

cmpGraphPair() [2/2]

SCIP_RETCODE cmpGraphPair	(	SCIP *	scip,
		gcg::PARTIALDECOMP *	partialdec,
		int	block1,
		int	block2,
		SCIP_RESULT *	result,
		SCIP_HASHMAP *	varmap,
		SCIP_HASHMAP *	consmap,
		unsigned int	searchnodelimit,
		unsigned int	generatorlimit
	)

compare two graphs w.r.t. automorphism

Parameters

scip	SCIP data structure
partialdec	partialdec the graphs should be compared for
block1	index of first pricing prob
block2	index of second pricing prob
result	result pointer to indicate success or failure
varmap	hashmap to save permutation of variables
consmap	hashmap to save permutation of constraints
searchnodelimit	bliss search node limit (requires patched bliss version)
generatorlimit	bliss generator limit (requires patched bliss version)

Definition at line 1385 of file bliss_automorph.cpp.

References allocMemoryNewDetection(), createGraphNewDetection(), fhook(), freeMemory(), GCGconshdlrDecompGetDetprobdataOrig(), GCGconshdlrDecompGetDetprobdataPresolved(), AUT_HOOK2::getBool(), gcg::PARTIALDECOMP::getNCoeffsForBlock(), gcg::PARTIALDECOMP::getNCoeffsForMaster(), gcg::PARTIALDECOMP::getNConssForBlock(), gcg::PARTIALDECOMP::getNMasterconss(), gcg::PARTIALDECOMP::getNVarsForBlock(), gcg::PARTIALDECOMP::isAssignedToOrigProb(), AUT_HOOK2::ncalls, AUT_HOOK2::setNewDetectionStuff(), and setuparraysnewdetection().