ClusterPlanarityModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/Module.h>
#include <ogdf/cluster/ClusterGraph.h>
 
namespace ogdf {
 
class OGDF_EXPORT ClusterPlanarityModule : public Module {
public:
    ClusterPlanarityModule() = default;
 
    virtual ~ClusterPlanarityModule() = default;
 
    virtual bool isClusterPlanar(const ClusterGraph& CG) {
        Graph Gcopy;
        ClusterGraph CGcopy(CG, Gcopy);
        return isClusterPlanarDestructive(CGcopy, Gcopy);
    };
 
 
    virtual bool isClusterPlanarDestructive(ClusterGraph& CG, Graph& G) = 0;
 
    virtual bool clusterPlanarEmbed(ClusterGraph& CG, Graph& G) {
        OGDF_ASSERT(&CG.constGraph() == &G);
        Graph Gcopy;
        ClusterArray<cluster> copyC(CG, nullptr);
        NodeArray<node> copyN(G, nullptr);
        EdgeArray<edge> copyE(G, nullptr);
        ClusterGraph CGcopy(CG, Gcopy, copyC, copyN, copyE);
 
        if (!clusterPlanarEmbedClusterPlanarGraph(CGcopy, Gcopy)) {
            return false;
        } else {
            EdgeArray<edge> origE(Gcopy, nullptr);
            invertRegisteredArray(copyE, origE);
            copyBackEmbedding(CG, G, CGcopy, Gcopy, copyC, copyN, copyE, origE);
            return true;
        }
    }
 
 
    virtual bool clusterPlanarEmbedClusterPlanarGraph(ClusterGraph& CG, Graph& G) {
        throw std::runtime_error(
                "Embedding is (currently) not implemented by this ClusterPlanarityModule!");
    }
 
protected:
    virtual void copyBackEmbedding(ClusterGraph& CG, Graph& G, const ClusterGraph& CGcopy,
            const Graph& Gcopy, const ClusterArray<cluster>& copyC, const NodeArray<node>& copyN,
            const EdgeArray<edge>& copyE, const EdgeArray<edge>& origE) const {
        CG.adjAvailable(true);
        copyEmbedding(Gcopy, G, [&origE](adjEntry adj) { return origE.mapEndpoint(adj); });
        for (cluster c : CG.clusters) {
            c->adjEntries.clear();
            for (adjEntry adj : copyC[c]->adjEntries) {
                c->adjEntries.pushBack(origE.mapEndpoint(adj));
            }
        }
    };
};
 
}