FixedEmbeddingUpwardEdgeInserter.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/upward/UpwardEdgeInserterModule.h>
#include <ogdf/upward/UpwardPlanarity.h>
 
namespace ogdf {
class UpwardPlanRep;
template<class E>
class List;
template<class E>
class SList;
 
class OGDF_EXPORT FixedEmbeddingUpwardEdgeInserter : public UpwardEdgeInserterModule {
public:
    FixedEmbeddingUpwardEdgeInserter() { }
 
    ~FixedEmbeddingUpwardEdgeInserter() { }
 
 
private:
    bool isUpwardPlanar(Graph& G) const { return UpwardPlanarity::isUpwardPlanar_singleSource(G); }
 
    virtual ReturnType doCall(UpwardPlanRep& UPR, const List<edge>& origEdges,
            const EdgeArray<int>* costOrig = nullptr,
            const EdgeArray<bool>* forbiddenEdgeOrig = nullptr) override;
 
 
    ReturnType insertAll(UpwardPlanRep& UPR, List<edge>& toInsert, EdgeArray<int>& cost);
 
 
    void staticLock(UpwardPlanRep& UPR, EdgeArray<bool>& locked, const List<edge>& origEdges,
            edge e_orig);
 
    void dynamicLock(UpwardPlanRep& UPR, EdgeArray<bool>& locked, face f, adjEntry e_cur);
 
    void nextFeasibleEdges(UpwardPlanRep& UPR, List<adjEntry>& nextEdges, face f, adjEntry e_cur,
            EdgeArray<bool>& locked, bool heuristic);
 
    void minFIP(UpwardPlanRep& UPR, List<edge>& origEdges, EdgeArray<int>& cost, edge e_orig,
            SList<adjEntry>& path) {
        getPath(UPR, origEdges, cost, e_orig, path, false);
    }
 
    void constraintFIP(UpwardPlanRep& UPR, List<edge>& origEdges, EdgeArray<int>& cost, edge e_orig,
            SList<adjEntry>& path) {
        getPath(UPR, origEdges, cost, e_orig, path, true);
    }
 
    void getPath(UpwardPlanRep& UPR, List<edge>& origEdges, EdgeArray<int>& cost, edge e_orig,
            SList<adjEntry>& path, bool heuristic);
 
 
    void markUp(const Graph& G, node v, EdgeArray<bool>& markedEdges);
 
 
    void markDown(const Graph& G, node v, EdgeArray<bool>& markedEdges);
 
    void feasibleEdges(UpwardPlanRep& UPR,
            face f, // current face
            adjEntry adj, // current adjEntry, right face muss be f
            EdgeArray<bool>& locked, // we compute the dyn. locked edges on the fly with respect to e
            List<adjEntry>& feasible, // the list of feasible edges in f with respect to e
            bool heuristic);
 
    bool isConstraintFeasible(UpwardPlanRep& UPR, const List<edge>& orig_edges, edge e_orig,
            adjEntry adjCurrent,
            adjEntry adjNext, // the next adjEntry of the current insertion path
            EdgeArray<adjEntry>& predAdj //Array to reconstruction the insertion path
    );
 
 
    bool isConstraintFeasible(UpwardPlanRep& UPR, List<edge>& origEdges, edge e_orig,
            SList<adjEntry>& path);
};
 
}