Scippy

GCG

Branch-and-Price & Column Generation for Everyone

gcg::GraphAlgorithms< T > Class Template Reference

Detailed Description

template<class T>
class gcg::GraphAlgorithms< T >

Definition at line 53 of file graphalgorithms.h.

#include <graphalgorithms.h>

Static Public Member Functions

static SCIP_Real computeSoed (Hypergraph< T > &graph)
 
static SCIP_Real computeMincut (Hypergraph< T > &graph)
 
static SCIP_Real computekMetric (Hypergraph< T > &graph)
 
static std::vector< int > dbscan (Graph< GraphGCG > &graph, double eps, int minPts=4)
 
static std::vector< int > mst (Graph< GraphGCG > &graph, double cutoff, int minPts=4)
 
static std::vector< int > mcl (Graph< GraphGCG > &graph, int &stoppedAfter, double inflatefac, int maxiters=25, int expandfac=2)
 
static void expandCluster (Graph< T > &graph, std::vector< bool > &visited, std::vector< bool > &is_core, std::vector< int > &labels, int point, std::vector< int > &NeighborPts, int curr_cluster, double eps, int minPts)
 
static bool cutoffif (EdgeGCG &a)
 
static int weightComp (const void *a, const void *b)
 
static int mstfind (std::vector< subset > &subsets, int i)
 
static void mstunion (std::vector< subset > &subsets, int x, int y)
 

Static Public Attributes

static double cutoff = 0.0
 

Member Function Documentation

◆ computeSoed()

template<class T >
double gcg::GraphAlgorithms< T >::computeSoed ( Hypergraph< T > &  graph)
static

compute weighted sum of external degrees

Parameters
graphthe hypergraph

Definition at line 59 of file graphalgorithms_def.h.

References gcg::Hypergraph< T >::getHyperedgeNodes(), gcg::Hypergraph< T >::getHyperedgeWeight(), gcg::Hypergraph< T >::getNHyperedges(), gcg::GraphInterface::getPartition(), and partition().

◆ computeMincut()

template<class T >
double gcg::GraphAlgorithms< T >::computeMincut ( Hypergraph< T > &  graph)
static

◆ computekMetric()

template<class T >
double gcg::GraphAlgorithms< T >::computekMetric ( Hypergraph< T > &  graph)
static

◆ dbscan()

template<class T >
std::vector< int > gcg::GraphAlgorithms< T >::dbscan ( Graph< GraphGCG > &  graph,
double  eps,
int  minPts = 4 
)
static

run DBSCAN on the distance graph

Parameters
graphthe graph with weighted edges
epsradius in which we search for the neighbors
minPtsminimum number of neighbors needed to define a core point (can be fixed to 4 as stated in the paper)

Definition at line 135 of file graphalgorithms_def.h.

References gcg::Graph< T >::getNeighborWeights(), and gcg::Graph< T >::getNNodes().

Referenced by gcg::RowGraphWeighted< T >::computePartitionDBSCAN(), and gcg::RowGraphWeighted< T >::computePartitionDBSCANForPartialGraph().

◆ mst()

template<class T >
std::vector< int > gcg::GraphAlgorithms< T >::mst ( Graph< GraphGCG > &  graph,
double  cutoff,
int  minPts = 4 
)
static

run MST on the distance graph

Parameters
graphthe graph with weighted edges
cutoffthreshold below which we cut the edges
minPtsminimum number of points needed in a cluster

Definition at line 260 of file graphalgorithms_def.h.

References gcg::EdgeGCG::dest, gcg::Graph< T >::getEdges(), gcg::Graph< T >::getNEdges(), gcg::Graph< T >::getNNodes(), and gcg::EdgeGCG::src.

Referenced by gcg::RowGraphWeighted< T >::computePartitionMST(), and gcg::RowGraphWeighted< T >::computePartitionMSTForPartialGraph().

◆ mcl()

template<class T >
std::vector< int > gcg::GraphAlgorithms< T >::mcl ( Graph< GraphGCG > &  graph,
int &  stoppedAfter,
double  inflatefac,
int  maxiters = 25,
int  expandfac = 2 
)
static

run MCL on the similarity graph

Parameters
graphthe graph with weighted edges
stoppedAfternumber of iterations after which the clustering terminated
inflatefacinflate factor
maxitersmax number of iterations, set to 25 per default
expandfacexpand factor, should be always set to 2

Definition at line 434 of file graphalgorithms_def.h.

Referenced by gcg::RowGraphWeighted< T >::computePartitionMCL(), and gcg::RowGraphWeighted< T >::computePartitionMCLForPartialGraph().

◆ expandCluster()

template<class T >
void gcg::GraphAlgorithms< T >::expandCluster ( Graph< T > &  graph,
std::vector< bool > &  visited,
std::vector< bool > &  is_core,
std::vector< int > &  labels,
int  point,
std::vector< int > &  NeighborPts,
int  curr_cluster,
double  eps,
int  minPts 
)
static

help function for DBSCAN

Definition at line 201 of file graphalgorithms_def.h.

References gcg::Graph< T >::getNeighborWeights().

◆ cutoffif()

template<class T >
bool gcg::GraphAlgorithms< T >::cutoffif ( EdgeGCG a)
static

Definition at line 378 of file graphalgorithms_def.h.

References gcg::EdgeGCG::weight.

◆ weightComp()

template<class T >
int gcg::GraphAlgorithms< T >::weightComp ( const void *  a,
const void *  b 
)
static

Definition at line 387 of file graphalgorithms_def.h.

References gcg::EdgeGCG::weight.

◆ mstfind()

template<class T >
int gcg::GraphAlgorithms< T >::mstfind ( std::vector< subset > &  subsets,
int  i 
)
static

Definition at line 398 of file graphalgorithms_def.h.

◆ mstunion()

template<class T >
void gcg::GraphAlgorithms< T >::mstunion ( std::vector< subset > &  subsets,
int  x,
int  y 
)
static

Definition at line 411 of file graphalgorithms_def.h.

Field Documentation

◆ cutoff

template<typename T >
double gcg::GraphAlgorithms< T >::cutoff = 0.0
static

Definition at line 114 of file graphalgorithms.h.