PlanRep.h

Go to the documentation of this file.

/*
 * $Revision: 2027 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2010-09-01 11:55:17 +0200 (Wed, 01 Sep 2010) $ 
 ***************************************************************/
 
//PlanRep should not know about generalizations and association,
//but we already set types in Attributedgraph, therefore set them 
//in PlanRep, too

#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_PLANREP_H
#define OGDF_PLANREP_H


#include <ogdf/basic/GraphCopy.h>
#include <ogdf/planarity/EdgeTypePatterns.h>
#include <ogdf/planarity/NodeTypePatterns.h>
#include <ogdf/basic/Layout.h>
#include <ogdf/orthogonal/OrthoRep.h>
#include <ogdf/basic/GraphAttributes.h>


namespace ogdf {


class OGDF_EXPORT PlanRep : public GraphCopy
{
public:
    struct Deg1RestoreInfo
    {
        Deg1RestoreInfo() : m_eOriginal(0), m_deg1Original(0), m_adjRef(0) { }
        Deg1RestoreInfo(edge eOrig, node deg1Orig, adjEntry adjRef)
            : m_eOriginal(eOrig), m_deg1Original(deg1Orig), m_adjRef(adjRef) { }

        edge m_eOriginal;    
        node m_deg1Original; 
        adjEntry m_adjRef;   
    };


    /* @{
     * \brief Creates a planarized representation of graph \a G.
     */
    PlanRep(const Graph& G);

    PlanRep(const GraphAttributes& AG);

    virtual ~PlanRep() {}




    int numberOfCCs() const {
        return m_nodesInCC.size();
    }

    int currentCC() const {
        return m_currentCC;
    }

    const List<node> &nodesInCC(int i) const {
        return m_nodesInCC[i];
    }

    const List<node> &nodesInCC() const {
        return m_nodesInCC[m_currentCC];
    }

    void initCC(int i);




    adjEntry expandAdj(node v) const {
        return m_expandAdj[v];
    }

    adjEntry& expandAdj(node v) {
        return m_expandAdj[v];
    }



    adjEntry boundaryAdj(node v) const {
        return m_boundaryAdj[v];
    }

    adjEntry& boundaryAdj(node v){
        return m_boundaryAdj[v];
    }

    //edge on the clique boundary, adjSource
    void setCliqueBoundary(edge e) {
        setEdgeTypeOf(e, edgeTypeOf(e) | cliquePattern());
    }
    bool isCliqueBoundary(edge e) {
        return ((edgeTypeOf(e) & cliquePattern()) == cliquePattern());
    }




    Graph::NodeType typeOf(node v) const {
        return m_vType[v];
    }

   Graph::NodeType& typeOf(node v) {
        return m_vType[v];
    }

    inline bool isVertex(node v)
    {
        return ( (typeOf(v) == Graph::vertex) ||
            (typeOf(v) == Graph::associationClass));
    }

    nodeType nodeTypeOf(node v)
    {
        return m_nodeTypes[v];
    }

    void setCrossingType(node v)
    {
        m_nodeTypes[v] |= ntTerCrossing << ntoTertiary;
    }

    bool isCrossingType(node v)
    {
        return (m_nodeTypes[v] &= (ntTerCrossing << ntoTertiary)) != 0;
    }



    EdgeType typeOf(edge e) const {
        return m_eType[e];
    }

    EdgeType& typeOf(edge e) {
        return m_eType[e];
    }

    edgeType& oriEdgeTypes(edge e)
    {
        return m_oriEdgeTypes[e];
    }

    edgeType edgeTypeOf(edge e) 
    {
        return m_edgeTypes[e];
    }

    edgeType& edgeTypes(edge e)
    {
        return m_edgeTypes[e];
    }

    void setEdgeTypeOf(edge e, edgeType et) 
    {
        m_edgeTypes[e] = et;
    }

    void setType(edge e, EdgeType et)
    {
        m_eType[e] = et;
        switch (et)
        {
            case Graph::association: m_edgeTypes[e] = etcPrimAssociation;break;
            case Graph::generalization: m_edgeTypes[e] = etcPrimGeneralization; 
                break;
            case Graph::dependency: m_edgeTypes[e] = etcPrimDependency; break;
            default: break;
        }
    }

    //-------------------------------------------------------------------------
    //new edge types
    //to set or check edge types use the pattern function in the private section

    //-------------------
    //primary level types

    bool isGeneralization(edge e) {
        bool check = (((m_edgeTypes[e] & etpPrimary) & etcPrimGeneralization) == etcPrimGeneralization);
        return check;
    }

    void setGeneralization(edge e) {
        setPrimaryType(e, etcPrimGeneralization);

        //preliminary set old array too
        m_eType[e] = generalization; //can be removed if edgetypes work properly
    }

    bool isDependency(edge e) {
        bool check = (((m_edgeTypes[e] & etpPrimary) & etcPrimDependency) == etcPrimDependency);
        return check;
    }

    void setDependency(edge e) {
        setPrimaryType(e, etcPrimDependency);

        //preliminary set old array too
        m_eType[e] = dependency; //can be removed if edgetypes work properly
    }

    void setAssociation(edge e) {
        setPrimaryType(e, etcPrimAssociation);

        //preliminary set old array too
        m_eType[e] = association; //can be removed if edgetypes work properly
    }

    //------------------
    //second level types

    //in contrast to setsecondarytype: do not delete old value

    void setExpansion(edge e) {
        m_edgeTypes[e] |= expansionPattern();

        //preliminary set old array too
        m_expansionEdge[e] = 1;//can be removed if edgetypes work properly
    }

    bool isExpansion(edge e) {
        return ((m_edgeTypes[e] & expansionPattern()) == expansionPattern());
    }

    //should add things like cluster and clique boundaries that need rectangle shape

    bool isBoundary(edge e) {
        return isCliqueBoundary(e); }

    //--------------
    //tertiary types

    void setAssClass(edge e)
    {
        m_edgeTypes[e] |= assClassPattern();
    }

    bool isAssClass(edge e)
    {
        return ((m_edgeTypes[e] & assClassPattern()) == assClassPattern());
    }


    //------------------
    //fourth level types

    void setBrother(edge e) {
        m_edgeTypes[e] |= brotherPattern();
    }

    void setHalfBrother(edge e) {
        m_edgeTypes[e] |= halfBrotherPattern();
    }

    bool isBrother(edge e) {
        return ( (((m_edgeTypes[e] & etpFourth) & brotherPattern())>> etoFourth) == etcBrother);
    }

    bool isHalfBrother(edge e) {
        return ( (((m_edgeTypes[e] & etpFourth) & halfBrotherPattern())>> etoFourth) == etcHalfBrother);
    }

    //-----------------
    //set generic types

    edgeType edgeTypeAND(edge e, edgeType et) {m_edgeTypes[e] &= et; return m_edgeTypes[e];}

    edgeType edgeTypeOR(edge e, edgeType et) {m_edgeTypes[e] |= et; return m_edgeTypes[e];}

    //set primary edge type of edge e to primary edge type in et
    //deletes old primary value
    void setPrimaryType(edge e, edgeType et) {m_edgeTypes[e] &= 0xfffffff0; 
                                              m_edgeTypes[e] |= (etpPrimary & et); } 

    void setSecondaryType(edge e, edgeType et) {m_edgeTypes[e] &= 0xffffff0f; 
                                                m_edgeTypes[e] |= (etpSecondary & ( et << etoSecondary)); }

    //sets primary type to bitwise AND of et's primary value and old value
    edgeType edgeTypePrimaryAND(edge e, edgeType et) {m_edgeTypes[e] &= (etpAll & et); return m_edgeTypes[e];}    

    //sets primary type to bitwise OR of et's primary value and old value
    edgeType edgeTypePrimaryOR(edge e, edgeType et) {m_edgeTypes[e] |= et; return m_edgeTypes[e];}

    //set user defined type locally
    void setUserType(edge e, edgeType et)
    {   
        OGDF_ASSERT( et < 147);
        m_edgeTypes[e] |= (et << etoUser);
    }

    bool isUserType(edge e, edgeType et)
    {
        OGDF_ASSERT( et < 147);
        return ( (m_edgeTypes[e] & (et << etoUser)) == (et << etoUser));
    }

    //---------------
    //
    // old edge types

    //this is pure nonsense, cause we have uml-edgetype and m_etype, and should be able to 
    //use them with different types, but as long as they arent used correctly (switch instead of xor),
    //use this function to return if e is expansionedge
    //if it is implemented correctly later, delete the array and return m_etype == Graph::expand
    //(the whole function then is obsolete, cause you can check it directly, but for convenience...)
    //should use genexpand, nodeexpand, dissect instead of bool
    void setExpansionEdge(edge e, int expType) {
        m_expansionEdge[e] = expType;
        }

    bool isExpansionEdge(edge e) const {
        return (m_expansionEdge[e] > 0);
    }

    int expansionType(edge e) const { return m_expansionEdge[e]; }

    //precondition normalized
    bool isDegreeExpansionEdge(edge e) const {
        //return (m_eType[e] == Graph::expand);
        return ( m_expansionEdge[e]  == 2);
    }





    const NodeArray<double> &widthOrig() const {
        return m_pGraphAttributes->width();
    }

    double widthOrig(node v) const {
        return m_pGraphAttributes->width(v);
    }

    const NodeArray<double> &heightOrig() const {
        return m_pGraphAttributes->height();
    }

    double heightOrig(node v) const {
        return m_pGraphAttributes->height(v);
    }

    EdgeType typeOrig(edge e) const {
        return m_pGraphAttributes->type(e);
    }

    const GraphAttributes &getGraphAttributes() const {
        return *m_pGraphAttributes;
    }



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

    void expandLowDegreeVertices(OrthoRep &OR);

    void collapseVertices(const OrthoRep &OR, Layout &drawing);

    void removeCrossing(node v); //removes the crossing at node v

    //model a boundary around a star subgraph centered at center
    //and keep external face information (outside the clique
    void insertBoundary(node center, adjEntry& adjExternal);




    virtual edge split(edge e);


    //returns node which was expanded using v
    node expandedNode(node v) const { return m_expandedNode[v]; }

    void setExpandedNode(node v, node w) { m_expandedNode[v] = w; }




    node newCopy(node vOrig, Graph::NodeType vType);

    edge newCopy(node v, adjEntry adjAfter, edge eOrig);

    edge newCopy(node v, adjEntry adjAfter, edge eOrig, CombinatorialEmbedding &E);




    // embeds current copy
    bool embed();

    // removes all crossing nodes which are actually only two "touching" edges
    void removePseudoCrossings();

    // re-inserts edge eOrig by "crossing" the edges in crossedEdges;
    // splits each edge in crossedEdges
    // Precond.: eOrig is an edge in the original graph,
    //           the edges in crossedEdges are in this graph
    void insertEdgePath(edge eOrig, const SList<adjEntry> &crossedEdges);

    // same as insertEdgePath, but assumes that the graph is embedded
    void insertEdgePathEmbedded(
        edge eOrig,
        CombinatorialEmbedding &E,
        const SList<adjEntry> &crossedEdges);

    // removes the complete edge path for edge eOrig
    // Precond.: eOrig s an edge in the original graph
    void removeEdgePathEmbedded(CombinatorialEmbedding &E,
        edge eOrig,
        FaceSetPure &newFaces) {
        GraphCopy::removeEdgePathEmbedded(E,eOrig,newFaces);
    }

    //inserts crossings between two copy edges (used in TopologyModule)
    //replaces crossingedge by first crossingedge part and returns second.
    //the parameter topDown describes he following:
    // if the crossingEdge is running horizontally from left to right,
    // is the crossedEdge direction top->down?
    edge insertCrossing(edge& crossingEdge,
                        const edge crossedEdge,
                        bool topDown);



    void removeDeg1Nodes(Stack<Deg1RestoreInfo> &S, const NodeArray<bool> &mark);

    void restoreDeg1Nodes(Stack<Deg1RestoreInfo> &S, List<node> &deg1s);


protected:

    int m_currentCC; 
    int m_numCC;     

    Array<List<node> >  m_nodesInCC; 
    
    const GraphAttributes* m_pGraphAttributes; 

    //------------
    //object types

    //set the type of eCopy according to the type of eOrig
    //should be virtual if PlanRepUML gets its own
    void setCopyType(edge eCopy, edge eOrig);

    //helper to cope with the edge types, shifting to the right place
    edgeType generalizationPattern() {return etcPrimGeneralization;}
    edgeType associationPattern()    {return etcPrimAssociation;}
    edgeType expansionPattern()      {return etcSecExpansion << etoSecondary;}
    edgeType assClassPattern()       {return etcAssClass << etoTertiary;}
    edgeType brotherPattern()        {return etcBrother   << etoFourth;}
    edgeType halfBrotherPattern()    {return etcHalfBrother   << etoFourth;}
    edgeType cliquePattern()         {return etcSecClique << etoSecondary;} //boundary
    
    
    void removeUnnecessaryCrossing(
        adjEntry adjA1,
        adjEntry adjA2,
        adjEntry adjB1,
        adjEntry adjB2);

//--------------------------------------------------------------------------

    NodeArray<NodeType> m_vType; 

    NodeArray<nodeType> m_nodeTypes; 

    NodeArray<node>     m_expandedNode; 
    NodeArray<adjEntry> m_expandAdj;

    //clique handling: We save an adjEntry of the first edge of an inserted
    //boundary around a clique at its center v
    NodeArray<adjEntry> m_boundaryAdj;

    //zusammenlegbare Typen
    EdgeArray<int>      m_expansionEdge; //1 genmerge, 2 degree (2 highdegree, 3 lowdegree)
    EdgeArray<EdgeType> m_eType;
    
    //m_edgeTypes stores semantic edge type information on several levels: 
    //primary type: generalization, association,...
    //secondary type: merger,...
    //tertiary type: vertical in hierarchy, inner, outer, ...
    //fourth type: neighbour relation (brother, cousin in hierarchy)
    //user types: user defined for local changes
    EdgeArray<edgeType> m_edgeTypes; //store all type information

    //workaround fuer typsuche in insertedgepathembed
    //speichere kopietyp auf originalen
    //maybe it's enough to set gen/ass without extra array
    EdgeArray<edgeType> m_oriEdgeTypes;

    EdgeArray<edge>     m_eAuxCopy; // auxiliary (GraphCopy::initByNodes())

};//PlanRep

} // end namespace ogdf


#endif