Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
CliqueFinderHeuristic.h
Go to the documentation of this file.
1
32#pragma once
33
36
37namespace ogdf {
38
40
48public:
51
57 inline void setPostProcessing(bool postProcess) { m_postProcess = postProcess; }
58
68 void setDensity(double density) {
69 if (density < 0.0) {
70 m_density = 0.0;
71 } else if (density > 1.0) {
72 m_density = 1.0;
73 } else {
74 m_density = density;
75 }
76 }
77
78protected:
80 void doCall() override;
81
86 void preProcess();
87
96
109
118
129
130private:
131 double m_density;
132
134
136
138};
139
140}
Declaration of ogdf::AdjacencyOracle class.
Declares ogdf::CliqueFinderModule class.
Tells you in constant time if two nodes are adjacent.
Finds cliques and dense subgraphs using a heuristic.
int evaluate(node v)
Evaluates v in m_pCopy heuristically concerning its qualification as a clique start node.
void setDensity(double density)
Sets the density needed for subgraphs to be detected.
void doCall() override
Find cliques in m_pCopy.
double m_density
Value in [0,1] defining how dense subgraphs need to be.
void findClique(node v, List< node > &neighbours)
Searches for a clique/dense subgraph around node v in list neighbours.
void postProcessCliques(List< List< node > * > &cliqueList)
If postprocessing is activated, use the result of the first phase and revisit cliques that are too sm...
bool m_postProcess
Whether postprocessing should be activated.
void preProcess()
Deletes all nodes from m_pCopy with degree < m_density * m_minDegree in O(n+m).
NodeArray< bool > m_usedNode
Whether the node is already assigned to a clique.
AdjacencyOracle * m_adjOracle
Adjacency oracle for m_pCopy.
void setPostProcessing(bool postProcess)
Sets whether postprocessing should be activated.
CliqueFinderHeuristic()
Creates a CliqueFinderHeuristic.
bool allAdjacent(node v, List< node > *vList) const
Checks whether v is adjacent to (at least m_density times) all nodes in vList.
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
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.