PlanRep.h

Go to the documentation of this file.

 
// PlanRep should not know about generalizations and association,
// but we already set types in Attributedgraph, therefore set them
// in PlanRep, too
 
#pragma once
 
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphAttributes.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
#include <ogdf/planarity/EdgeTypePatterns.h>
#include <ogdf/planarity/NodeTypePatterns.h>
 
#include <iosfwd>
 
namespace ogdf {
 
class CombinatorialEmbedding;
class GridLayout;
class Layout;
class OrthoRep;
template<bool>
class FaceSet;
template<class E>
class List;
 
 
class OGDF_EXPORT PlanRep : public GraphCopy {
public:
    struct Deg1RestoreInfo {
        Deg1RestoreInfo() : m_eOriginal(nullptr), m_deg1Original(nullptr), m_adjRef(nullptr) { }
 
        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; 
    };
 
    explicit PlanRep(const Graph& G);
 
    explicit PlanRep(const GraphAttributes& AG);
 
    virtual ~PlanRep() { }
 
 
 
    int numberOfCCs() const { return m_ccInfo.numberOfCCs(); }
 
    int currentCC() const { return m_currentCC; }
 
    const CCsInfo& ccInfo() const { return m_ccInfo; }
 
    int numberOfNodesInCC() const { return numberOfNodesInCC(m_currentCC); }
 
    int numberOfNodesInCC(int cc) const { return stopNode(cc) - startNode(cc); }
 
    node v(int i) const { return m_ccInfo.v(i); }
 
    edge e(int i) const { return m_ccInfo.e(i); }
 
    int startNode() const { return m_ccInfo.startNode(m_currentCC); }
 
    int startNode(int cc) const { return m_ccInfo.startNode(cc); }
 
    int stopNode() const { return m_ccInfo.stopNode(m_currentCC); }
 
    int stopNode(int cc) const { return m_ccInfo.stopNode(cc); }
 
    int startEdge() const { return m_ccInfo.startEdge(m_currentCC); }
 
    int stopEdge() const { return m_ccInfo.stopEdge(m_currentCC); }
 
 
    void initCC(int cc);
 
 
 
    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) const {
        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) const {
        return typeOf(v) == Graph::NodeType::vertex || typeOf(v) == Graph::NodeType::associationClass;
    }
 
    nodeType nodeTypeOf(node v) { return m_nodeTypes[v]; }
 
    void setCrossingType(node v) {
        m_nodeTypes[v] |= UMLNodeTypeConstants::TerCrossing << UMLNodeTypeOffsets::Tertiary;
    }
 
    bool isCrossingType(node v) const {
        return (m_nodeTypes[v] & (UMLNodeTypeConstants::TerCrossing << UMLNodeTypeOffsets::Tertiary))
                != 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) const { 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::EdgeType::association:
            m_edgeTypes[e] = static_cast<edgeType>(UMLEdgeTypeConstants::PrimAssociation);
            break;
        case Graph::EdgeType::generalization:
            m_edgeTypes[e] = static_cast<edgeType>(UMLEdgeTypeConstants::PrimGeneralization);
            break;
        case Graph::EdgeType::dependency:
            m_edgeTypes[e] = static_cast<edgeType>(UMLEdgeTypeConstants::PrimDependency);
            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) const {
        bool check = (((m_edgeTypes[e] & UMLEdgeTypePatterns::Primary)
                              & UMLEdgeTypeConstants::PrimGeneralization)
                == UMLEdgeTypeConstants::PrimGeneralization);
        return check;
    }
 
    void setGeneralization(edge e) {
        setPrimaryType(e, UMLEdgeTypeConstants::PrimGeneralization);
 
        //preliminary set old array too
        m_eType[e] = EdgeType::generalization; //can be removed if edgetypes work properly
    }
 
    bool isDependency(edge e) const {
        bool check = (((m_edgeTypes[e] & UMLEdgeTypePatterns::Primary)
                              & UMLEdgeTypeConstants::PrimDependency)
                == UMLEdgeTypeConstants::PrimDependency);
        return check;
    }
 
    void setDependency(edge e) {
        setPrimaryType(e, UMLEdgeTypeConstants::PrimDependency);
 
        //preliminary set old array too
        m_eType[e] = EdgeType::dependency; //can be removed if edgetypes work properly
    }
 
    void setAssociation(edge e) {
        setPrimaryType(e, UMLEdgeTypeConstants::PrimAssociation);
 
        //preliminary set old array too
        m_eType[e] = EdgeType::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) const {
        return (m_edgeTypes[e] & expansionPattern()) == expansionPattern();
    }
 
    //should add things like cluster and clique boundaries that need rectangle shape
 
    bool isBoundary(edge e) const { return isCliqueBoundary(e); }
 
    //tertiary types
 
    void setAssClass(edge e) { m_edgeTypes[e] |= assClassPattern(); }
 
    bool isAssClass(edge e) const {
        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) const {
        return ((m_edgeTypes[e] & UMLEdgeTypePatterns::Fourth & brotherPattern())
                       >> UMLEdgeTypeOffsets::Fourth)
                == UMLEdgeTypeConstants::Brother;
    }
 
    bool isHalfBrother(edge e) const {
        return ((m_edgeTypes[e] & UMLEdgeTypePatterns::Fourth & halfBrotherPattern())
                       >> UMLEdgeTypeOffsets::Fourth)
                == UMLEdgeTypeConstants::HalfBrother;
    }
 
    //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];
    }
 
    void setPrimaryType(edge e, edgeType et) {
        m_edgeTypes[e] &= 0xfffffff0;
        m_edgeTypes[e] |= (UMLEdgeTypePatterns::Primary & et);
    }
 
    void setPrimaryType(edge e, UMLEdgeTypeConstants et) {
        setPrimaryType(e, static_cast<edgeType>(et));
    }
 
    void setSecondaryType(edge e, edgeType et) {
        m_edgeTypes[e] &= 0xffffff0f;
        m_edgeTypes[e] |= (UMLEdgeTypePatterns::Secondary & (et << UMLEdgeTypeOffsets::Secondary));
    }
 
    edgeType edgeTypePrimaryAND(edge e, edgeType et) {
        m_edgeTypes[e] &= (UMLEdgeTypePatterns::All & et);
        return m_edgeTypes[e];
    }
 
    edgeType edgeTypePrimaryOR(edge e, edgeType et) {
        m_edgeTypes[e] |= et;
        return m_edgeTypes[e];
    }
 
    void setUserType(edge e, edgeType et) {
        OGDF_ASSERT(et < 147);
        m_edgeTypes[e] |= (et << UMLEdgeTypeOffsets::User);
    }
 
    bool isUserType(edge e, edgeType et) const {
        OGDF_ASSERT(et < 147);
        return (m_edgeTypes[e] & (et << UMLEdgeTypeOffsets::User))
                == (et << UMLEdgeTypeOffsets::User);
    }
 
    // 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 {
#if 0
        return (m_eType[e] == Graph::expand);
#else
        return m_expansionEdge[e] == 2;
#endif
    }
 
 
 
 
    const NodeArray<double>& widthOrig() const {
        OGDF_ASSERT(m_pGraphAttributes != nullptr);
        return m_pGraphAttributes->width();
    }
 
    double widthOrig(node v) const {
        OGDF_ASSERT(m_pGraphAttributes != nullptr);
        return m_pGraphAttributes->width(v);
    }
 
    const NodeArray<double>& heightOrig() const {
        OGDF_ASSERT(m_pGraphAttributes != nullptr);
        return m_pGraphAttributes->height();
    }
 
    double heightOrig(node v) const {
        OGDF_ASSERT(m_pGraphAttributes != nullptr);
        return m_pGraphAttributes->height(v);
    }
 
    EdgeType typeOrig(edge e) const {
        OGDF_ASSERT(m_pGraphAttributes != nullptr);
        return m_pGraphAttributes->type(e);
    }
 
    const GraphAttributes& getGraphAttributes() const {
        OGDF_ASSERT(m_pGraphAttributes != nullptr);
        return *m_pGraphAttributes;
    }
 
 
 
    // Expands nodes with degree > 4 and merge nodes for generalizations
    virtual void expand(bool lowDegreeExpand = false);
 
    void expandLowDegreeVertices(OrthoRep& OR);
 
    void collapseVertices(const OrthoRep& OR, Layout& drawing);
    void collapseVertices(const OrthoRep& OR, GridLayout& 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) override;
 
    //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);
 
 
 
 
 
    void insertEdgePath(edge eOrig, const SList<adjEntry>& crossedEdges);
 
    void insertEdgePathEmbedded(edge eOrig, CombinatorialEmbedding& E,
            const SList<adjEntry>& crossedEdges);
 
 
    void removeEdgePathEmbedded(CombinatorialEmbedding& E, edge eOrig, FaceSet<false>& newFaces) {
        GraphCopy::removeEdgePathEmbedded(E, eOrig, newFaces);
    }
 
 
    edge insertCrossing(edge& crossingEdge, edge crossedEdge, bool topDown);
 
 
 
    void removeDeg1Nodes(ArrayBuffer<Deg1RestoreInfo>& S, const NodeArray<bool>& mark);
 
    void restoreDeg1Nodes(ArrayBuffer<Deg1RestoreInfo>& S, List<node>& deg1s);
 
    void writeGML(const char* fileName, const OrthoRep& OR, const GridLayout& drawing);
    void writeGML(std::ostream& os, const OrthoRep& OR, const GridLayout& drawing);
 
protected:
    int m_currentCC; 
    Graph::CCsInfo m_ccInfo;
    //int m_numCC;     //!< The number of components in the original graph.
 
    //Array<List<node> >  m_nodesInCC; //!< The list of original nodes in each component.
 
    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() const {
        return static_cast<edgeType>(UMLEdgeTypeConstants::PrimGeneralization);
    }
 
    edgeType associationPattern() const {
        return static_cast<edgeType>(UMLEdgeTypeConstants::PrimAssociation);
    }
 
    edgeType expansionPattern() const {
        return UMLEdgeTypeConstants::SecExpansion << UMLEdgeTypeOffsets::Secondary;
    }
 
    edgeType assClassPattern() const {
        return UMLEdgeTypeConstants::AssClass << UMLEdgeTypeOffsets::Tertiary;
    }
 
    edgeType brotherPattern() const {
        return UMLEdgeTypeConstants::Brother << UMLEdgeTypeOffsets::Fourth;
    }
 
    edgeType halfBrotherPattern() const {
        return UMLEdgeTypeConstants::HalfBrother << UMLEdgeTypeOffsets::Fourth;
    }
 
    edgeType cliquePattern() const {
        return UMLEdgeTypeConstants::SecClique << UMLEdgeTypeOffsets::Secondary;
    }
 
    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())
};
 
}