|
|||
|
|
|
|||
|
|
Finds cliques and dense subgraphs using a heuristic. More...
#include <ogdf/clique/CliqueFinderHeuristic.h>
Inheritance diagram for ogdf::CliqueFinderHeuristic:Public Member Functions | |
| CliqueFinderHeuristic () | |
| Creates a CliqueFinderHeuristic. | |
| void | setDensity (double density) |
| Sets the density needed for subgraphs to be detected. | |
| void | setPostProcessing (bool postProcess) |
| Sets whether postprocessing should be activated. | |
| Public Member Functions inherited from ogdf::CliqueFinderModule | |
| CliqueFinderModule () | |
| Creates a CliqueFinderModule. | |
| virtual | ~CliqueFinderModule () |
| 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. | |
| void | setMinSize (int i) |
| Sets the minimum size of a clique. | |
Protected Member Functions | |
| bool | allAdjacent (node v, List< node > *vList) const |
Checks whether v is adjacent to (at least m_density times) all nodes in vList. | |
| void | doCall () override |
| Find cliques in m_pCopy. | |
| int | evaluate (node v) |
Evaluates v in m_pCopy heuristically concerning its qualification as a clique start node. | |
| 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 small. | |
| void | preProcess () |
| Deletes all nodes from m_pCopy with degree < m_density * m_minDegree in O(n+m). | |
Private Attributes | |
| AdjacencyOracle * | m_adjOracle |
| Adjacency oracle for m_pCopy. | |
| double | m_density |
| Value in [0,1] defining how dense subgraphs need to be. | |
| bool | m_postProcess |
| Whether postprocessing should be activated. | |
| NodeArray< bool > | m_usedNode |
| Whether the node is already assigned to a clique. | |
Additional Inherited Members | |
| Static Public Member Functions inherited from ogdf::CliqueFinderModule | |
| 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. | |
| 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. | |
| 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. | |
| 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. | |
| Protected Attributes inherited from ogdf::CliqueFinderModule | |
| NodeArray< int > | m_copyCliqueNumber |
| The clique number for each node in m_pCopy. | |
| int | m_minDegree |
| Minimum degree of the nodes in a found clique. | |
| GraphCopy * | m_pCopy |
| Copy of m_pGraph without self-loops and multi-edges. | |
Finds cliques and dense subgraphs using a heuristic.
The class CliqueFinderHeuristic can be called on a graph to retrieve (disjoint) cliques or dense subgraphs respectively by using a greedy heuristic.
Definition at line 47 of file CliqueFinderHeuristic.h.
|
explicit |
Creates a CliqueFinderHeuristic.
|
overrideprotectedvirtual |
Find cliques in m_pCopy.
The found cliques are noted in m_copyCliqueNumber. Clique nodes get a number >= 0, all other nodes -1.
Implements ogdf::CliqueFinderModule.
Evaluates v in m_pCopy heuristically concerning its qualification as a clique start node.
The higher this value, the better the node as a clique start node.
v. Searches for a clique/dense subgraph around node v in list neighbours.
neighbours + v will form a clique/dense subgraph afterwards.
| v | The node around which to search for a clique/dense subgraph. |
| neighbours | The nodes which potentially form a clique together with v. Is assigned a list of nodes that actually forms a clique/dense subgraph together with v. |
|
protected |
If postprocessing is activated, use the result of the first phase and revisit cliques that are too small.
These cliques are rearranged to potentially find new, bigger cliques.
| cliqueList | The cliques to postprocess. |
|
protected |
Deletes all nodes from m_pCopy with degree < m_density * m_minDegree in O(n+m).
Sets the density needed for subgraphs to be detected.
For a subgraph of size k to recognized as dense, it has to contain at least (density * (k*(k-1))/2) edges. This setting does not have an effect for graphs with less than 3 nodes.
| density | value in [0.0 ... 1.0] |
Definition at line 68 of file CliqueFinderHeuristic.h.
Sets whether postprocessing should be activated.
| postProcess | Whether postprocessing should be activated. |
Definition at line 57 of file CliqueFinderHeuristic.h.
|
private |
Adjacency oracle for m_pCopy.
Definition at line 135 of file CliqueFinderHeuristic.h.
|
private |
Value in [0,1] defining how dense subgraphs need to be.
Definition at line 131 of file CliqueFinderHeuristic.h.
|
private |
Whether postprocessing should be activated.
Definition at line 133 of file CliqueFinderHeuristic.h.
Whether the node is already assigned to a clique.
Definition at line 137 of file CliqueFinderHeuristic.h.