SimpleIncNodeInserter.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/IncNodeInserter.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
 
namespace ogdf {
class PlanRepInc;
template<class E>
class List;
 
class OGDF_EXPORT SimpleIncNodeInserter : public IncNodeInserter {
public:
    //creates inserter on PG
    explicit SimpleIncNodeInserter(PlanRepInc& PG);
    virtual ~SimpleIncNodeInserter();
 
    //insert copy in m_planRep for original node v
    void insertCopyNode(node v, CombinatorialEmbedding& E, Graph::NodeType vTyp) override;
 
    //insert copy without respecting embedding
    void insertCopyNode(node v, Graph::NodeType vTyp);
 
protected:
    //insertAfterAdj will be filled with adjEntries for the
    //(new) edges around the copy of v to be inserted after.
    //sorted in the order of the edge around v
    face getInsertionFace(node v, CombinatorialEmbedding& E) override;
 
    //constructs a dual graph on the copy PlanRep,
    //vCopy is the node to be inserted
    void constructDual(const Graph& G, const CombinatorialEmbedding& E, bool forbidCrossings = true);
 
    void insertFaceEdges(node v, node vCopy, face f, CombinatorialEmbedding& E, adjEntry& adExternal);
    void insertCrossingEdges(node v, node vCopy, CombinatorialEmbedding& E, adjEntry& adExternal);
    void findShortestPath(const CombinatorialEmbedding& E, node s, node t, Graph::EdgeType eType,
            SList<adjEntry>& crossed);
    void insertEdge(CombinatorialEmbedding& E, edge eOrig, const SList<adjEntry>& crossed,
            bool forbidCrossingGens);
 
private:
    inline void updateComponentNumber(node vCopy, node wCopy, CombinatorialEmbedding& E,
            adjEntry adExternal);
 
    //dual graph for the edge insertion
    Graph m_dual;
    FaceArray<node> m_nodeOf; 
    NodeArray<bool> m_insertFaceNode; 
    NodeArray<bool> m_vAdjNodes; 
    NodeArray<List<edge>*> m_incidentEdges; 
    EdgeArray<adjEntry> m_primalAdj; 
    EdgeArray<bool> m_primalIsGen; 
    bool m_forbidCrossings; 
    node m_vS; 
    node m_vT; 
};
 
}