GraphCopy.h

Go to the documentation of this file.

/*
 * $Revision: 2027 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2010-09-01 11:55:17 +0200 (Wed, 01 Sep 2010) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_GRAPH_COPY_H
#define OGDF_GRAPH_COPY_H


#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/CombinatorialEmbedding.h>


namespace ogdf {

class OGDF_EXPORT FaceSetPure;


//---------------------------------------------------------
// GraphCopySimple
// simple graph copies (no support for edge splitting)
//---------------------------------------------------------
class OGDF_EXPORT GraphCopySimple : public Graph {

    const Graph *m_pGraph;   
    NodeArray<node> m_vOrig; 
    NodeArray<node> m_vCopy; 
    EdgeArray<edge> m_eOrig; 
    EdgeArray<edge> m_eCopy; 

public:
    // construction

    GraphCopySimple(const Graph &G);

    GraphCopySimple(const GraphCopySimple &GC);

    virtual ~GraphCopySimple() {};

    const Graph &original() const { return *m_pGraph; }

    node original(node v) const { return m_vOrig[v]; }

    edge original(edge e) const { return m_eOrig[e]; }

    node copy(node v) const { return m_vCopy[v]; }

    edge copy(edge e) const { return m_eCopy[e]; }

    bool isDummy(node v) const { return (m_vOrig[v] == 0); }

    bool isDummy(edge e) const { return (m_eOrig[e] == 0); }

    GraphCopySimple &operator=(const GraphCopySimple &GC);


    node newNode() {
        return Graph::newNode();
    }

    node newNode(node vOrig) {
        OGDF_ASSERT(vOrig != 0 && vOrig->graphOf() == m_pGraph);
        node v = Graph::newNode();
        m_vCopy[m_vOrig[v] = vOrig] = v;
        return v;
    }

    edge newEdge(node v, node w) {
        return Graph::newEdge(v,w);
    }

    edge newEdge(edge eOrig) {
        OGDF_ASSERT(eOrig != 0 && eOrig->graphOf() == m_pGraph);
        edge e = Graph::newEdge(m_vCopy[eOrig->source()], m_vCopy[eOrig->target()]);
        m_eCopy[m_eOrig[e] = eOrig] = e;
        return e;
    }

private:
    void initGC(const GraphCopySimple &GC, NodeArray<node> &vCopy,
        EdgeArray<edge> &eCopy);
}; // class GraphCopySimple


//---------------------------------------------------------
// GraphCopy
// graph copies (support for edge splitting)
//---------------------------------------------------------
class OGDF_EXPORT GraphCopy : public Graph {
protected:

    const Graph *m_pGraph;   
    NodeArray<node> m_vOrig; 
    EdgeArray<edge> m_eOrig; 
    EdgeArray<ListIterator<edge> > m_eIterator; 

    NodeArray<node> m_vCopy; 
    EdgeArray<List<edge> > m_eCopy; 

public:

    GraphCopy(const Graph &G);

    GraphCopy() : Graph() { }


    GraphCopy(const GraphCopy &GC);

    virtual ~GraphCopy() {};



    const Graph &original() const { return *m_pGraph; }

    node original(node v) const { return m_vOrig[v]; }

    edge original(edge e) const { return m_eOrig[e]; }

    node copy(node v) const { return m_vCopy[v]; }

    const List<edge> &chain(edge e) const { return m_eCopy[e]; }

    // returns first edge in chain(e)
    edge copy(edge e) const { return m_eCopy[e].front(); }

    bool isDummy(node v) const { return (m_vOrig[v] == 0); }

    bool isDummy(edge e) const { return (m_eOrig[e] == 0); }

    bool isReversed (edge e) const {
        return e->source() != original(copy(e)->source());
    }

    

    node newNode() {
        return Graph::newNode();
    }

    node newNode(node vOrig) {
        OGDF_ASSERT(vOrig != 0 && vOrig->graphOf() == m_pGraph);
        node v = Graph::newNode();
        m_vCopy[m_vOrig[v] = vOrig] = v;
        return v;
    }

    void delCopy(node v);

    void delCopy(edge e);


    virtual edge split(edge e);


    void unsplit(edge eIn, edge eOut);

    edge newEdge(edge eOrig);


    edge newEdge(edge eOrig, adjEntry adjSrc, node w);


    edge newEdge(edge eOrig, node v, adjEntry adjTgt);

    edge newEdge(node v, node w)                   { return Graph::newEdge(v, w); }
    edge newEdge(adjEntry adjSrc, adjEntry adjTgt) { return Graph::newEdge(adjSrc, adjTgt); }
    edge newEdge(node v, adjEntry adjTgt)          { return Graph::newEdge(v, adjTgt); }
    edge newEdge(adjEntry adjSrc, node w)          { return Graph::newEdge(adjSrc, w); }


    void setEdge(edge eOrig, edge eCopy);
    

    void insertEdgePath(edge eOrig, const SList<adjEntry> &crossedEdges);

    //for FixedEmbeddingUpwardEdgeInserter only
    void insertEdgePath(node srcOrig, node tgtOrig, const SList<adjEntry> &crossedEdges);
    


    void removeEdgePath(edge eOrig);


    edge insertCrossing(edge& crossingEdge,
                        edge crossedEdge,
                        bool topDown);




    edge newEdge(node v, adjEntry adj, edge eOrig, CombinatorialEmbedding &E);

    void setOriginalEmbedding();


    void insertEdgePathEmbedded(
        edge eOrig,
        CombinatorialEmbedding &E,
        const SList<adjEntry> &crossedEdges);
    
    void removeEdgePathEmbedded(
        CombinatorialEmbedding &E,
        edge                    eOrig,
        FaceSetPure            &newFaces);




    bool consistencyCheck() const;


    void createEmpty(const Graph &G);


    void initByNodes(const List<node> &nodes, EdgeArray<edge> &eCopy);


    void initByActiveNodes(const List<node> &nodes, 
        const NodeArray<bool> &activeNodes, EdgeArray<edge> &eCopy);




    GraphCopy &operator=(const GraphCopy &GC);



private:
    void initGC(const GraphCopy &GC,
        NodeArray<node> &vCopy, EdgeArray<edge> &eCopy);

}; // class GraphCopy


} // end namespace ogdf

#endif