dec_mst.cpp File Reference

Detailed Description

minimum spanning tree clustering detector

Author

Igor Pesic

Note

requires package to be installed: GSL library, requires flag to be set: GSL=true

This detector performs minimum spanning tree clustering.

Definition in file dec_mst.cpp.

#include <time.h>
#include "dec_mst.h"
#include "cons_decomp.h"
#include "graph/matrixgraph.h"
#include "graph/rowgraph_weighted.h"
#include "graph/graph_gcg.h"
#include "scip/clock.h"

Go to the source code of this file.

Data Structures
struct	DEC_DetectorData

Macros
#define	DEC_DETECTORNAME   "mst"
#define	DEC_DESC   "detector based on MST clustering"
#define	DEC_PRIORITY   910
#define	DEC_FREQCALLROUND   1
#define	DEC_MAXCALLROUND   INT_MAX
#define	DEC_MINCALLROUND   0
#define	DEC_FREQCALLROUNDORIGINAL   1
#define	DEC_MAXCALLROUNDORIGINAL   INT_MAX
#define	DEC_MINCALLROUNDORIGINAL   0
#define	DEC_DECCHAR   'M'
#define	DEC_ENABLED   FALSE
#define	DEC_ENABLEDFINISHING   FALSE
#define	DEC_ENABLEDPOSTPROCESSING   FALSE
#define	DEC_SKIP   FALSE
#define	DEC_USEFULRECALL   FALSE
#define	DEFAULT_N_ITERATIONS   51
#define	DEFAULT_JOHNSON_ENABLE   true
#define	DEFAULT_INTERSECTION_ENABLE   false
#define	DEFAULT_JACCARD_ENABLE   false
#define	DEFAULT_COSINE_ENABLE   false
#define	DEFAULT_SIMPSON_ENABLE   false
#define	DEFAULT_POSTPROC_ENABLE   true
#define	MAX_N_BLOCKS   100
#define	finishPartialdecMST   NULL
#define	detectorPostprocessPartialdecMST   NULL

Functions
static std::vector< double >	getEpsList (int length, double mid, bool isintersection)
static	DEC_DECL_FREEDETECTOR (freeMST)
static	DEC_DECL_EXITDETECTOR (exitMST)
static	DEC_DECL_INITDETECTOR (initMST)
static bool	graphCompletible (gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec)
static	DEC_DECL_PROPAGATEPARTIALDEC (propagatePartialdecMST)
static	DEC_DECL_SETPARAMAGGRESSIVE (setParamAggressiveMST)
static	DEC_DECL_SETPARAMDEFAULT (setParamDefaultMST)
static	DEC_DECL_SETPARAMFAST (setParamFastMST)
SCIP_RETCODE	SCIPincludeDetectorMST (SCIP *scip)

Macro Definition Documentation

DEC_DETECTORNAME

#define DEC_DETECTORNAME   "mst"

name of detector

Definition at line 55 of file dec_mst.cpp.

DEC_DESC

#define DEC_DESC   "detector based on MST clustering"

description of detector

Definition at line 56 of file dec_mst.cpp.

DEC_PRIORITY

#define DEC_PRIORITY   910

priority of the constraint handler for separation

Definition at line 57 of file dec_mst.cpp.

DEC_FREQCALLROUND

#define DEC_FREQCALLROUND   1

frequency the detector gets called in detection loop, i.e. it is called in round r if and only if minCallRound <= r <= maxCallRound AND (r - minCallRound) mod freqCallRound == 0

Definition at line 58 of file dec_mst.cpp.

DEC_MAXCALLROUND

#define DEC_MAXCALLROUND   INT_MAX

last round the detector gets called

Definition at line 59 of file dec_mst.cpp.

DEC_MINCALLROUND

#define DEC_MINCALLROUND   0

first round the detector gets called

Definition at line 60 of file dec_mst.cpp.

DEC_FREQCALLROUNDORIGINAL

#define DEC_FREQCALLROUNDORIGINAL   1

frequency the detector gets called in detection loop while detecting the original problem

Definition at line 61 of file dec_mst.cpp.

DEC_MAXCALLROUNDORIGINAL

#define DEC_MAXCALLROUNDORIGINAL   INT_MAX

last round the detector gets called while detecting the original problem

Definition at line 62 of file dec_mst.cpp.

DEC_MINCALLROUNDORIGINAL

#define DEC_MINCALLROUNDORIGINAL   0

first round the detector gets called while detecting the original problem

Definition at line 63 of file dec_mst.cpp.

DEC_DECCHAR

#define DEC_DECCHAR   'M'

display character of detector

Definition at line 64 of file dec_mst.cpp.

DEC_ENABLED

#define DEC_ENABLED   FALSE

should the detection be enabled

Definition at line 65 of file dec_mst.cpp.

DEC_ENABLEDFINISHING

#define DEC_ENABLEDFINISHING   FALSE

should the finishing be enabled

Definition at line 66 of file dec_mst.cpp.

DEC_ENABLEDPOSTPROCESSING

#define DEC_ENABLEDPOSTPROCESSING   FALSE

should the postprocessing be enabled

Definition at line 67 of file dec_mst.cpp.

DEC_SKIP

#define DEC_SKIP   FALSE

should detector be skipped if other detectors found decompositions

Definition at line 68 of file dec_mst.cpp.

DEC_USEFULRECALL

#define DEC_USEFULRECALL   FALSE

is it useful to call this detector on a descendant of the propagated partialdec

Definition at line 69 of file dec_mst.cpp.

DEFAULT_N_ITERATIONS

#define DEFAULT_N_ITERATIONS   51

Definition at line 72 of file dec_mst.cpp.

DEFAULT_JOHNSON_ENABLE

#define DEFAULT_JOHNSON_ENABLE   true

Definition at line 73 of file dec_mst.cpp.

DEFAULT_INTERSECTION_ENABLE

#define DEFAULT_INTERSECTION_ENABLE   false

Definition at line 74 of file dec_mst.cpp.

DEFAULT_JACCARD_ENABLE

#define DEFAULT_JACCARD_ENABLE   false

Definition at line 75 of file dec_mst.cpp.

DEFAULT_COSINE_ENABLE

#define DEFAULT_COSINE_ENABLE   false

Definition at line 76 of file dec_mst.cpp.

DEFAULT_SIMPSON_ENABLE

#define DEFAULT_SIMPSON_ENABLE   false

Definition at line 77 of file dec_mst.cpp.

DEFAULT_POSTPROC_ENABLE

#define DEFAULT_POSTPROC_ENABLE   true

Definition at line 78 of file dec_mst.cpp.

MAX_N_BLOCKS

#define MAX_N_BLOCKS   100

Definition at line 79 of file dec_mst.cpp.

finishPartialdecMST

#define finishPartialdecMST   NULL

Definition at line 488 of file dec_mst.cpp.

detectorPostprocessPartialdecMST

#define detectorPostprocessPartialdecMST   NULL

Definition at line 490 of file dec_mst.cpp.

Function Documentation

getEpsList()

static std::vector<double> getEpsList ( int  length, double  mid, bool  isintersection  )

static

Definition at line 105 of file dec_mst.cpp.

Referenced by DEC_DECL_PROPAGATEPARTIALDEC().

DEC_DECL_FREEDETECTOR()

static DEC_DECL_FREEDETECTOR ( freeMST  )

static

destructor of detector to free user data (called when GCG is exiting)

Definition at line 153 of file dec_mst.cpp.

References DEC_DETECTORNAME, DECdetectorGetData(), and DECdetectorGetName().

DEC_DECL_EXITDETECTOR()

static DEC_DECL_EXITDETECTOR ( exitMST  )

static

destructor of detector to free detector data (called before the solving process begins)

Definition at line 170 of file dec_mst.cpp.

DEC_DECL_INITDETECTOR()

static DEC_DECL_INITDETECTOR ( initMST  )

static

detection initialization function of detector (called before solving is about to begin)

Definition at line 178 of file dec_mst.cpp.

References DEC_DETECTORNAME, DECdetectorGetData(), DECdetectorGetName(), DEC_DetectorData::found, and DEC_DetectorData::n_similarities.

graphCompletible()

static bool graphCompletible ( gcg::DETPROBDATA *  detprobdata, gcg::PARTIALDECOMP *  partialdec  )

static

are there conss and vars to be included by the graph and have the conss common vars included by the graph

Definition at line 196 of file dec_mst.cpp.

References gcg::PARTIALDECOMP::getNOpenconss(), gcg::PARTIALDECOMP::getNOpenvars(), gcg::DETPROBDATA::getNVarsForCons(), gcg::PARTIALDECOMP::getOpenconss(), gcg::PARTIALDECOMP::getOpenvars(), gcg::DETPROBDATA::getVarsForCons(), and gcg::PARTIALDECOMP::isVarOpenvar().

Referenced by DEC_DECL_PROPAGATEPARTIALDEC().

DEC_DECL_PROPAGATEPARTIALDEC()

static DEC_DECL_PROPAGATEPARTIALDEC ( propagatePartialdecMST  )

static

Definition at line 250 of file dec_mst.cpp.

References gcg::RowGraphWeighted< T >::computePartitionMSTForPartialGraph(), gcg::COSINE, DEC_DetectorData::cosineenable, gcg::RowGraphWeighted< T >::createFromPartialMatrix(), gcg::RowGraph< T >::createPartialdecFromPartition(), DECdetectorGetData(), gcg::DIST, DEC_DetectorData::found, getEpsList(), gcg::RowGraphWeighted< T >::getNBlocks(), graphCompletible(), gcg::INTERSECTION, DEC_DetectorData::intersectionenable, gcg::JACCARD, DEC_DetectorData::jaccardenable, gcg::JOHNSON, DEC_DetectorData::johnsonenable, MAX_N_BLOCKS, DEC_DetectorData::n_iterations, DEC_DetectorData::n_similarities, gcg::RowGraphWeighted< T >::nonClustered(), DEC_DetectorData::postprocenable, gcg::PARTIALDECOMP::refineToBlocks(), gcg::SIMPSON, and DEC_DetectorData::simpsonenable.

DEC_DECL_SETPARAMAGGRESSIVE()

static DEC_DECL_SETPARAMAGGRESSIVE ( setParamAggressiveMST  )

static

Definition at line 493 of file dec_mst.cpp.

References DECdetectorGetName().

DEC_DECL_SETPARAMDEFAULT()

static DEC_DECL_SETPARAMDEFAULT ( setParamDefaultMST  )

static

Definition at line 509 of file dec_mst.cpp.

References DEC_ENABLED, DEC_ENABLEDFINISHING, and DECdetectorGetName().

DEC_DECL_SETPARAMFAST()

static DEC_DECL_SETPARAMFAST ( setParamFastMST  )

static

Definition at line 524 of file dec_mst.cpp.

References DECdetectorGetName().

SCIPincludeDetectorMST()

SCIP_RETCODE SCIPincludeDetectorMST

(

SCIP *

scip

)

creates the handler for xyz detector and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 544 of file dec_mst.cpp.

References DEC_DetectorData::cosineenable, DEC_DECCHAR, DEC_DESC, DEC_DETECTORNAME, DEC_ENABLED, DEC_ENABLEDFINISHING, DEC_ENABLEDPOSTPROCESSING, DEC_FREQCALLROUND, DEC_FREQCALLROUNDORIGINAL, DEC_MAXCALLROUND, DEC_MAXCALLROUNDORIGINAL, DEC_MINCALLROUND, DEC_MINCALLROUNDORIGINAL, DEC_PRIORITY, DEC_SKIP, DEC_USEFULRECALL, DECincludeDetector(), DEFAULT_COSINE_ENABLE, DEFAULT_INTERSECTION_ENABLE, DEFAULT_JACCARD_ENABLE, DEFAULT_JOHNSON_ENABLE, DEFAULT_N_ITERATIONS, DEFAULT_POSTPROC_ENABLE, DEFAULT_SIMPSON_ENABLE, detectorPostprocessPartialdecMST, finishPartialdecMST, DEC_DetectorData::found, DEC_DetectorData::intersectionenable, DEC_DetectorData::jaccardenable, DEC_DetectorData::johnsonenable, DEC_DetectorData::n_iterations, DEC_DetectorData::postprocenable, and DEC_DetectorData::simpsonenable.

Referenced by SCIPincludeGcgPlugins().