ClusterAnalysis.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/HashArray.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/cluster/ClusterGraph.h>
 
#include <algorithm>
 
namespace ogdf {
template<class X>
class Skiplist;
 
/***
 * @ingroup ga-cplanarity
 *
 * Although most parts of the code are written with efficiency in mind,
 * this class is meant to be used in a static one-time analysis way,
 * not for dynamic checks over and over again.
 */
class ClusterAnalysis {
public:
    static const int IsNotActiveBound;
    static const int DefaultIndex; // Vertex index for independent bags, used to detect processing status.
 
    explicit ClusterAnalysis(const ClusterGraph& C, bool indyBags = false);
    ClusterAnalysis(const ClusterGraph& C, bool oalists, bool indyBags);
    ~ClusterAnalysis();
 
    // Quantitative
    // @param c is the cluster for which the active vertices are counted
    int outerActive(cluster c) const;
 
    // @param c is the cluster for which the active vertices are counted
    int innerActive(cluster c) const;
 
    int minIOALevel(node v) const { return min(minIALevel(v), minOALevel(v)); }
 
    int minIALevel(node v) const { return m_ialevel[v]; }
 
    int minOALevel(node v) const { return m_oalevel[v]; }
 
    // Qualitative
 
    bool isOuterActive(node v, cluster c) const;
    bool isInnerActive(node v, cluster c) const;
 
    List<edge>& lcaEdges(cluster c);
 
    List<node>& oaNodes(cluster c);
 
    int bagIndex(node v, cluster c);
 
    int numberOfBags(cluster c) const;
 
#if 0
    //TODO
    void reInit(const ClusterGraph &C);
#endif
 
    int indyBagIndex(node v);
 
    int numberOfIndyBags() { return m_numIndyBags; }
 
    cluster indyBagRoot(int i);
 
protected:
    void computeBags();
 
    void computeIndyBags();
 
private:
    void partitionCluster(ListConstIterator<node>& nodeIt, cluster c,
            HashArray<int, List<node>>& bagNodes, HashArray<int, bool>& indyBag,
            Skiplist<int*>& indexNumbers, Array<cluster>& bagRoots);
    void init(); 
    void cleanUp(); 
    const ClusterGraph* m_C;
    // we keep data structures to save inner/outer activity status
    // instead of computing them on the fly when needed
    // keep number of activity defining adjacent edges
    NodeArray<ClusterArray<int>*> m_iactive;
    NodeArray<ClusterArray<int>*> m_oactive;
 
    NodeArray<ClusterArray<int>*> m_bagindex;
 
    NodeArray<int> m_ialevel;
    NodeArray<int> m_oalevel;
 
    ClusterArray<int>* m_oanum; 
    ClusterArray<int>* m_ianum; 
    ClusterArray<int>* m_bags; 
 
    ClusterArray<List<node>>* m_oalists;
    const bool m_storeoalists; 
 
    ClusterArray<List<edge>>* m_lcaEdges; 
 
    const bool m_indyBags;
    NodeArray<int> m_indyBagNumber; 
    int m_numIndyBags; //<! Number of independent bags in clustergraph
    cluster* m_indyBagRoots; //<! Root clusters of independent bags (only when computed).
};
}