CombinatorialEmbedding.h

Go to the documentation of this file.

/*
 * $Revision: 2047 $
 * 
 * last checkin:
 *   $Author: klein $ 
 *   $Date: 2010-10-13 17:12:21 +0200 (Wed, 13 Oct 2010) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_COMBINATORIAL_EMBEDDING_H
#define OGDF_COMBINATORIAL_EMBEDDING_H


#include <ogdf/basic/AdjEntryArray.h>


namespace ogdf {

class OGDF_EXPORT ConstCombinatorialEmbedding;

typedef FaceElement *face;

class OGDF_EXPORT FaceElement : private GraphElement
{
    friend class ConstCombinatorialEmbedding;
    friend class CombinatorialEmbedding;
    friend class GraphList<FaceElement>;

    adjEntry m_adjFirst; 
    int m_id;   
    int m_size; 

#ifdef OGDF_DEBUG
    const ConstCombinatorialEmbedding *m_pEmbedding;
#endif

    // constructor
#ifdef OGDF_DEBUG
    FaceElement(const ConstCombinatorialEmbedding *pEmbedding,
        adjEntry adjFirst,
        int id) :
        m_adjFirst(adjFirst), m_id(id), m_size(0), m_pEmbedding(pEmbedding) { }
#else

    FaceElement(adjEntry adjFirst, int id) :
        m_adjFirst(adjFirst), m_id(id), m_size(0) { }
#endif

public:
    int index() const { return m_id; }

    adjEntry firstAdj() const { return m_adjFirst; }

    int size() const { return m_size; }

    face succ() const { return (face)m_next; }

    face pred() const { return (face)m_prev; }

    adjEntry nextFaceEdge(adjEntry adj) const {
        adj = adj->faceCycleSucc();
        return (adj != m_adjFirst) ? adj : 0;
    }

#ifdef OGDF_DEBUG
    const ConstCombinatorialEmbedding *embeddingOf() const { return m_pEmbedding; }
#endif

    OGDF_NEW_DELETE
}; // class FaceElement


class FaceArrayBase;
template<class T>class FaceArray;


class OGDF_EXPORT ConstCombinatorialEmbedding
{
protected:
    const Graph *m_cpGraph; 

    GraphList<FaceElement> m_faces; 
    int m_nFaces; 
    int m_faceIdCount; 
    int m_faceArrayTableSize; 

    AdjEntryArray<face> m_rightFace; 
    face m_externalFace; 

    mutable ListPure<FaceArrayBase*> m_regFaceArrays; 

public:
    ConstCombinatorialEmbedding();

    explicit ConstCombinatorialEmbedding(const Graph &G);


    ConstCombinatorialEmbedding(const ConstCombinatorialEmbedding &C);

    ConstCombinatorialEmbedding &operator=(const ConstCombinatorialEmbedding &C);

    const Graph &getGraph() const { return *m_cpGraph; }

    operator const Graph &() const { return *m_cpGraph; }

    face firstFace() const { return m_faces.begin(); }

    face lastFace() const { return m_faces.rbegin(); }

    int numberOfFaces() const { return m_nFaces; }

    face rightFace(adjEntry adj) const { return m_rightFace[adj]; }

    face leftFace(adjEntry adj) const { return m_rightFace[adj->twin()]; }

    int maxFaceIndex() const { return m_faceIdCount-1; }

    int faceArrayTableSize() const { return m_faceArrayTableSize; }

    face chooseFace() const;

    face maximalFace() const;

    face externalFace() const {
        return m_externalFace;
    }

    void setExternalFace(face f) {
        OGDF_ASSERT(f->embeddingOf() == this);
        m_externalFace = f;
    }

    bool isBridge(edge e) const {
        return m_rightFace[e->adjSource()] == m_rightFace[e->adjTarget()];
    }

    void init(const Graph &G);

    void computeFaces();
    

    bool consistencyCheck();


    ListIterator<FaceArrayBase*> registerArray(FaceArrayBase *pFaceArray) const;

    void unregisterArray(ListIterator<FaceArrayBase*> it) const;

protected:
    face createFaceElement(adjEntry adjFirst);

    void reinitArrays();

}; // class ConstCombinatorialEmbedding



class OGDF_EXPORT CombinatorialEmbedding : public ConstCombinatorialEmbedding
{
    Graph *m_pGraph; 

    // the following methods are private in order to make them unusable
    // It is not clear which meaning copying of a comb. embedding should
    // have since we only store a pointer to the topology (Graph)
    CombinatorialEmbedding(const CombinatorialEmbedding &) : ConstCombinatorialEmbedding() { }
    CombinatorialEmbedding &operator=(const CombinatorialEmbedding &) {
        return *this;
    }

public:
    CombinatorialEmbedding() : ConstCombinatorialEmbedding() {
        m_pGraph = 0;
    }

    explicit CombinatorialEmbedding(Graph &G) : ConstCombinatorialEmbedding(G) {
        m_pGraph = &G;
    }



    const Graph &getGraph() const { return *m_cpGraph; }
    
    Graph &getGraph() { return *m_pGraph; }

    operator const Graph &() const { return *m_cpGraph; }

    operator Graph &() { return *m_pGraph; }




    void init(Graph &G) {
        ConstCombinatorialEmbedding::init(G);
        m_pGraph = &G;
    }

    void clear();




    edge split(edge e);

    void unsplit(edge eIn, edge eOut);

    node splitNode(adjEntry adjStartLeft, adjEntry adjStartRight);

    node contract(edge e);

    edge splitFace(adjEntry adjSrc, adjEntry adjTgt);

    // incremental stuff

    //special version of the above function doing a pushback of the new edge
    //on the adjacency list of v making it possible to insert new degree 0
    //nodes into a face
    edge splitFace(node v, adjEntry adjTgt);
    edge splitFace(adjEntry adjSrc, node v);

    face joinFaces(edge e);

    void reverseEdge(edge e);

    void moveBridge(adjEntry adjBridge, adjEntry adjBefore);

    void removeDeg1(node v);

    void updateMerger(edge e, face fRight, face fLeft);


}; // class CombinatorialEmbedding


//---------------------------------------------------------
// iteration macros
//---------------------------------------------------------

#define forall_faces(f,E) for((f)=(E).firstFace(); (f); (f)=(f)->succ())


#define forall_rev_faces(f,E) for((f)=(E).lastFace(); (f); (f)=(f)->pred())

#define forall_face_adj(adj,f) for((adj)=(f)->firstAdj(); (adj); (adj)=(f)->nextFaceEdge(adj))


} // end namespace ogdf


#endif