ext/OGDF/ogdf/graphalg/Clusterer.h

   1 /*
   2  * $Revision: 2564 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of Clusterer class that computes a clustering
  11  *        for a given graph based on the local neighborhood
  12  *        structure of each edge. Uses the criteria by
  13  *        Auber, Chiricota, Melancon for small-world graphs to
  14  *        compute clustering index and edge strength.
  15  *
  16  * \author Karsten Klein
  17  *
  18  * \par License:
  19  * This file is part of the Open Graph Drawing Framework (OGDF).
  20  *
  21  * \par
  22  * Copyright (C)<br>
  23  * See README.txt in the root directory of the OGDF installation for details.
  24  *
  25  * \par
  26  * This program is free software; you can redistribute it and/or
  27  * modify it under the terms of the GNU General Public License
  28  * Version 2 or 3 as published by the Free Software Foundation;
  29  * see the file LICENSE.txt included in the packaging of this file
  30  * for details.
  31  *
  32  * \par
  33  * This program is distributed in the hope that it will be useful,
  34  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  35  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  36  * GNU General Public License for more details.
  37  *
  38  * \par
  39  * You should have received a copy of the GNU General Public
  40  * License along with this program; if not, write to the Free
  41  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  42  * Boston, MA 02110-1301, USA.
  43  *
  44  * \see  http://www.gnu.org/copyleft/gpl.html
  45  ***************************************************************/
  46
  47
  48 #ifdef _MSC_VER
  49 #pragma once
  50 #endif
  51
  52 #ifndef OGDF_CLUSTERER_H
  53 #define OGDF_CLUSTERER_H
  54
  55 #include <ogdf/module/ClustererModule.h>
  56
  57 namespace ogdf {
  58
  59
  60         /**
  61          * Clustering is determined based on the threshold values (connectivity
  62          * thresholds determine edges to be deleted) and stopped if average
  63          * clustering index drops below m_stopIndex.
  64          *
  65          * \pre Input graph has to be connected
  66          */
  67         class OGDF_EXPORT Clusterer : public ClustererModule
  68         {
  69                 public:
  70                 //Constructor taking a graph G to be clustered
  71                 Clusterer(const Graph &G);
  72                 //Default constructor allowing to cluster multiple
  73                 //graphs with the same instance of the Clusterer
  74                 //Clusterer();
  75                 virtual ~Clusterer() {}
  76
  77                 //The clustering can be done recursively (use single threshold
  78                 //on component to delete weak edges (recompute strengths)) or
  79                 //by applying a set of thresholds, set the behaviour in
  80                 //function setRecursive
  81                 virtual void computeClustering(SList<SimpleCluster*> &sl);
  82                 //set the thresholds defining the hierarchy assignment decision
  83                 //should be dependent on the used metrics
  84                 void setClusteringThresholds(const List<double> &threshs);
  85                 //thresholds are computed from edge strengths to split off
  86                 //at least some edges as long as there is a difference between
  87                 //min and max strength (progressive clustering)
  88                 //set this value to 0 to use your own or the default values
  89                 void setAutomaticThresholds(int numValues)
  90                 {m_autoThreshNum = numValues;}
  91                 //for recursive clustering, only the first threshold is used
  92                 void setRecursive(bool b) {m_recursive = b;}
  93                 //preliminary
  94                 void computeEdgeStrengths(EdgeArray<double> & strength);
  95                 void computeEdgeStrengths(const Graph &G, EdgeArray<double> & strength);
  96
  97                 void createClusterGraph(ClusterGraph &C);
  98
  99                 void setStopIndex(double stop) {m_stopIndex = stop;}
 100
 101                 //compute a clustering index for node v
 102                 //number of connections in neighborhood compared to clique
 103                 virtual double computeCIndex(node v)
 104                 {
 105                         return computeCIndex(*m_pGraph, v);
 106                 }
 107                 virtual double computeCIndex(const Graph &G, node v)
 108                 {
 109                         OGDF_ASSERT(v->graphOf() == &G);
 110                         if (v->degree()<2) return 1.0;
 111                         int conns = 0; //connections, without v
 112                         NodeArray<bool> neighbor(G, false);
 113                         adjEntry adjE;
 114                         forall_adj(adjE, v)
 115                         {
 116                                 neighbor[adjE->twinNode()] = true;
 117                         }
 118                         forall_adj(adjE, v)
 119                         {
 120                                 adjEntry adjEE;
 121                                 forall_adj(adjEE, adjE->twinNode())
 122                                 {
 123                                         if (neighbor[adjEE->twinNode()])
 124                                                 conns++;
 125                                 }
 126                         }
 127                         //connections were counted twice
 128                         double index = conns / 2.0;
 129                         return index / (v->degree()*(v->degree()-1));
 130                 }
 131
 132                 protected:
 133                 EdgeArray<double> m_edgeValue; //strength value for edge clustering index
 134                 NodeArray<double> m_vertexValue; //clustering index for vertices
 135                 List<double> m_thresholds; //clustering level thresholds
 136                 List<double> m_autoThresholds; //automatically generated values (dep. on graph instance)
 137                 List<double> m_defaultThresholds; //some default values
 138                 double m_stopIndex; //average clustering index when recursive clustering stops
 139                                                         //between 0 and 1
 140                 bool m_recursive; //recursive clustering or list of tresholds
 141                 //bool m_autoThresholds; //compute thresholds according to edge strengths
 142                 int m_autoThreshNum; //number of thresholds to be computed
 143
 144         };//class Clusterer
 145
 146 } //end namespace ogdf
 147
 148 #endif