ext/OGDF/ogdf/graphalg/CliqueFinder.h

   1 /*
   2  * $Revision: 2584 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-12 02:38:07 +0200 (Do, 12. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declares CliqueFinder class.
  11  * CliqueFinder searches for complete (dense) subgraphs.
  12  *
  13  * \author Karsten Klein
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_CLIQUEFINDER_H
  49 #define OGDF_CLIQUEFINDER_H
  50
  51
  52 #include <ogdf/basic/NodeArray.h>
  53 #include <ogdf/basic/EdgeArray.h>
  54 #include <ogdf/basic/List.h>
  55 #include <ogdf/basic/GraphCopy.h>
  56
  57 namespace ogdf{
  58
  59
  60 //! Finds cliques and dense subgraphs.
  61 /**
  62  * The class CliqueFinder can be called on a graph
  63  * to retrieve (disjoint) cliques or dense subgraphs
  64  * respectively. Uses SPQR trees to find 3-connected
  65  * components.
  66  *
  67  * In the following, clique always stands for a subgraph
  68  * with properties that can be defined by the user to change
  69  * the standard definition of a complete subgraph, e.g. a
  70  * minimum size/degree etc.
  71  * We search for cliques in graph G by first dividing G into
  72  * its triconnnected components and then using a greedy
  73  * heuristics within each component
  74  */
  75 class OGDF_EXPORT CliqueFinder {
  76
  77 public:
  78         //constructor
  79         CliqueFinder(const Graph &G);
  80         ~CliqueFinder();
  81
  82         //Calls
  83         //We first make G biconnected, this keeps the triconnected
  84         //components. then the triconnected components are computed
  85         //within these components, we search for cliques
  86
  87         //!Searches for cliques and returns the clique index number for each node
  88         /**
  89          * Each clique will be assigned a different number, each node gets the
  90          * number of the clique it is contained in, -1 if not a clique member
  91          */
  92         void call(NodeArray<int> &cliqueNumber);
  93         //!Searches for cliques and returns the list of cliques
  94         /**
  95          * Each clique on return is represented by a list of member nodes
  96          * in the list of cliques cliqueLists
  97          */
  98         void call(List< List<node> > &cliqueLists);
  99
 100         //! the minimum degree of the nodes within the clique/subgraph
 101         void setMinSize(int i) { m_minDegree = max(2, i-1);}
 102         enum postProcess {ppNone, ppSimple};
 103
 104         //! Sets the abstract measure of density needed for subgraphs to be detected.
 105         /**
 106          * Does not have an effect for graphs with less than 4 nodes.
 107          */
 108         void setDensity(int density)
 109         {
 110                 if (density < 0) m_density = 0;
 111                 else if (density > 100) m_density = 100;
 112                 else m_density = density;
 113         }
 114
 115 protected:
 116         /**
 117          * doing the real work, find subgraphs in graph G, skip
 118          * all nodes with degree < minDegree
 119          * value 2: all triangles are cliques
 120          */
 121         void doCall(int minDegree = 2);
 122
 123         //------------------------------------------------------
 124         //sets the results of doCall depending on call signature
 125
 126         //clique nodes get numbers from >=0, all other nodes -1
 127         void setResults(NodeArray<int> &cliqueNumber);
 128         void setResults(List< List<node> > &cliqueLists);
 129         void setResults(List< List<node>* > &cliqueLists);
 130
 131         //work on the result of the first phase (heuristic), e.g.
 132         //by dropping, splitting or joining some of the found subgraphs
 133         void postProcessCliques(List< List<node>* > &cliqueList,
 134                 EdgeArray<bool> &usableEdge);
 135
 136         //check if node v is adjacent to all nodes in node list
 137         bool allAdjacent(node v, List<node>* vList);
 138         void writeGraph(Graph &G, NodeArray<int> &cliqueNumber,
 139                 const String &fileName);
 140
 141         //does a heuristic evaluation of node v (in m_pCopy)
 142         //concerning its qualification as a cluster start node
 143         //the higher the return value, the better the node
 144         //uses only edges with usableEdge == true
 145         int evaluate(node v, EdgeArray<bool> &usableEdge);
 146         void checkCliques(List< List<node>* > &cliqueList, bool sizeCheck = true);
 147         bool cliqueOK(List<node> *clique);
 148         void findClique(node v, List<node> &neighbours,
 149                                                 int numRandom = 0);
 150
 151 private:
 152         const Graph* m_pGraph;
 153         GraphCopy* m_pCopy;
 154         NodeArray<int> m_copyCliqueNumber;
 155         NodeArray<bool> m_usedNode; //node is assigned to clique
 156         //List< List<node>* > m_cliqueList;
 157         int m_minDegree;
 158         int m_numberOfCliques; //stores the number of found cliques
 159         postProcess m_postProcess;
 160         bool m_callByList; //stores information on type of call for result setting
 161         List< List<node> > *m_pList; //stores pointer on list given as call parameter
 162
 163         int m_density;  //an abstract value from 0..100 definin how dense the
 164                                         //subgraphs need to be, is not directly related to any
 165                                         //measure (degree, ...) but translated into a constraint
 166                                         //based on the heuristical search of the subgraphs
 167 };//CliqueFinder
 168
 169 }//end namespace ogdf
 170
 171 #endif