dec_dbscan.cpp File Reference

Detailed Description

detector DBSCAN

Author

Igor Pesic

Note

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

This detector performs DBSCAN clustering.

Definition in file dec_dbscan.cpp.

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

Go to the source code of this file.

Data Structures
struct	DEC_DetectorData

Macros
#define	DEC_DETECTORNAME   "dbscan"
#define	DEC_DESC   "detector based on DBSCAN clustering"
#define	DEC_PRIORITY   901
#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   'D'
#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	finishPartialdecDBSCAN   NULL
#define	detectorPostprocessPartialdecDBSCAN   NULL

Functions
static std::vector< double >	getEpsList (int length, double mid, bool isintersection)
static	DEC_DECL_FREEDETECTOR (freeDBSCAN)
static	DEC_DECL_EXITDETECTOR (exitDBSCAN)
static	DEC_DECL_INITDETECTOR (initDBSCAN)
static bool	graphCompletible (gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec)
static	DEC_DECL_PROPAGATEPARTIALDEC (propagatePartialdecDBSCAN)
static	DEC_DECL_SETPARAMAGGRESSIVE (setParamAggressiveDBSCAN)
static	DEC_DECL_SETPARAMDEFAULT (setParamDefaultDBSCAN)
static	DEC_DECL_SETPARAMFAST (setParamFastDBSCAN)
SCIP_RETCODE	SCIPincludeDetectorDBSCAN (SCIP *scip)

Macro Definition Documentation

DEC_DETECTORNAME

#define DEC_DETECTORNAME   "dbscan"

name of detector

Definition at line 55 of file dec_dbscan.cpp.

DEC_DESC

#define DEC_DESC   "detector based on DBSCAN clustering"

description of detector

Definition at line 56 of file dec_dbscan.cpp.

DEC_PRIORITY

#define DEC_PRIORITY   901

priority of the constraint handler for separation

Definition at line 57 of file dec_dbscan.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_dbscan.cpp.

DEC_MAXCALLROUND

#define DEC_MAXCALLROUND   INT_MAX

last round the detector gets called

Definition at line 59 of file dec_dbscan.cpp.

DEC_MINCALLROUND

#define DEC_MINCALLROUND   0

first round the detector gets called

Definition at line 60 of file dec_dbscan.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_dbscan.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_dbscan.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_dbscan.cpp.

DEC_DECCHAR

#define DEC_DECCHAR   'D'

display character of detector

Definition at line 64 of file dec_dbscan.cpp.

DEC_ENABLED

#define DEC_ENABLED   FALSE

should the detection be enabled

Definition at line 65 of file dec_dbscan.cpp.

DEC_ENABLEDFINISHING

#define DEC_ENABLEDFINISHING   FALSE

should the finishing be enabled

Definition at line 66 of file dec_dbscan.cpp.

DEC_ENABLEDPOSTPROCESSING

#define DEC_ENABLEDPOSTPROCESSING   FALSE

should the postprocessing be enabled

Definition at line 67 of file dec_dbscan.cpp.

DEC_SKIP

#define DEC_SKIP   FALSE

should detector be skipped if other detectors found decompositions

Definition at line 68 of file dec_dbscan.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_dbscan.cpp.

DEFAULT_N_ITERATIONS

#define DEFAULT_N_ITERATIONS   51

Definition at line 73 of file dec_dbscan.cpp.

DEFAULT_JOHNSON_ENABLE

#define DEFAULT_JOHNSON_ENABLE   true

Definition at line 74 of file dec_dbscan.cpp.

DEFAULT_INTERSECTION_ENABLE

#define DEFAULT_INTERSECTION_ENABLE   false

Definition at line 75 of file dec_dbscan.cpp.

DEFAULT_JACCARD_ENABLE

#define DEFAULT_JACCARD_ENABLE   false

Definition at line 76 of file dec_dbscan.cpp.

DEFAULT_COSINE_ENABLE

#define DEFAULT_COSINE_ENABLE   false

Definition at line 77 of file dec_dbscan.cpp.

DEFAULT_SIMPSON_ENABLE

#define DEFAULT_SIMPSON_ENABLE   false

Definition at line 78 of file dec_dbscan.cpp.

DEFAULT_POSTPROC_ENABLE

#define DEFAULT_POSTPROC_ENABLE   true

Definition at line 79 of file dec_dbscan.cpp.

MAX_N_BLOCKS

#define MAX_N_BLOCKS   100

Definition at line 80 of file dec_dbscan.cpp.

finishPartialdecDBSCAN

#define finishPartialdecDBSCAN   NULL

Definition at line 478 of file dec_dbscan.cpp.

detectorPostprocessPartialdecDBSCAN

#define detectorPostprocessPartialdecDBSCAN   NULL

Definition at line 479 of file dec_dbscan.cpp.

Function Documentation

getEpsList()

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

static

Definition at line 106 of file dec_dbscan.cpp.

Referenced by DEC_DECL_PROPAGATEPARTIALDEC().

DEC_DECL_FREEDETECTOR()

static DEC_DECL_FREEDETECTOR ( freeDBSCAN  )

static

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

Definition at line 154 of file dec_dbscan.cpp.

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

DEC_DECL_EXITDETECTOR()

static DEC_DECL_EXITDETECTOR ( exitDBSCAN  )

static

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

Definition at line 171 of file dec_dbscan.cpp.

DEC_DECL_INITDETECTOR()

static DEC_DECL_INITDETECTOR ( initDBSCAN  )

static

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

Definition at line 179 of file dec_dbscan.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 197 of file dec_dbscan.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 ( propagatePartialdecDBSCAN  )

static

Definition at line 249 of file dec_dbscan.cpp.

References gcg::RowGraphWeighted< T >::computePartitionDBSCANForPartialGraph(), 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 ( setParamAggressiveDBSCAN  )

static

Definition at line 482 of file dec_dbscan.cpp.

References DECdetectorGetName().

DEC_DECL_SETPARAMDEFAULT()

static DEC_DECL_SETPARAMDEFAULT ( setParamDefaultDBSCAN  )

static

Definition at line 498 of file dec_dbscan.cpp.

References DEC_ENABLED, DEC_ENABLEDFINISHING, and DECdetectorGetName().

DEC_DECL_SETPARAMFAST()

static DEC_DECL_SETPARAMFAST ( setParamFastDBSCAN  )

static

Definition at line 514 of file dec_dbscan.cpp.

References DECdetectorGetName().

SCIPincludeDetectorDBSCAN()

SCIP_RETCODE SCIPincludeDetectorDBSCAN

(

SCIP *

scip

)

creates the handler for xyz detector and includes it in SCIP

Parameters

scip	SCIP data structure

Definition at line 537 of file dec_dbscan.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, detectorPostprocessPartialdecDBSCAN, finishPartialdecDBSCAN, 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().