MMFixedEmbeddingInserter.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
#include <ogdf/planarity/MMEdgeInsertionModule.h>
#include <ogdf/planarity/PlanRepExpansion.h>
#include <ogdf/planarity/RemoveReinsertType.h>
 
namespace ogdf {
class FaceSet;
class NodeSet;
template<class E1, class E2>
class Tuple2;
template<class E>
class List;
 
 
class OGDF_EXPORT MMFixedEmbeddingInserter : public MMEdgeInsertionModule {
public:
    MMFixedEmbeddingInserter();
 
    // destruction
    virtual ~MMFixedEmbeddingInserter() { }
 
    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:
    virtual ReturnType doCall(PlanRepExpansion& PG, const List<edge>& origEdges,
            const EdgeArray<bool>* forbiddenEdgeOrig) override;
 
 
    void constructDual(const PlanRepExpansion& PG, const CombinatorialEmbedding& E);
 
 
    void findShortestPath(const PlanRepExpansion& PG, const CombinatorialEmbedding& E,
            const List<node>& sources, const List<node>& targets,
            List<Tuple2<adjEntry, adjEntry>>& crossed, const EdgeArray<bool>* forbiddenEdgeOrig);
 
    void prepareAnchorNode(PlanRepExpansion& PG, CombinatorialEmbedding& E, adjEntry& adjStart,
            node srcOrig);
 
    void preprocessInsertionPath(PlanRepExpansion& PG, CombinatorialEmbedding& E, node srcOrig,
            node tgtOrig,
            //PlanRepExpansion::nodeSplit ns,
            List<Tuple2<adjEntry, adjEntry>>& crossed);
 
    void insertEdge(PlanRepExpansion& PG, CombinatorialEmbedding& E, edge eOrig, node srcOrig,
            node tgtOrig, PlanRepExpansion::NodeSplit* nodeSplit,
            List<Tuple2<adjEntry, adjEntry>>& crossed);
 
    void removeEdge(PlanRepExpansion& PG, CombinatorialEmbedding& E, edge eOrig,
            PlanRepExpansion::NodeSplit* nodeSplit, node& oldSrc, node& oldTgt);
 
    void insertDualEdge(node vDual, adjEntry adj, const CombinatorialEmbedding& E);
 
    void insertDualEdges(node v, const CombinatorialEmbedding& E);
 
    void contractSplit(PlanRepExpansion& PG, CombinatorialEmbedding& E,
            PlanRepExpansion::NodeSplit* nodeSplit);
 
    void contractSplitIfReq(PlanRepExpansion& PG, CombinatorialEmbedding& E, node u,
            const PlanRepExpansion::nodeSplit nsCurrent = nullptr);
 
    void convertDummy(PlanRepExpansion& PG, CombinatorialEmbedding& E, node u, node vOrig,
            PlanRepExpansion::nodeSplit ns);
 
    void collectAnchorNodes(node v, NodeSet& nodes, const PlanRepExpansion::NodeSplit* nsParent,
            const PlanRepExpansion& PG) const;
 
    void anchorNodes(node vOrig, NodeSet& nodes, const PlanRepExpansion& PG) const;
 
    void findSourcesAndTargets(node src, node tgt, NodeSet& sources, NodeSet& targets,
            const PlanRepExpansion& PG) const;
 
    node commonDummy(NodeSet& sources, NodeSet& targets);
 
    bool checkDualGraph(PlanRepExpansion& PG, const CombinatorialEmbedding& E) const;
 
    bool checkSplitDeg(PlanRepExpansion& PG) const;
 
    bool origOfDualForbidden(edge e, const PlanRepExpansion& PG,
            const EdgeArray<bool>* forbiddenEdgeOrig) const {
        if (forbiddenEdgeOrig == nullptr) {
            return false;
        }
 
        if (e->source() == m_vS || e->target() == m_vT) {
            return false;
        }
 
        if (m_primalNode[e->source()] != nullptr) {
            return false;
        }
        if (m_primalNode[e->target()] != nullptr) {
            return false;
        }
 
        adjEntry adj = m_primalAdj[e];
        if (adj == nullptr) {
            return false;
        }
 
        edge eOrig = PG.originalEdge(adj->theEdge());
        if (eOrig != nullptr) {
#if 0
            if((*forbiddenEdgeOrig)[eOrig]) {
                std::cout << "forbidden: " << eOrig << ", dual: " << e << std::endl;
            }
#endif
            return (*forbiddenEdgeOrig)[eOrig];
        } else {
            return false;
        }
    }
 
    void drawDual(const PlanRepExpansion& PG, const EdgeArray<bool>* forbiddenEdgeOrig);
 
    RemoveReinsertType m_rrOption; 
    double m_percentMostCrossed; 
 
    Graph m_dual; 
    FaceArray<node> m_dualOfFace; 
    NodeArray<node> m_dualOfNode; 
    NodeArray<node> m_primalNode; 
    EdgeArray<adjEntry> m_primalAdj; 
    AdjEntryArray<edge> m_dualEdge; 
    EdgeArray<int> m_dualCost; 
 
    node m_vS; 
    node m_vT; 
    int m_maxCost; 
 
    FaceSet* m_delFaces;
    FaceSet* m_newFaces;
    NodeSet* m_mergedNodes;
};
 
}