ClusterGraph.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/Observer.h>
#include <ogdf/basic/RegisteredArray.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/comparer.h>
#include <ogdf/basic/memory.h>
 
#include <functional>
#include <iosfwd>
#include <memory>
#include <utility>
 
namespace ogdf {
 
class OGDF_EXPORT ClusterElement; // IWYU pragma: keep
class OGDF_EXPORT ClusterGraph; // IWYU pragma: keep
class OGDF_EXPORT ClusterGraphObserver; // IWYU pragma: keep
 
using cluster = ClusterElement*; 
 
 
class OGDF_EXPORT ClusterElement : private internal::GraphElement {
    friend class ClusterGraph;
    friend class internal::GraphList<ClusterElement>;
 
    int m_id; 
    int m_depth; 
 
public:
 
    ListContainer<node, ClusterElement> nodes;
 
    ListContainer<cluster, ClusterElement> children;
 
 
    ListContainer<adjEntry, ClusterElement> adjEntries;
 
 
private:
    cluster m_parent; 
    cluster m_pPrev; 
    cluster m_pNext; 
    ListIterator<cluster> m_it; 
 
#ifdef OGDF_DEBUG
    // we store the graph containing this cluster for debugging purposes only
    const ClusterGraph* m_pClusterGraph;
#endif
 
 
    List<cluster>& getChildren() { return children; }
 
    List<node>& getNodes() { return nodes; }
 
    List<adjEntry>& getAdjEntries() { return adjEntries; }
 
 
    void getClusterInducedNodes(List<node>& clusterNodes);
 
    void getClusterInducedNodes(NodeArray<bool>& clusterNode, int& num);
 
public:
#ifdef OGDF_DEBUG
    ClusterElement(const ClusterGraph* pClusterGraph, int id)
        : m_id(id)
        , m_depth(0)
        , m_parent(nullptr)
        , m_pPrev(nullptr)
        , m_pNext(nullptr)
        , m_pClusterGraph(pClusterGraph) { }
#else
    explicit ClusterElement(int id)
        : m_id(id), m_depth(0), m_parent(nullptr), m_pPrev(nullptr), m_pNext(nullptr) { }
#endif
 
 
 
#ifdef OGDF_DEBUG
    const ClusterGraph* graphOf() const { return m_pClusterGraph; }
#endif
 
 
    int index() const { return m_id; }
 
    int depth() const { return m_depth; }
 
    cluster parent() { return m_parent; }
 
    cluster succ() const { return static_cast<cluster>(m_next); }
 
    cluster pred() const { return static_cast<cluster>(m_prev); }
 
    cluster pSucc() const { return m_pNext; }
 
    cluster pPred() const { return m_pPrev; }
 
 
    void getClusterNodes(List<node>& clusterNodes) {
        clusterNodes.clear();
        getClusterInducedNodes(clusterNodes);
    }
 
 
    int getClusterNodes(NodeArray<bool>& clusterNode) {
        int num = 0;
        getClusterInducedNodes(clusterNode, num);
        return num;
    }
 
 
    bool isDescendant(ClusterElement* child, bool allow_equal = false) {
        OGDF_ASSERT(child != nullptr);
        if (!allow_equal) {
            child = child->parent();
        }
        while (child != this) {
            if (child == nullptr) {
                return false;
            }
            child = child->parent();
        }
        return true;
    }
 
 
 
    ListConstIterator<ClusterElement*> cBegin() const { return children.begin(); }
 
    ListConstIterator<ClusterElement*> crBegin() const { return children.rbegin(); }
 
    int cCount() { return children.size(); }
 
    ListConstIterator<node> nBegin() const { return nodes.begin(); }
 
    int nCount() { return nodes.size(); }
 
    ListConstIterator<adjEntry> firstAdj() const { return adjEntries.begin(); }
 
    ListConstIterator<adjEntry> lastAdj() const { return adjEntries.rbegin(); }
 
 
    static int compare(const ClusterElement& x, const ClusterElement& y) { return x.m_id - y.m_id; }
    OGDF_AUGMENT_COMPARER(ClusterElement)
 
    OGDF_NEW_DELETE
};
 
 
#define forall_cluster_adj(adj, c)                                          \
    for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->firstAdj(); \
            ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var, (adj)); \
            ogdf_loop_var = ogdf_loop_var.succ())
 
#define forall_cluster_rev_adj(adj, c)                                      \
    for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->lastAdj();  \
            ogdf::test_forall_adj_entries_of_cluster(ogdf_loop_var, (adj)); \
            ogdf_loop_var = ogdf_loop_var.pred())
 
#define forall_cluster_adj_edges(e, c)                                      \
    for (ogdf::ListConstIterator<adjEntry> ogdf_loop_var = (c)->firstAdj(); \
            ogdf::test_forall_adj_edges_of_cluster(ogdf_loop_var, (e));     \
            ogdf_loop_var = ogdf_loop_var.succ())
 
inline bool test_forall_adj_entries_of_cluster(ListConstIterator<adjEntry>& it, adjEntry& adj) {
    if (it.valid()) {
        adj = (*it);
        return true;
    } else {
        return false;
    }
}
 
inline bool test_forall_adj_edges_of_cluster(ListConstIterator<adjEntry>& it, edge& e) {
    adjEntry adj = (*it);
    if (adj) {
        e = adj->theEdge();
        return true;
    } else {
        return false;
    }
}
 
inline bool test_forall_adj_edges_of_cluster(adjEntry& adj, edge& e) {
    if (adj) {
        e = adj->theEdge();
        return true;
    } else {
        return false;
    }
}
 
#define forall_clusters(c, C) for ((c) = (C).firstCluster(); (c); (c) = (c)->succ())
 
#define forall_postOrderClusters(c, C) \
    for ((c) = (C).firstPostOrderCluster(); (c); (c) = (c)->pSucc())
 
 
using ClusterGraphRegistry = RegistryBase<cluster, ClusterGraph, internal::GraphIterator<cluster>>;
 
template<typename Value, bool WithDefault>
class ClusterArrayBase; // IWYU pragma: keep
 
#define OGDF_DECL_REG_ARRAY_TYPE(v, c) ClusterArrayBase<v, c>
OGDF_DECL_REG_ARRAY(ClusterArray)
#undef OGDF_DECL_REG_ARRAY_TYPE
 
class OGDF_EXPORT ClusterGraphObserver : public Observer<ClusterGraph, ClusterGraphObserver> {
public:
    ClusterGraphObserver() = default;
 
    explicit ClusterGraphObserver(const ClusterGraph* CG) { reregister(CG); }
 
    virtual void clusterDeleted(cluster v) = 0;
    virtual void clusterAdded(cluster v) = 0;
    virtual void clustersCleared() = 0;
 
    const ClusterGraph* getGraph() const { return getObserved(); }
};
 
 
class OGDF_EXPORT ClusterGraph
    : public GraphObserver, // to get updates when graph nodes/edges added/removed
      public Observable<ClusterGraphObserver, ClusterGraph>, // to publish updates when clusters added/removed
      public ClusterGraphRegistry // for ClusterArrays
{
    int m_clusterIdCount = 0; 
 
    mutable cluster m_postOrderStart = nullptr; 
    cluster m_rootCluster = nullptr; 
 
    bool m_adjAvailable = false; 
    bool m_allowEmptyClusters =
            true; 
 
    NodeArray<cluster> m_nodeMap; 
    NodeArray<ListIterator<node>> m_itMap;
 
public:
 
    using cluster_iterator = internal::GraphIterator<cluster>;
 
 
 
    internal::GraphObjectContainer<ClusterElement> clusters;
 
 
 
 
    ClusterGraph();
 
 
    explicit ClusterGraph(const Graph& G);
 
 
    ClusterGraph(const ClusterGraph& C);
 
 
    ClusterGraph(const ClusterGraph& C, Graph& G);
 
 
    ClusterGraph(const ClusterGraph& C, Graph& G, ClusterArray<cluster>& originalClusterTable,
            NodeArray<node>& originalNodeTable);
 
 
    ClusterGraph(const ClusterGraph& C, Graph& G, ClusterArray<cluster>& originalClusterTable,
            NodeArray<node>& originalNodeTable, EdgeArray<edge>& edgeCopy);
 
    virtual ~ClusterGraph();
 
 
    cluster rootCluster() const { return m_rootCluster; }
 
    int numberOfClusters() const { return clusters.size(); }
 
    int maxClusterIndex() const { return m_clusterIdCount - 1; }
 
    inline cluster clusterOf(node v) const { return m_nodeMap[v]; }
 
    //should be called instead of direct c->depth call to assure
    //valid depth
    int& clusterDepth(cluster c) const {
        // updateDepth must be set to true if depth info shall be used
        OGDF_ASSERT(m_updateDepth);
 
        //initialize depth at first call
        if (!m_depthUpToDate) {
            computeSubTreeDepth(rootCluster());
        }
        OGDF_ASSERT(c->depth() != 0);
        return c->m_depth;
    }
 
    cluster firstCluster() const { return clusters.head(); }
 
    cluster lastCluster() const { return clusters.tail(); }
 
    cluster firstPostOrderCluster() const {
        if (!m_postOrderStart) {
            postOrder();
        }
        return m_postOrderStart;
    }
 
    template<class CLUSTERLIST>
    void allClusters(CLUSTERLIST& clusterList) const {
        clusterList.clear();
        for (cluster c : clusters) {
            clusterList.pushBack(c);
        }
    }
 
 
 
    void clear();
 
    void init(const Graph& G);
 
    void clearClusterTree(cluster C);
 
    cluster newCluster(cluster parent, int id = -1);
 
    cluster createEmptyCluster(const cluster parent = nullptr, int clusterId = -1);
 
 
    cluster createCluster(const SList<node>& nodes, const cluster parent = nullptr);
 
 
    void delCluster(cluster c);
 
    void moveCluster(cluster c, cluster newParent);
 
 
    void reassignNode(node v, cluster c);
 
    //inserted mainly for use in gmlparser.
    void reInit(Graph& G) { reinitGraph(G); }
 
    void copyClusterTree(
            const ClusterGraph& C, const Graph& G, ClusterArray<cluster>& originalClusterTable,
            std::function<node(node)> nodeMap = [](node v) { return v; });
 
    template<class NODELIST>
    void collapse(NODELIST& nodes, Graph& G) {
        OGDF_ASSERT(&G == &constGraph());
        m_adjAvailable = false;
 
        m_postOrderStart = nullptr;
        node v = nodes.popFrontRet();
        while (!nodes.empty()) {
            node w = nodes.popFrontRet();
            adjEntry adj = w->firstAdj();
            while (adj != nullptr) {
                adjEntry succ = adj->succ();
                edge e = adj->theEdge();
                if (e->source() == v || e->target() == v) {
                    G.delEdge(e);
                } else if (e->source() == w) {
                    G.moveSource(e, v);
                } else {
                    G.moveTarget(e, v);
                }
                adj = succ;
            }
            //because nodes can already be unassigned (they are always
            //unassigned if deleted), we have to check this
#if 0
            if (m_nodeMap[w])
            {
                cluster c = m_nodeMap[w];
                c->m_entries.del(m_itMap[w]);
            }
            removeNodeAssignment(w);
#endif
            G.delNode(w);
        }
    }
 
 
 
 
    cluster chooseCluster(
            std::function<bool(cluster)> includeCluster = [](cluster) { return true; },
            bool isFastTest = true) const;
 
    void setUpdateDepth(bool b) const {
        m_updateDepth = b;
        //make sure that depth cant be used anymore
        //(even if it may still be valid a little while)
        if (!b) {
            m_depthUpToDate = false;
        }
    }
 
    void pullUpSubTree(cluster c);
 
    //maybe later we should provide a permanent depth member update
    int treeDepth() const;
 
    void computeSubTreeDepth(cluster c) const;
 
    cluster commonCluster(SList<node>& nodes);
 
 
    cluster commonCluster(node v, node w) const {
        cluster c1, c2;
        return commonClusterLastAncestors(v, w, c1, c2);
    }
 
    cluster commonClusterLastAncestors(node v, node w, cluster& c1, cluster& c2) const {
        List<cluster> eL;
        return commonClusterAncestorsPath(v, w, c1, c2, eL);
    }
 
 
    cluster commonClusterPath(node v, node w, List<cluster>& eL) const {
        cluster c1, c2;
        return commonClusterAncestorsPath(v, w, c1, c2, eL);
    }
 
    cluster commonClusterAncestorsPath(node v, node w, cluster& c1, cluster& c2,
            List<cluster>& eL) const;
 
 
    void emptyClusters(SList<cluster>& emptyCluster, SList<cluster>* checkCluster = nullptr);
 
    inline bool emptyOnNodeDelete(cluster c) //virtual?
    {
#if 0
        if (!c) {
            return false; //Allows easy use in loops
        }
#endif
        return c->nCount() == 1 && c->cCount() == 0;
    }
 
    inline bool emptyOnClusterDelete(cluster c) //virtual?
    {
#if 0
        if (!c) {
            return false; //Allows easy use in loops
        }
#endif
        return c->nCount() == 0 && c->cCount() == 1;
    }
 
 
 
    template<class EDGELIST>
    void adjEdges(cluster c, EDGELIST& edges) const {
        edges.clear();
 
        if (m_adjAvailable) {
            edge e;
            forall_cluster_adj_edges(e, c) {
                edges.pushBack(e);
            }
        }
    }
 
    template<class ADJLIST>
    void adjEntries(cluster c, ADJLIST& entries) const {
        entries.clear();
        if (m_adjAvailable) {
            for (adjEntry adj : c->adjEntries) {
                entries.pushBack(adj);
            }
        }
    }
 
    template<class LISTITERATOR>
    void makeAdjEntries(cluster c, LISTITERATOR start) {
        c->adjEntries.clear();
        LISTITERATOR its;
        for (its = start; its.valid(); its++) {
            adjEntry adj = (*its);
            c->adjEntries.pushBack(adj);
        }
    }
 
    bool adjAvailable() const { return m_adjAvailable; }
 
    void adjAvailable(bool val) { m_adjAvailable = val; }
 
 
 
 
    bool representsCombEmbedding() const;
 
 
    bool representsConnectedCombEmbedding() const;
 
#ifdef OGDF_DEBUG
    void consistencyCheck() const;
#endif
 
 
 
    static inline int keyToIndex(cluster key) { return key->index(); }
 
    bool isKeyAssociated(cluster key) const {
        if (key == nullptr) {
            return false;
        }
#ifdef OGDF_DEBUG
        if (key->graphOf() == this) {
            OGDF_ASSERT(keyToIndex(key) < this->getArraySize());
            return true;
        } else {
            return false;
        }
#else
        return true;
#endif
    }
 
    int calculateArraySize(int add) const { return calculateTableSize(m_clusterIdCount + add); }
 
    int maxKeyIndex() const { return (m_clusterIdCount)-1; }
 
    cluster_iterator begin() const { return clusters.begin(); }
 
    cluster_iterator end() const { return clusters.end(); }
 
 
 
    operator const Graph&() const { return *getGraph(); }
 
    const Graph& constGraph() const { return *getGraph(); }
 
    ClusterGraph& operator=(const ClusterGraph& C);
 
 
protected:
    mutable std::unique_ptr<ClusterArray<int>> m_lcaSearch; 
    mutable int m_lcaNumber = 0; 
    mutable std::unique_ptr<ClusterArray<cluster>> m_vAncestor; 
    mutable std::unique_ptr<ClusterArray<cluster>> m_wAncestor; 
 
    mutable bool m_updateDepth = false; 
    mutable bool m_depthUpToDate = false; 
 
    cluster doCreateCluster(const SList<node>& nodes, const cluster parent, int clusterId = -1);
 
    cluster doCreateCluster(const SList<node>& nodes, SList<cluster>& emptyCluster,
            const cluster parent, int clusterId = -1);
 
    void doClear();
 
    void copyLCA(const ClusterGraph& C);
    //int m_treeDepth; //should be implemented and updated in operations?
 
    //we assume that c is inserted via pushback in newparent->children
    void updatePostOrder(cluster c, cluster oldParent, cluster newParent);
 
    cluster postOrderPredecessor(cluster c) const;
 
    cluster leftMostCluster(cluster c) const;
 
 
    void nodeDeleted(node v) override;
 
    void nodeAdded(node v) override { assignNode(v, rootCluster()); }
 
    void edgeDeleted(edge /* e */) override { }
 
    void edgeAdded(edge /* e */) override { }
 
    void cleared() override {
        //we don't want a complete clear, as the graph still exists
        //and can be updated from input stream
        clear();
    }
 
    void registrationChanged(const Graph* newG) override;
 
 
private:
    template<typename T>
    inline void fillEmptyClusters(SList<cluster>& emptyCluster, const T& clusterList) const {
        emptyCluster.clear();
 
        for (cluster cc : clusterList) {
            if (cc->cCount() + cc->nCount() == 0 && cc != rootCluster()) { // we dont add rootcluster
                emptyCluster.pushBack(cc);
            }
        }
    }
 
    void recurseClearClusterTreeOnChildren(cluster c, List<node>& attached) {
        m_adjAvailable = false;
        for (auto child : c->getChildren()) {
            clearClusterTree(child, attached);
        }
    }
 
    void assignNode(node v, cluster C);
 
    void unassignNode(node v);
 
    void removeNodeAssignment(node v) {
        if (m_nodeMap[v]) //iff == 0, itmap == 0 !!?
        {
            cluster c2 = m_nodeMap[v];
            c2->nodes.del(m_itMap[v]);
            m_nodeMap[v] = nullptr;
            m_itMap[v] = ListIterator<node>();
        }
    }
 
    void shallowCopy(const ClusterGraph& C);
 
    void deepCopy(const ClusterGraph& C, Graph& G);
 
    void deepCopy(const ClusterGraph& C, Graph& G, ClusterArray<cluster>& originalClusterTable,
            NodeArray<node>& originalNodeTable);
 
    void deepCopy(const ClusterGraph& C, Graph& G, ClusterArray<cluster>& originalClusterTable,
            NodeArray<node>& originalNodeTable, EdgeArray<edge>& edgeCopy);
 
 
    void clearClusterTree(cluster c, List<node>& attached);
 
    void initGraph(const Graph& G);
 
    void reinitGraph(const Graph& G);
 
    cluster newCluster(int id);
 
    cluster newCluster();
 
    void postOrder() const;
 
#ifdef OGDF_DEBUG
    void checkPostOrder() const;
#endif
 
    void postOrder(cluster c, SListPure<cluster>& S) const;
};
 
template<class Value, bool WithDefault>
class ClusterArrayBase : public RegisteredArray<ClusterGraph, Value, WithDefault> {
    using RA = RegisteredArray<ClusterGraph, Value, WithDefault>;
 
public:
    using RA::RA;
 
    ClusterArrayBase() = default;
 
    ClusterArrayBase(const ClusterGraph& C, const Value& def, int size) : RA(C, def) {
        RA::resize(size, true);
    };
 
    ClusterGraph* graphOf() const { return RA::registeredAt(); }
};
 
OGDF_EXPORT std::ostream& operator<<(std::ostream& os, cluster c);
 
 
OGDF_EXPORT void planarizeClusterBorderCrossings(const ClusterGraph& CG, Graph& G,
        EdgeArray<List<std::pair<adjEntry, cluster>>>* subdivisions,
        const std::function<edge(edge)>& translate);
 
}