FixEdgeInserterCore.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/FaceSet.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/Module.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/Timeouter.h>
#include <ogdf/basic/basic.h>
#include <ogdf/planarity/PlanRepLight.h>
 
#include <cstdint>
 
namespace ogdf {
enum class RemoveReinsertType;
template<class E>
class QueuePure;
 
class OGDF_EXPORT FixEdgeInserterCore : public Timeouter {
public:
    FixEdgeInserterCore(PlanRepLight& pr, const EdgeArray<int>* pCostOrig,
            const EdgeArray<bool>* pForbiddenOrig, const EdgeArray<uint32_t>* pEdgeSubgraphs)
        : m_pr(pr), m_pCost(pCostOrig), m_pForbidden(pForbiddenOrig), m_pSubgraph(pEdgeSubgraphs) { }
 
    virtual ~FixEdgeInserterCore() { }
 
    Module::ReturnType call(const Array<edge>& origEdges, bool keepEmbedding,
            RemoveReinsertType rrPost, double percentMostCrossed);
 
    int runsPostprocessing() const { return m_runsPostprocessing; }
 
protected:
    int getCost(edge e, int stSubGraph) const;
    void findShortestPath(const CombinatorialEmbedding& E, edge eOrig, SList<adjEntry>& crossed);
    void findWeightedShortestPath(const CombinatorialEmbedding& E, edge eOrig,
            SList<adjEntry>& crossed);
 
    int costCrossed(edge eOrig) const;
    void insertEdge(CombinatorialEmbedding& E, edge eOrig, const SList<adjEntry>& crossed);
    void removeEdge(CombinatorialEmbedding& E, edge eOrig);
 
    virtual void storeTypeOfCurrentEdge(edge eOrig) { }
 
    virtual void init(CombinatorialEmbedding& E);
    virtual void cleanup();
    virtual void constructDual(const CombinatorialEmbedding& E);
 
    virtual void appendCandidates(QueuePure<edge>& queue, node v);
    virtual void appendCandidates(Array<SListPure<edge>>& nodesAtDist, EdgeArray<int>& costDual,
            int maxCost, node v, int currentDist);
 
    virtual void insertEdgesIntoDual(const CombinatorialEmbedding& E, adjEntry adjSrc);
    virtual void insertEdgesIntoDualAfterRemove(const CombinatorialEmbedding& E, face f);
 
    PlanRepLight& m_pr;
 
    const EdgeArray<int>* m_pCost;
    const EdgeArray<bool>* m_pForbidden;
    const EdgeArray<uint32_t>* m_pSubgraph;
 
    Graph m_dual; 
 
    EdgeArray<adjEntry> m_primalAdj; 
    FaceArray<node> m_nodeOf; 
 
    FaceSet<false>* m_delFaces;
    FaceSet<false>* m_newFaces;
 
    node m_vS; 
    node m_vT; 
 
    int m_runsPostprocessing; 
};
 
class FixEdgeInserterUMLCore : public FixEdgeInserterCore {
public:
    FixEdgeInserterUMLCore(PlanRepLight& pr, const EdgeArray<int>* pCostOrig,
            const EdgeArray<uint32_t>* pEdgeSubgraph)
        : FixEdgeInserterCore(pr, pCostOrig, nullptr, pEdgeSubgraph) { }
 
protected:
    void storeTypeOfCurrentEdge(edge eOrig) override { m_typeOfCurrentEdge = m_pr.typeOrig(eOrig); }
 
    void init(CombinatorialEmbedding& E) override;
    void cleanup() override;
    void constructDual(const CombinatorialEmbedding& E) override;
 
    void appendCandidates(QueuePure<edge>& queue, node v) override;
    void appendCandidates(Array<SListPure<edge>>& nodesAtDist, EdgeArray<int>& costDual,
            int maxCost, node v, int currentDist) override;
 
    void insertEdgesIntoDual(const CombinatorialEmbedding& E, adjEntry adjSrc) override;
    void insertEdgesIntoDualAfterRemove(const CombinatorialEmbedding& E, face f) override;
 
    EdgeArray<bool> m_primalIsGen; 
    Graph::EdgeType m_typeOfCurrentEdge;
};
 
}