UpwardPlanRep.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
 
#include <iostream>
 
namespace ogdf {
 
 
class OGDF_EXPORT UpwardPlanRep : public GraphCopy {
public:
    friend class SubgraphUpwardPlanarizer;
 
#if 0
    //debug only
    friend class FixedEmbeddingUpwardEdgeInserter;
#endif
 
    /* @{
     * \brief Creates a planarized representation with respect to \p Gamma.
     * Gamma muss be an upward planar embedding with a fixed ext. face
     * Precondition: the graph is a single source graph
     */
 
    explicit UpwardPlanRep(
            const CombinatorialEmbedding& Gamma); //upward planar embedding with a fixed ext. face
 
    UpwardPlanRep(const GraphCopy& GC, // must be upward embedded and single source
            adjEntry adj_ext); // the right face of this adjEntry is the external face
 
    UpwardPlanRep(const UpwardPlanRep& UPR);
 
    UpwardPlanRep()
        : GraphCopy()
        , isAugmented(false)
        , t_hat(nullptr)
        , s_hat(nullptr)
        , extFaceHandle(nullptr)
        , crossings(0)
    // multisources(false)
    {
        m_Gamma.init(*this);
        m_isSinkArc.init(*this, false);
        m_isSourceArc.init(*this, false);
    }
 
    virtual ~UpwardPlanRep() { }
 
    void insertEdgePathEmbedded(edge eOrig, SList<adjEntry> crossedEdges, EdgeArray<int>& cost);
 
    // pred. the graph muss be a sinlge source graph
    // We construct node t and connect the sink-switches with t. The new arcs are sSinkArc.
    // For simplicity we construct an additional edge (t,t_hat) (the extFaceArc), where t_hat is the super sink.
    void augment();
 
    bool augmented() const { return isAugmented; }
 
    const CombinatorialEmbedding& getEmbedding() const { return m_Gamma; }
 
    CombinatorialEmbedding& getEmbedding() { return m_Gamma; }
 
    node getSuperSink() const { return t_hat; }
 
    node getSuperSource() const { return s_hat; }
 
    int numberOfCrossings() const { return crossings; }
 
    UpwardPlanRep& operator=(const UpwardPlanRep& copy);
 
    bool isSinkArc(edge e) const { return m_isSinkArc[e]; }
 
    bool isSourceArc(edge e) const { return m_isSourceArc[e]; }
 
    adjEntry sinkSwitchOf(node v) { return m_sinkSwitchOf[v]; }
 
    adjEntry getAdjEntry(const CombinatorialEmbedding& Gamma, node v, face f) const;
 
    //return the left in edge of node v.
    adjEntry leftInEdge(node v) const {
        if (v->indeg() == 0) {
            return nullptr;
        }
 
        adjEntry adjFound = nullptr;
        for (adjEntry adj : v->adjEntries) {
            if (adj->theEdge()->target() == v && adj->cyclicSucc()->theEdge()->source() == v) {
                adjFound = adj;
                break;
            }
        }
        return adjFound;
    }
 
    // debug
    void outputFaces(const CombinatorialEmbedding& embedding) const {
        std::cout << std::endl << "Face UPR " << std::endl;
        for (face f : embedding.faces) {
            std::cout << "face " << f->index() << ": ";
            adjEntry adjNext = f->firstAdj();
            do {
                std::cout << adjNext->theEdge() << "; ";
                adjNext = adjNext->faceCycleSucc();
            } while (adjNext != f->firstAdj());
            std::cout << std::endl;
        }
        if (embedding.externalFace() != nullptr) {
            std::cout << "ext. face of the graph is: " << embedding.externalFace()->index()
                      << std::endl;
        } else {
            std::cout << "no ext. face set." << std::endl;
        }
    }
 
 
protected:
    bool isAugmented; 
 
    CombinatorialEmbedding m_Gamma; 
 
    node t_hat; 
 
    node s_hat; 
 
    // sinkArk are edges which are added to transform the original graph to single sink graph.
    // note: the extFaceHandle is a sink arc.
    EdgeArray<bool> m_isSinkArc;
 
    // source arc are edges which are added to transform the original graph to a single source graph
    EdgeArray<bool> m_isSourceArc;
 
    // 0 if node v is not a non-top-sink-switch of a internal face.
    // else v is (non-top) sink-switch of f (= right face of adjEntry).
    NodeArray<adjEntry> m_sinkSwitchOf;
 
    adjEntry extFaceHandle; // the right face of this adjEntry is always the ext. face
 
    int crossings;
 
 
private:
    void computeSinkSwitches();
 
    void initMe();
 
    void copyMe(const UpwardPlanRep& UPR);
 
    void removeSinkArcs(SList<adjEntry>& crossedEdges);
 
    void constructSinkArcs(face f, node t);
};
 
}