Clusterer.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/ClustererModule.h>
 
namespace ogdf {
class ClusterGraph;
template<class E>
class SList;
 
class OGDF_EXPORT Clusterer : public ClustererModule {
public:
    explicit Clusterer(const Graph& G);
 
    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) override;
 
    //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);
 
    virtual void createClusterGraph(ClusterGraph& C) override;
 
    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) override { return computeCIndex(*m_pGraph, v); }
 
    virtual double computeCIndex(const Graph& G, node v) override {
        OGDF_ASSERT(v->graphOf() == &G);
        if (v->degree() < 2) {
            return 1.0;
        }
        int conns = 0; //connections, without v
        NodeArray<bool> neighbor(G, false);
        for (adjEntry adjE : v->adjEntries) {
            neighbor[adjE->twinNode()] = true;
        }
        for (adjEntry adjE : v->adjEntries) {
            for (adjEntry adjEE : adjE->twinNode()->adjEntries) {
                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
#if 0
    bool m_autoThresholds; //compute thresholds according to edge strengths
#endif
    int m_autoThreshNum; //number of thresholds to be computed
};
 
}