ClusterPlanRep.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_CLUSTER_PLAN_REP_H
#define OGDF_CLUSTER_PLAN_REP_H



#include <ogdf/planarity/PlanRepUML.h>
#include <ogdf/cluster/ClusterGraphAttributes.h>
#include <ogdf/cluster/ClusterGraph.h>
#include <ogdf/cluster/ClusterArray.h>

#include <ogdf/basic/HashArray.h>


namespace ogdf {


class OGDF_EXPORT ClusterPlanRep : public PlanRep
{

public:

    ClusterPlanRep(const ClusterGraphAttributes &acGraph, 
                   const ClusterGraph &clusterGraph);

    virtual ~ClusterPlanRep() {}

    void initCC(int i);

    //edge on the cluster boundary, adjSource
    void setClusterBoundary(edge e) {
        setEdgeTypeOf(e, edgeTypeOf(e) | clusterPattern());
    }
    bool isClusterBoundary(edge e) {
        return ((edgeTypeOf(e) & clusterPattern()) == clusterPattern());
    }
    const ClusterGraph &getClusterGraph() const {
        return *m_pClusterGraph;
    }
    void insertEdgePathEmbedded(edge eOrig,
                                CombinatorialEmbedding &E,
                                const SList<adjEntry> &crossedEdges);

    void ModelBoundaries();

    //rootadj is set by ModelBoundaries
    adjEntry externalAdj() {return m_rootAdj;};


    //*************************************************************************
    //structural alterations

    // Expands nodes with degree > 4 and merge nodes for generalizations
    virtual void expand(bool lowDegreeExpand = false);

    virtual void expandLowDegreeVertices(OrthoRep &OR);

    //splits edge e, updates clustercage lists if necessary and returns new edge
    virtual edge split(edge e)
    {
        edge eNew = PlanRep::split(e);

        //update edge to cluster info
        m_edgeClusterID[eNew] = m_edgeClusterID[e];
        m_nodeClusterID[eNew->source()] = m_edgeClusterID[e];

        return eNew;
    }//split


    //returns cluster of edge e
    //edges only have unique numbers if clusters are already modelled
    //we derive the edge cluster from the endnode cluster information
    cluster clusterOfEdge(edge e) 
    {

        OGDF_ASSERT(m_clusterOfIndex.isDefined(ClusterID(e->source())))
        OGDF_ASSERT(m_clusterOfIndex.isDefined(ClusterID(e->target())))

        OGDF_ASSERT( (ClusterID(e->source()) == ClusterID(e->target())) ||
                      (clusterOfIndex(ClusterID(e->source())) ==
                       clusterOfIndex(ClusterID(e->target()))->parent()) ||
                       (clusterOfIndex(ClusterID(e->target())) ==
                       clusterOfIndex(ClusterID(e->source()))->parent()) ||
                       (clusterOfIndex(ClusterID(e->target()))->parent() ==
                       clusterOfIndex(ClusterID(e->source()))->parent())
                       )

        if (ClusterID(e->source()) == ClusterID(e->target()))
            return clusterOfIndex(ClusterID(e->target()));
        if (clusterOfIndex(ClusterID(e->source())) ==
            clusterOfIndex(ClusterID(e->target()))->parent())
            return clusterOfIndex(ClusterID(e->source()));
        if (clusterOfIndex(ClusterID(e->target())) ==
            clusterOfIndex(ClusterID(e->source()))->parent())
            return clusterOfIndex(ClusterID(e->target()));
        if (clusterOfIndex(ClusterID(e->target()))->parent() ==
            clusterOfIndex(ClusterID(e->source()))->parent())
            return clusterOfIndex(ClusterID(e->source()))->parent();

        OGDF_THROW(AlgorithmFailureException);
        //return 0;
    }//clusterOfEdge

    inline int ClusterID(node v) const {return m_nodeClusterID[v];}
    inline int ClusterID(edge e) const {return m_edgeClusterID[e];}
    cluster clusterOfIndex(int i) {return m_clusterOfIndex[i];}

    inline cluster clusterOfDummy(node v) 
        {
            OGDF_ASSERT(!original(v))
            OGDF_ASSERT(ClusterID(v) != -1)
            return clusterOfIndex(ClusterID(v));
        }

    //output functions
    void writeGML(const char *fileName, const Layout &drawing);
    void writeGML(const char *fileName);
    void writeGML(ostream &os, const Layout &drawing);


protected:

    //insert boundaries for all given clusters
    void convertClusterGraph(cluster act, 
                             AdjEntryArray<edge>& currentEdge,
                             AdjEntryArray<int>& outEdge);

    //insert edges to represent the cluster boundary
    void insertBoundary(cluster C, 
                        AdjEntryArray<edge>& currentEdge,
                        AdjEntryArray<int>& outEdge,
                        bool clusterIsLeaf);

    //reinsert edges to planarize the graph after convertClusterGraph
    void reinsertEdge(edge e);

private:

    const ClusterGraph *m_pClusterGraph;

    edgeType clusterPattern()        {return etcSecCluster << etoSecondary;}

    adjEntry m_rootAdj; //connects cluster on highest level with non cluster or 
                     //same level


    //******************
    EdgeArray<int> m_edgeClusterID;
    NodeArray<int> m_nodeClusterID;
    //we maintain an array of index to cluster mappings (CG is const)
    //cluster numbers don't need to be consecutive
    HashArray<int, cluster> m_clusterOfIndex;
};


}//namespace

#endif