doc/ogdf/_m_m_variable_embedding_inserter_8h_source.html

#pragma once


#include <ogdf/planarity/MMEdgeInsertionModule.h>

#include <ogdf/planarity/RemoveReinsertType.h>

#include <ogdf/basic/CombinatorialEmbedding.h>

#include <ogdf/basic/FaceArray.h>

#include <ogdf/basic/NodeSet.h>

#include <ogdf/basic/tuples.h>


namespace ogdf {


class OGDF_EXPORT MMVariableEmbeddingInserter : public MMEdgeInsertionModule

{

public:

    MMVariableEmbeddingInserter();


    // destruction

    virtual ~MMVariableEmbeddingInserter() { }


    void removeReinsert(RemoveReinsertType rrOption) {

        OGDF_ASSERT(rrOption != RemoveReinsertType::IncInserted);

        m_rrOption = rrOption;

    }


    RemoveReinsertType removeReinsert() const {

        return m_rrOption;

    }


    void percentMostCrossed(double percent) {

        m_percentMostCrossed = percent;

    }


    double percentMostCrossed() const {

        return m_percentMostCrossed;

    }


private:

    class Block;

    class ExpandedSkeleton;


    using Crossing = PlanRepExpansion::Crossing;


    struct AnchorNodeInfo {

        AnchorNodeInfo() { m_adj_1 = m_adj_2 = nullptr; }

        AnchorNodeInfo(adjEntry adj) {

            m_adj_1 = adj;

            m_adj_2 = nullptr;

        }

        AnchorNodeInfo(adjEntry adj_1, adjEntry adj_2) {

            m_adj_1 = adj_1;

            m_adj_2 = adj_2;

        }


        adjEntry m_adj_1;

        adjEntry m_adj_2;

    };


    enum class PathType { pathToEdge = 0, pathToSource = 1, pathToTarget = 2 };


    struct Paths {

        Paths() :

            m_addPartLeft(3), m_addPartRight(3),

            m_paths(3),

            m_src(0,2,nullptr), m_tgt(0,2,nullptr),

            m_pred(0,2,PathType::pathToEdge)

        { }


        Array<SList<adjEntry> > m_addPartLeft;

        Array<SList<adjEntry> > m_addPartRight;

        Array<List<Crossing> >  m_paths;

        Array<AnchorNodeInfo>   m_src;

        Array<AnchorNodeInfo>   m_tgt;

        Array<PathType>         m_pred;

    };


    virtual ReturnType doCall(

        PlanRepExpansion &PG,

        const List<edge> &origEdges,

        const EdgeArray<bool> *forbiddenEdgeOrig) override;


    void collectAnchorNodes(

        node v,

        NodeSet<> &nodes,

        const PlanRepExpansion::NodeSplit *nsParent) const;


    void findSourcesAndTargets(

        node src, node tgt,

        NodeSet<> &sources,

        NodeSet<> &targets) const;


    void anchorNodes(

        node vOrig,

        NodeSet<> &nodes) const;


    static node commonDummy(

        NodeSet<> &sources,

        NodeSet<> &targets);


    void insert(List<Crossing> &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd);


    node prepareAnchorNode(

        const AnchorNodeInfo &anchor,

        node vOrig,

        bool isSrc,

        edge &eExtra);


    void preprocessInsertionPath(

        const AnchorNodeInfo &srcInfo,

        const AnchorNodeInfo &tgtInfo,

        node srcOrig,

        node tgtOrig,

        node &src,

        node &tgt,

        edge &eSrc,

        edge &eTgt);


    node preparePath(

        node vAnchor,

        adjEntry adjPath,

        bool bOrigEdge,

        node vOrig);


    void findPseudos(

        node vDummy,

        adjEntry adjSrc,

        AnchorNodeInfo &infoSrc,

        SListPure<node> &pseudos);


    void insertWithCommonDummy(

        edge eOrig,

        node vDummy,

        node &src,

        node &tgt);


    bool dfsVertex(node v,

        int parent,

        List<Crossing> &eip,

        AnchorNodeInfo &vStart,

        AnchorNodeInfo &vEnd);


    bool dfsBlock(int i,

        node parent,

        node &repS,

        List<Crossing> &eip,

        AnchorNodeInfo &vStart,

        AnchorNodeInfo &vEnd);


    bool pathSearch(node v, edge parent, const Block &BC, List<edge> &path);


    void blockInsert(

        Block &BC,

        List<Crossing> &L,

        AnchorNodeInfo &srcInfo,

        AnchorNodeInfo &tgtInfo);


    void buildSubpath(

        node v,

        edge eIn,

        edge eOut,

        Paths &paths,

        bool &bPathToEdge,

        bool &bPathToSrc,

        bool &bPathToTgt,

        ExpandedSkeleton &Exp);


    void contractSplitIfReq(node u);

    void convertDummy(

        node u,

        node vOrig,

        PlanRepExpansion::nodeSplit ns_0);


    void writeEip(const List<Crossing> &eip);


    RemoveReinsertType m_rrOption;

    double m_percentMostCrossed;


    PlanRepExpansion *m_pPG;


    NodeSet<> *m_pSources;

    NodeSet<> *m_pTargets;


    NodeArray<SList<int> > m_compV;

    Array<SList<node> >    m_nodeB;

    Array<SList<edge> >    m_edgeB;

    NodeArray<node>        m_GtoBC;


    bool m_conFinished;

    const EdgeArray<bool> *m_forbiddenEdgeOrig;

};


}