UpwardPlanRep.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_UPWARDPLANREP_H
#define OGDF_UPWARDPLANREP_H


#include <ogdf/basic/GraphCopy.h>

#include <iostream>

//class SubgraphUpwardPlanarizer;



namespace ogdf {


class OGDF_EXPORT UpwardPlanRep : public GraphCopy
{
public:
    
    friend class SubgraphUpwardPlanarizer;

    //debug only
    //friend class FixedEmbeddingUpwardEdgeInserter;

    /* @{
     * \brief Creates a planarized representation with respect to \a Gamma.
     * Gamma muss be an upward planar embedding with a fixed ext. face      
     * Precondition: the graph is a single source graph
     */
    
    UpwardPlanRep(const CombinatorialEmbedding &Gamma); //upward planar embedding with a fixed ext. face            
    
    UpwardPlanRep(const GraphCopy &GC, // muss 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(0), s_hat(0), extFaceHandle(0), 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];}

    // return the adjEntry of v which right face is f.
    adjEntry getAdjEntry(const CombinatorialEmbedding &Gamma, node v, face f) const {
        adjEntry adj;       
        forall_adj(adj, v) {
            if (Gamma.rightFace(adj) == f)
                break;  
        }
    
        OGDF_ASSERT(Gamma.rightFace(adj) == f);
        
        return adj;
    }

    //return the left in edge of node v.
    adjEntry leftInEdge(node v) const 
    {
        if (v->indeg() == 0)
            return 0;
        adjEntry adj;
        forall_adj(adj, v) {
            if (adj->theEdge()->target() == v && adj->cyclicSucc()->theEdge()->source() == v)
                break;
        }
        return adj;
    }

    //*************************** debug ********************************
    void outputFaces (const CombinatorialEmbedding &embedding) const {
        cout << endl << "Face UPR " << endl;            
        face f;
        forall_faces(f, embedding) {
            cout << "face " << f->index() << ": ";
            adjEntry adjNext = f->firstAdj();
            do {
                cout << adjNext->theEdge() << "; ";
                adjNext = adjNext->faceCycleSucc();
            } while(adjNext != f->firstAdj());
            cout << endl;
        }
        if (embedding.externalFace() != 0)
            cout << "ext. face of the graph is: " << embedding.externalFace()->index() << endl;
        else
        cout << "no ext. face set." << 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);

};//UpwardPlanRep

} // end namespace ogdf


#endif