TopologyModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EdgeComparer.h>
#include <ogdf/basic/GraphAttributes.h>
#include <ogdf/planarity/PlanRep.h>
 
namespace ogdf {
 
namespace topology_module {
 
 
class EdgeLeg {
public:
    EdgeLeg() : m_xp(0.0, 0.0), m_topDown(false), m_copyEdge(nullptr), m_number(0) { }
 
    EdgeLeg(edge e, int number, DPoint p1, DPoint p2)
        : m_xp(DPoint(0.0, 0.0))
        , m_topDown(false)
        , m_copyEdge(e)
        , m_p1(p1)
        , m_p2(p2)
        , m_number(number) { }
 
    DPoint& start() { return m_p1; }
 
    DPoint& end() { return m_p2; }
 
    int& number() { return m_number; }
 
    edge& copyEdge() { return m_copyEdge; }
 
    DPoint m_xp;
    bool m_topDown;
 
    ListIterator<EdgeLeg*> m_eIterator;
 
private:
    edge m_copyEdge; 
    DPoint m_p1, m_p2; 
    int m_number; 
};
 
}
 
 
class OGDF_EXPORT TopologyModule {
public:
 
    enum class Options {
        DegOneCrossings = 0x0001,
        GenToAss = 0x0002,
        CrossFlip = 0x0004,
        FlipUML = 0x0010,
        Loop = 0x0008,
    };
 
private:
    friend int operator|(int, TopologyModule::Options);
    friend int operator|(TopologyModule::Options, TopologyModule::Options);
 
public:
    TopologyModule()
        : m_options(Options::DegOneCrossings | Options::GenToAss | Options::CrossFlip
                | Options::Loop | Options::FlipUML) { }
 
    virtual ~TopologyModule() { }
 
    void setOptions(int i) { m_options = i; }
 
    void addOption(TopologyModule::Options o) { m_options = m_options | o; }
 
 
    bool setEmbeddingFromGraph(PlanRep& PG, GraphAttributes& GA, adjEntry& adjExternal,
            bool setExternal = true, bool reuseGAEmbedding = false);
 
 
    void sortEdgesFromLayout(Graph& G, GraphAttributes& GA);
 
    face getExternalFace(PlanRep& PG, const GraphAttributes& AG);
 
    double faceSum(PlanRep& PG, const GraphAttributes& AG, face f);
 
protected:
    //compute a planarization, i.e. insert crossing vertices,
    //corresponding to the AG layout
    void planarizeFromLayout(PlanRep& PG, GraphAttributes& AG);
    //compute crossing point and return if existing
    bool hasCrossing(topology_module::EdgeLeg* legA, topology_module::EdgeLeg* legB, DPoint& xp);
    //check if node v is a crossing of two edges with a common
    //endpoint adjacent to v, crossing is removed if flip is set
    bool checkFlipCrossing(PlanRep& PG, node v, bool flip = true);
 
    void postProcess(PlanRep& PG);
    void handleImprecision(PlanRep& PG);
    bool skipable(topology_module::EdgeLeg* legA, topology_module::EdgeLeg* legB);
 
private:
    //compare vectors for sorting
    int compare_vectors(const double& x1, const double& y1, const double& x2, const double& y2);
    //compute and return the angle defined by p-q,p-r
    double angle(DPoint p, DPoint q, DPoint r);
    //we have to save the position of the inserted crossing vertices
    //in order to compute the external face
    NodeArray<DPoint> m_crossPosition;
 
    //we save a list of EdgeLegs for all original edges in
    //AG
    EdgeArray<List<topology_module::EdgeLeg*>> m_eLegs;
 
    //option settings as bits
    int m_options;
};
 
inline int operator&(int i, TopologyModule::Options b) { return i & static_cast<int>(b); }
 
inline int operator|(TopologyModule::Options a, TopologyModule::Options b) {
    return static_cast<int>(a) | static_cast<int>(b);
}
 
inline int operator|(int i, TopologyModule::Options b) { return i | static_cast<int>(b); }
 
}