MultiEdgeApproxInserter.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
#include <ogdf/planarity/EdgeInsertionModule.h>
#include <ogdf/planarity/PlanRepLight.h>
 
#include <cstdint>
 
namespace ogdf {
class StaticPlanarSPQRTree;
enum class RemoveReinsertType;
 
 
class OGDF_EXPORT MultiEdgeApproxInserter : public EdgeInsertionModule {
public:
    MultiEdgeApproxInserter();
 
    MultiEdgeApproxInserter(const MultiEdgeApproxInserter& inserter);
 
    ~MultiEdgeApproxInserter() { }
 
    virtual EdgeInsertionModule* clone() const override;
 
    MultiEdgeApproxInserter& operator=(const MultiEdgeApproxInserter& inserter);
 
    void removeReinsertFix(RemoveReinsertType rrOption) { m_rrOptionFix = rrOption; }
 
    RemoveReinsertType removeReinsertFix() const { return m_rrOptionFix; }
 
    void removeReinsertVar(RemoveReinsertType rrOption) { m_rrOptionVar = rrOption; }
 
    RemoveReinsertType removeReinsertVar() const { return m_rrOptionVar; }
 
 
    void percentMostCrossedFix(double percent) { m_percentMostCrossedFix = percent; }
 
    double percentMostCrossedFix() const { return m_percentMostCrossedFix; }
 
 
    void percentMostCrossedVar(double percent) { m_percentMostCrossedVar = percent; }
 
    double percentMostCrossedVar() const { return m_percentMostCrossedVar; }
 
    void statistics(bool b) { m_statistics = b; }
 
    bool statistics() const { return m_statistics; }
 
    int sumInsertionCosts() const { return m_sumInsertionCosts; }
 
    int sumFEInsertionCosts() const { return m_sumFEInsertionCosts; }
 
private:
    enum class PathDir { Left, Right, None };
 
    static inline PathDir oppDir(PathDir dir) {
        switch (dir) {
        case PathDir::Left:
            return PathDir::Right;
        case PathDir::Right:
            return PathDir::Left;
        default:
            return PathDir::None;
        }
    };
 
    class Block;
    class EmbeddingPreference;
 
    struct VertexBlock {
        VertexBlock(node v, int b) : m_vertex(v), m_block(b) { }
 
        node m_vertex;
        int m_block;
    };
 
    ReturnType doCall(PlanRepLight& pr, const Array<edge>& origEdges, const EdgeArray<int>* costOrig,
            const EdgeArray<bool>* forbiddenEdge, const EdgeArray<uint32_t>* edgeSubGraphs) override;
 
    MultiEdgeApproxInserter::Block* constructBlock(int i);
    node copy(node vOrig, int b);
 
    static bool dfsPathSPQR(node v, node v2, edge eParent, List<edge>& path);
    int computePathSPQR(int b, node v, node w, int k);
 
    bool dfsPathVertex(node v, int parent, int k, node t);
    bool dfsPathBlock(int b, node parent, int k, node t);
    void computePathBC(int k);
 
    void embedBlock(int b, int m);
    void recFlipPref(adjEntry adjP, NodeArray<EmbeddingPreference>& pi_pick,
            const NodeArray<bool>& visited, StaticPlanarSPQRTree& spqr);
 
    void cleanup();
 
    RemoveReinsertType m_rrOptionFix; 
    RemoveReinsertType m_rrOptionVar; 
    double m_percentMostCrossedFix; 
    double m_percentMostCrossedVar; 
    bool m_statistics; // !< Generates further statistic information.
 
    PlanRepLight* m_pPG; // pointer to plan-rep passed in call
    const EdgeArray<int>* m_costOrig;
 
    NodeArray<SList<int>> m_compV; //  m_compV[v] = list of blocks containing v
    Array<SList<node>> m_verticesB; // m_verticesB[i] = list of vertices in block i
    Array<SList<edge>> m_edgesB; // edgesB[i] = list of edges in block i
    NodeArray<node> m_GtoBC; // temporary mapping of nodes in PG to copies in block
    NodeArray<SList<VertexBlock>> m_copyInBlocks; // mapping of nodes in PG to copies in block
 
    const Array<edge>* m_edge; // pointer to array of edges to be inserted
    Array<List<VertexBlock>> m_pathBCs; // insertion path in BC-tree for each edge
    Array<int> m_insertionCosts; // computed insertion costs for each edge
    Array<Block*> m_block; // array of blocks
 
    // statistics of last run
    int m_sumInsertionCosts;
    int m_sumFEInsertionCosts;
 
    // just for testing
    void constructDual(const PlanRepLight& pr);
    int findShortestPath(node s, node t);
 
    ConstCombinatorialEmbedding m_E;
    Graph m_dual;
    FaceArray<node> m_faceNode;
    AdjEntryArray<adjEntry> m_primalAdj;
    node m_vS, m_vT;
};
 
}