CPlanarSubClusteredST.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/cluster/ClusterArray.h>
#include <ogdf/cluster/ClusterGraph.h>
 
namespace ogdf {
namespace cluster_planarity {
 
class CPlanarSubClusteredST {
public:
    CPlanarSubClusteredST() { }
 
    virtual void call(const ClusterGraph& CG, EdgeArray<bool>& inST);
    virtual void call(const ClusterGraph& CG, EdgeArray<bool>& inST, EdgeArray<double>& weight);
 
private:
    void dfsBuildOriginalST(/*ClusterGraph& CG,*/
            node v,
            ClusterArray<EdgeArray<bool>>& treeEdges, //edges in repgraph
            EdgeArray<bool>& inST, //original edges
            NodeArray<bool>& visited);
    //builds spanning tree on graph of node v in treeEdges
    void dfsBuildSpanningTree(node v, EdgeArray<bool>& treeEdges, NodeArray<bool>& visited);
 
    void constructRepresentationGraphNodes(const ClusterGraph& CG, Graph& g, cluster c) {
        // insert nodes for all child clusters
        ListConstIterator<cluster> it;
        for (auto child : c->children) {
            node v = g.newNode();
            m_cRepNode[child] = v;
        }
        // insert nodes for all node entries in c
        ListConstIterator<node> itn;
        for (auto u : c->nodes) {
            node v = g.newNode();
            m_vRepNode[u] = v;
        }
    }
 
    void constructRepresentationGraphEdges(const ClusterGraph& CG, ClusterArray<Graph*>& RepGraph) {
        for (edge e : CG.constGraph().edges) {
            //insert representation in RepGraph[allocation cluster]
            //defined by lowest common ancestor of end points
            node u = e->source();
            node v = e->target();
            cluster uAncestor, vAncestor;
            cluster allocCluster = CG.commonClusterLastAncestors(u, v, uAncestor, vAncestor);
            m_allocCluster[e] = allocCluster;
            //now derive the real ancestors (maybe the nodes themselves from
            //the supplied clusters
 
            //Case1: both nodes in same cluster => connect the nodes in the
            //cluster representation graph
            if (uAncestor == vAncestor) {
                m_repEdge[e] = RepGraph[uAncestor]->newEdge(m_vRepNode[u], m_vRepNode[v]);
            } else {
                OGDF_ASSERT(uAncestor != CG.rootCluster() || vAncestor != CG.rootCluster());
                //now only one node can be directly in rootcluster
                //this case now seems to fall together with else else...
                if (uAncestor == CG.rootCluster()) {
                    m_repEdge[e] = RepGraph[uAncestor]->newEdge(m_vRepNode[u], m_cRepNode[vAncestor]);
                } else if (vAncestor == CG.rootCluster()) {
                    m_repEdge[e] = RepGraph[vAncestor]->newEdge(m_cRepNode[uAncestor], m_vRepNode[v]);
                } else {
                    OGDF_ASSERT(allocCluster != nullptr);
                    //now create edge in lowest common cluster
                    node v1, v2;
                    v1 = ((uAncestor == nullptr) ? m_vRepNode[u] : m_cRepNode[uAncestor]);
                    v2 = ((vAncestor == nullptr) ? m_vRepNode[v] : m_cRepNode[vAncestor]);
                    m_repEdge[e] = RepGraph[allocCluster]->newEdge(v1, v2);
                }
            }
        }
    }
 
    void computeRepresentationGraphs(const ClusterGraph& CG, ClusterArray<Graph*>& RepGraph) {
        for (cluster c : CG.clusters) {
            RepGraph[c] = new Graph;
            constructRepresentationGraphNodes(CG, *RepGraph[c], c);
        }
        constructRepresentationGraphEdges(CG, RepGraph);
    }
 
    void deleteRepresentationGraphs(const ClusterGraph& CG, ClusterArray<Graph*>& RepGraph) {
        for (cluster c : CG.clusters) {
            delete RepGraph[c];
        }
    }
 
    void initialize(const ClusterGraph& CG);
 
#if 0
    EdgeArray<int> m_edgeStatus;
#endif
 
    EdgeArray<cluster> m_allocCluster;
    EdgeArray<edge> m_repEdge;
    ClusterArray<node> m_cRepNode;
    NodeArray<node> m_vRepNode;
#if 0
    int m_genDebug; //only for debugging
#endif
};
 
}
}