Open
Graph Drawing
Framework

#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;

};


}