Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
CliqueFinderModule.h
Go to the documentation of this file.
1
32#pragma once
33
36#include <ogdf/basic/List.h>
37
38namespace ogdf {
39
41
47public:
54 explicit CliqueFinderModule() : m_pGraph(nullptr), m_pCopy(nullptr), m_minDegree(2) { }
55
56 virtual ~CliqueFinderModule() { }
57
59
67
69
75 void call(const Graph& G, List<List<node>*>& cliqueLists);
76
79
81 void setMinSize(int i) { m_minDegree = max(0, i - 1); }
82
86
94 static void cliqueListToNumber(const Graph& G, const List<List<node>*>& cliqueLists,
96
107
121
132 static bool cliqueOK(const Graph& G, List<node>* clique, double density = 1.0);
133
135
136private:
138
141 void beginCall(const Graph& G);
142
149
158
160 void endCall();
161
168
170
171protected:
173
175
177
182 virtual void doCall() = 0;
183
185};
186
187}
Declaration of class GraphAttributes which extends a Graph by additional attributes.
Declaration of graph copy classes.
Declaration of doubly linked lists and iterators.
virtual void doCall()=0
Find cliques in m_pCopy.
static void cliqueListToNumber(const Graph &G, const List< List< node > * > &cliqueLists, NodeArray< int > &cliqueNumber)
Uses a list of cliques to get the clique number of each node.
void endCall()
Frees memory after doCall().
CliqueFinderModule()
Creates a CliqueFinderModule.
static void cliqueNumberToList(const Graph &G, const NodeArray< int > &cliqueNumber, List< List< node > * > &cliqueLists)
Uses the clique number for each node to create a list of cliques.
void beginCall(const Graph &G)
Initializes member variables and calls doCall().
void setResults(List< List< node > * > &cliqueLists)
Sets the results of doCall() using m_copyCliqueNumber.
bool handleTrivialCases()
Checks whether finding cliques in m_pCopy is trivial, i.e.
void setResults(NodeArray< int > &cliqueNumber)
Sets the results of doCall() using m_copyCliqueNumber.
NodeArray< int > m_copyCliqueNumber
The clique number for each node in m_pCopy.
GraphCopy * m_pCopy
Copy of m_pGraph without self-loops and multi-edges.
void call(const Graph &G, List< List< node > * > &cliqueLists)
Searches for cliques and returns the list of cliques.
void call(const Graph &G, NodeArray< int > &cliqueNumber)
Searches for cliques and sets the clique index number for each node.
static bool cliqueOK(const Graph &G, List< node > *clique, double density=1.0)
Checks whether density times the number of possible edges exist between clique members.
const Graph * m_pGraph
The original Graph in which cliques are searched.
static void cliqueGraphAttributes(const Graph &G, const NodeArray< int > &cliqueNumber, GraphAttributes &GA)
Labels and colors nodes in the given GraphAttributes according to their clique number.
void setMinSize(int i)
Sets the minimum size of a clique.
int m_minDegree
Minimum degree of the nodes in a found clique.
Stores additional attributes of a graph (like layout information).
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
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
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_MALLOC_NEW_DELETE
Makes the class use malloc for memory allocation.
Definition memory.h:91
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.