FixedEmbeddingInserter.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_FIXED_EMBEDDING_INSERTER_H
#define OGDF_FIXED_EMBEDDING_INSERTER_H



#include <ogdf/module/EdgeInsertionModule.h>
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/FaceArray.h>


template <class E> class FaceArray;


namespace ogdf {


class OGDF_EXPORT FaceSetSimple;


class OGDF_EXPORT FixedEmbeddingInserter : public EdgeInsertionModule
{
public:
    FixedEmbeddingInserter();

    ~FixedEmbeddingInserter() { }


    void removeReinsert(RemoveReinsertType rrOption) {
        m_rrOption = rrOption;
    }

    RemoveReinsertType removeReinsert() const {
        return m_rrOption;
    }



    void percentMostCrossed(double percent) {
        m_percentMostCrossed = percent;
    }

    double percentMostCrossed() const {
        return m_percentMostCrossed;
    }


    void keepEmbedding(bool keep) {
        m_keepEmbedding = keep;
    }

    bool keepEmbeding() const {
        return m_keepEmbedding;
    }
    

    int runsPostprocessing() const {
        return m_runsPostprocessing;
    }


private:
    ReturnType doCall(
        PlanRep &PG,                  // planarized representation
        const List<edge> &origEdges,     // original edge to be inserted
        bool forbidCrossinGens,          // frobid crossings between gen's
        const EdgeArray<int> *costOrig,  // pointer to array of cost of
                // original edges; if pointer is 0 all costs are 1
        const EdgeArray<bool> *forbiddenEdgeOrig = 0,
        const EdgeArray<unsigned int> *edgeSubGraph = 0); // pointer to array deciding
                // which original edges are forbidden to cross; if pointer is
                // is 0 no edges are explicitly forbidden to cross


    void constructDualForbidCrossingGens(const PlanRepUML &PG,
        const CombinatorialEmbedding &E);


    void constructDual(const GraphCopy &GC,
        const CombinatorialEmbedding &E,
        const EdgeArray<bool> *forbiddenEdgeOrig);


    void findShortestPath(const CombinatorialEmbedding &E,
        node s,
        node t,
        Graph::EdgeType eType,
        SList<adjEntry> &crossed);


    void findShortestPath(
        const PlanRep &PG,
        const CombinatorialEmbedding &E,
        const EdgeArray<int> &costOrig,
        node s,
        node t,
        Graph::EdgeType eType,
        SList<adjEntry> &crossed,
        const EdgeArray<unsigned int> *edgeSubGraph,
        int eSubGraph);

    void insertEdge(PlanRep &PG,
        CombinatorialEmbedding &E,
        edge eOrig,
        const SList<adjEntry> &crossed,
        bool forbidCrossingGens,
        const EdgeArray<bool> *forbiddenEdgeOrig);

    void removeEdge(
        PlanRep &PG,
        CombinatorialEmbedding &E,
        edge eOrig,
        bool forbidCrossingGens,
        const EdgeArray<bool> *forbiddenEdgeOrig);

    edge crossedEdge(adjEntry adj) const;
    int costCrossed(edge eOrig,
        const PlanRep &PG,
        const EdgeArray<int> &costOrig,
        const EdgeArray<unsigned int> *subgraphs) const;

    Graph m_dual;   

    EdgeArray<adjEntry> m_primalAdj;   
    FaceArray<node>     m_nodeOf;      
    EdgeArray<bool>     m_primalIsGen; 
    FaceSetSimple       *m_delFaces;
    FaceSetPure         *m_newFaces;

    node m_vS; 
    node m_vT; 


    RemoveReinsertType m_rrOption; 
    double m_percentMostCrossed;   
    bool m_keepEmbedding;

    int m_runsPostprocessing; 
};

} // end namespace ogdf

#endif