Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ModifiedNibbleClusterer.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/Graph.h>
36#include <ogdf/basic/geometry.h>
37
38#include <vector>
39
40namespace ogdf {
41
43
56public:
65
67#if 0
68 delete m_pGC;
69#endif
70 }
71
72 //TODO add a call with GraphAttributes and store in intweight
73
77
85
88 // TODO long call(ClusterGraph &C, Graph & G) {}
89 void setMaxClusterNum(int i) { maxClusterNum = i; }
90
91 void setMaxClusterSize(long i) { m_maxClusterSize = i; }
92
93 // Smaller clusters are joint with a neighbor (non-recursive) as a postprocessing
94 void setClusterSizeThreshold(int threshold) {
95 if (threshold > 0) {
96 m_clusterThreshold = threshold;
97 }
98 }
99
101
102protected:
103 void initialize(); //1< Initialize values for calculation before first step
106 std::vector<node>& bestCluster);
107 double findBestCluster(NodeArray<bool>& isActive, std::vector<node>& activeNodes,
108 std::vector<node>& cluster);
109 void spreadValues(NodeArray<bool>& isActive, std::vector<node>& activeNodes,
111
112 inline long maxClusterSize() { return m_maxClusterSize; }
113
114 // Arithmetic plus Geometric Progression
115 int aPGP(int i) {
116 const int a = 2;
117 const int d = 7;
118 const double r = 1.5;
119 return static_cast<int>(ceil(a * pot(r, i))) + i * d + a;
120 }
121
122 // TODO we expect i to be very small, but do this efficiently anyway
123 double pot(double r, long i) { return pow(r, static_cast<double>(i)); }
124
126 const int factor = 25;
127 //does not make sense to set it to 500 as they did, as we want less clusters.
128 return factor * m_maxClusterSize;
129 }
130
132
133private:
135 int m_clusterThreshold; // Below that size all remaining nodes are just packed in a cluster
137 long m_maxActiveNodes; // Bound on number of nodes in active set
139 double m_spreadProbability; //how much is spread, i.e. 1-val is the prob to stay at the node
140 node m_startNode; // Node to start a walk from
141 NodeArray<double> m_prob; // Probability of a node along the walk
145
146 // Tests
148 double sum = 0.0;
149 for (node v : m_pGC->nodes) {
150 sum += m_prob[v];
151 }
152 return OGDF_GEOM_ET.equal(sum, 1.0);
153 }
154};
155
156}
Includes declaration of graph class.
Declaration of graph copy classes.
Declaration of classes GenericPoint, GenericPolyline, GenericLine, GenericSegment,...
Representation of clusters in a clustered graph.
std::enable_if< std::is_integral< T >::value, bool >::type equal(const T &x, const T &y) const
Compare if x is EQUAL to y for integral types.
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition Graph_d.h:589
The modified nibble clustering algorithm.
void modifiedNibble(node snode, std::vector< node > &bestCluster)
main step with walks starting from snode
long call(Graph &G, NodeArray< long > &clusterNum)
Call method: Creates a clustering of G Returns number of created clusters and sets cluster index for ...
void spreadValues(NodeArray< bool > &isActive, std::vector< node > &activeNodes, NodeArray< double > &probUpdate)
node selectStartNode()
select start node according to some strategy
double findBestCluster(NodeArray< bool > &isActive, std::vector< node > &activeNodes, std::vector< node > &cluster)
long call(Graph &G, NodeArray< long > &clusterNum, NodeArray< long > &topLevelNum)
A convenience method. Due to the characteristics of the algorithm (not very accurate,...
void setMaxClusterNum(int i)
Call method: Creates a clustering of G in C Returns number of created clusters.
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
int r[]
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
const EpsilonTest OGDF_GEOM_ET