MMVariableEmbeddingInserter.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphSets.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
#include <ogdf/planarity/MMEdgeInsertionModule.h>
#include <ogdf/planarity/PlanRepExpansion.h>
#include <ogdf/planarity/RemoveReinsertType.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;
};
 
}