ModifiedNibbleClusterer.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/geometry.h>
 
#include <vector>
 
namespace ogdf {
 
 
class ModifiedNibbleClusterer {
public:
    ModifiedNibbleClusterer()
        : m_clusterThreshold(3)
        , m_maxClusterSize(100)
        , maxClusterNum(100)
        , m_spreadProbability(0.8)
        , m_pG(nullptr)
        , m_pGC(nullptr)
        , m_sns(StartNodeStrategy::MaxDeg) { }
 
    ~ModifiedNibbleClusterer() {
#if 0
        delete m_pGC;
#endif
    }
 
    //TODO add a call with GraphAttributes and store in intweight
 
    long call(Graph& G, NodeArray<long>& clusterNum);
 
    long call(Graph& G, NodeArray<long>& clusterNum, NodeArray<long>& topLevelNum);
 
    // TODO long call(ClusterGraph &C, Graph & G) {}
    void setMaxClusterNum(int i) { maxClusterNum = i; }
 
    void setMaxClusterSize(long i) { m_maxClusterSize = i; }
 
    // Smaller clusters are joint with a neighbor (non-recursive) as a postprocessing
    void setClusterSizeThreshold(int threshold) {
        if (threshold > 0) {
            m_clusterThreshold = threshold;
        }
    }
 
    enum class StartNodeStrategy { MinDeg, MaxDeg, Random };
 
protected:
    void initialize(); //1< Initialize values for calculation before first step
    node selectStartNode(); 
    void modifiedNibble(node snode,
            std::vector<node>& bestCluster); 
    double findBestCluster(NodeArray<bool>& isActive, std::vector<node>& activeNodes,
            std::vector<node>& cluster);
    void spreadValues(NodeArray<bool>& isActive, std::vector<node>& activeNodes,
            NodeArray<double>& probUpdate);
 
    inline long maxClusterSize() { return m_maxClusterSize; }
 
    // Arithmetic plus Geometric Progression
    int aPGP(int i) {
        const int a = 2;
        const int d = 7;
        const double r = 1.5;
        return static_cast<int>(ceil(a * pot(r, i))) + i * d + a;
    }
 
    // TODO we expect i to be very small, but do this efficiently anyway
    double pot(double r, long i) { return pow(r, static_cast<double>(i)); }
 
    long activeNodeBound() {
        const int factor = 25; 
        //does not make sense to set it to 500 as they did, as we want less clusters.
        return factor * m_maxClusterSize;
    }
 
    void postProcess();
 
private:
    int m_steps;
    int m_clusterThreshold; // Below that size all remaining nodes are just packed in a cluster
    long m_maxClusterSize;
    long m_maxActiveNodes; // Bound on number of nodes in active set
    int maxClusterNum;
    double m_spreadProbability; //how much is spread, i.e. 1-val is the prob to stay at the node
    node m_startNode; // Node to start a walk from
    NodeArray<double> m_prob; // Probability of a node along the walk
    Graph* m_pG;
    GraphCopy* m_pGC;
    StartNodeStrategy m_sns;
 
    // Tests
    bool testSpreadSum() {
        double sum = 0.0;
        for (node v : m_pGC->nodes) {
            sum += m_prob[v];
        }
        return OGDF_GEOM_ET.equal(sum, 1.0);
    }
};
 
}