Graph Drawing

 v. 2023.09 (Elderberry)

No Matches
Go to the documentation of this file.
36#pragma once
40namespace ogdf {
54 explicit Clusterer(const Graph& G);
61 virtual ~Clusterer() { }
63 //The clustering can be done recursively (use single threshold
64 //on component to delete weak edges (recompute strengths)) or
65 //by applying a set of thresholds, set the behaviour in
66 //function setRecursive
69 //set the thresholds defining the hierarchy assignment decision
70 //should be dependent on the used metrics
73 //thresholds are computed from edge strengths to split off
74 //at least some edges as long as there is a difference between
75 //min and max strength (progressive clustering)
76 //set this value to 0 to use your own or the default values
77 void setAutomaticThresholds(int numValues) { m_autoThreshNum = numValues; }
79 //for recursive clustering, only the first threshold is used
80 void setRecursive(bool b) { m_recursive = b; }
82 //preliminary
86 virtual void createClusterGraph(ClusterGraph& C) override;
88 void setStopIndex(double stop) { m_stopIndex = stop; }
90 //compute a clustering index for node v
91 //number of connections in neighborhood compared to clique
92 virtual double computeCIndex(node v) override { return computeCIndex(*m_pGraph, v); }
94 virtual double computeCIndex(const Graph& G, node v) override {
95 OGDF_ASSERT(v->graphOf() == &G);
96 if (v->degree() < 2) {
97 return 1.0;
98 }
99 int conns = 0; //connections, without v
100 NodeArray<bool> neighbor(G, false);
101 for (adjEntry adjE : v->adjEntries) {
102 neighbor[adjE->twinNode()] = true;
103 }
104 for (adjEntry adjE : v->adjEntries) {
105 for (adjEntry adjEE : adjE->twinNode()->adjEntries) {
106 if (neighbor[adjEE->twinNode()]) {
107 conns++;
108 }
109 }
110 }
111 //connections were counted twice
112 double index = conns / 2.0;
113 return index / (v->degree() * (v->degree() - 1));
114 }
117 EdgeArray<double> m_edgeValue; //strength value for edge clustering index
118 NodeArray<double> m_vertexValue; //clustering index for vertices
119 List<double> m_thresholds; //clustering level thresholds
120 List<double> m_autoThresholds; //automatically generated values (dep. on graph instance)
121 List<double> m_defaultThresholds; //some default values
122 double m_stopIndex; //average clustering index when recursive clustering stops
123 //between 0 and 1
124 bool m_recursive; //recursive clustering or list of tresholds
125#if 0
126 bool m_autoThresholds; //compute thresholds according to edge strengths
128 int m_autoThreshNum; //number of thresholds to be computed
Declaration of interface for clustering algorithms that compute a clustering for a given graph based ...
Class for adjacency list elements.
Definition Graph_d.h:79
Representation of clustered graphs.
Clustering is determined based on the threshold values (connectivity thresholds determine edges to be...
Definition Clusterer.h:51
Clusterer(const Graph &G)
Constructor taking a graph G to be clustered.
virtual double computeCIndex(const Graph &G, node v) override
compute a clustering index for each vertex
Definition Clusterer.h:94
virtual ~Clusterer()
Definition Clusterer.h:61
void setClusteringThresholds(const List< double > &threshs)
double m_stopIndex
Definition Clusterer.h:122
List< double > m_defaultThresholds
Definition Clusterer.h:121
Default constructor allowing to cluster multiple graphs with the same instance of the Clusterer graph...
void setAutomaticThresholds(int numValues)
Definition Clusterer.h:77
List< double > m_autoThresholds
Definition Clusterer.h:120
virtual double computeCIndex(node v) override
compute a clustering index for each vertex
Definition Clusterer.h:92
void setStopIndex(double stop)
Definition Clusterer.h:88
void computeEdgeStrengths(EdgeArray< double > &strength)
EdgeArray< double > m_edgeValue
Definition Clusterer.h:117
virtual void computeClustering(SList< SimpleCluster * > &sl) override
compute some kind of clustering on the graph m_pGraph
virtual void createClusterGraph(ClusterGraph &C) override
translate computed clustering into cluster hierarchy in cluster graph C
List< double > m_thresholds
Definition Clusterer.h:119
void setRecursive(bool b)
Definition Clusterer.h:80
NodeArray< double > m_vertexValue
Definition Clusterer.h:118
void computeEdgeStrengths(const Graph &G, EdgeArray< double > &strength)
Interface for algorithms that compute a clustering for a given graph.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition Graph_d.h:220
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition Graph_d.h:208
Singly linked lists (maintaining the length of the list).
Definition SList.h:833
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/ for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.