Clusterer.h

Go to the documentation of this file.

/*
 * $Revision: 2027 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2010-09-01 11:55:17 +0200 (Wed, 01 Sep 2010) $ 
 ***************************************************************/

#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_CLUSTERER_H
#define OGDF_CLUSTERER_H

#include <ogdf/module/ClustererModule.h>

namespace ogdf {
    
    
    class OGDF_EXPORT Clusterer : public ClustererModule
    {
        public: 
        //Constructor taking a graph G to be clustered 
        Clusterer(const Graph &G);
        //Default constructor allowing to cluster multiple
        //graphs with the same instance of the Clusterer  
        //Clusterer();
        virtual ~Clusterer() {}
        
        //The clustering can be done recursively (use single threshold
        //on component to delete weak edges (recompute strengths)) or 
        //by applying a set of thresholds, set the behaviour in 
        //function setRecursive
        virtual void computeClustering(SList<SimpleCluster*> &sl);
        //set the thresholds defining the hierarchy assignment decision
        //should be dependent on the used metrics
        void setClusteringThresholds(const List<double> &threshs);
        //thresholds are computed from edge strengths to split off
        //at least some edges as long as there is a difference between 
        //min and max strength (progressive clustering)
        //set this value to 0 to use your own or the default values
        void setAutomaticThresholds(int numValues)
        {m_autoThreshNum = numValues;}
        //for recursive clustering, only the first threshold is used
        void setRecursive(bool b) {m_recursive = b;}
        //preliminary 
        void computeEdgeStrengths(EdgeArray<double> & strength);
        void computeEdgeStrengths(const Graph &G, EdgeArray<double> & strength);
        
        void createClusterGraph(ClusterGraph &C);
        
        void setStopIndex(double stop) {m_stopIndex = stop;} 
        
        //compute a clustering index for node v
        //number of connections in neighborhood compared to clique
        virtual double computeCIndex(node v)
        {
            return computeCIndex(*m_pGraph, v);
        }
        virtual double computeCIndex(const Graph &G, node v) 
        {
            OGDF_ASSERT(v->graphOf() == &G);
            if (v->degree()<2) return 1.0;
            int conns = 0; //connections, without v
            NodeArray<bool> neighbor(G, false);
            adjEntry adjE;
            forall_adj(adjE, v)
            {
                neighbor[adjE->twinNode()] = true;
            }
            forall_adj(adjE, v)
            {
                adjEntry adjEE;
                forall_adj(adjEE, adjE->twinNode())
                {
                    if (neighbor[adjEE->twinNode()])
                        conns++;
                }
            }
            //connections were counted twice
            double index = conns / 2.0;
            return index / (v->degree()*(v->degree()-1));
        }
        
        protected:
        EdgeArray<double> m_edgeValue; //strength value for edge clustering index
        NodeArray<double> m_vertexValue; //clustering index for vertices
        List<double> m_thresholds; //clustering level thresholds
        List<double> m_autoThresholds; //automatically generated values (dep. on graph instance)
        List<double> m_defaultThresholds; //some default values
        double m_stopIndex; //average clustering index when recursive clustering stops
                            //between 0 and 1
        bool m_recursive; //recursive clustering or list of tresholds
        //bool m_autoThresholds; //compute thresholds according to edge strengths
        int m_autoThreshNum; //number of thresholds to be computed 
    
    };//class Clusterer
    
} //end namespace ogdf

#endif