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

template<class T >
double gcg::GraphAlgorithms< T >::computekMetric ( Hypergraph< T > &  graph)
static
template<class T >
double gcg::GraphAlgorithms< T >::computeMincut ( Hypergraph< T > &  graph)
static
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().

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

Definition at line 378 of file graphalgorithms_def.h.

References gcg::EdgeGCG::weight.

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().

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().

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
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().

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().

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

Definition at line 398 of file graphalgorithms_def.h.

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.

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.

Member Data Documentation

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

Definition at line 114 of file graphalgorithms.h.