VariableEmbeddingInserter.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_VARIABLE_EMBEDDING_INSERTER_H
#define OGDF_VARIABLE_EMBEDDING_INSERTER_H


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


namespace ogdf {

class OGDF_EXPORT PlanarSPQRTree;
class OGDF_EXPORT ExpandedGraph;
class OGDF_EXPORT PlaneGraphCopy;


class OGDF_EXPORT BiconnectedComponent;



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

    ~VariableEmbeddingInserter() { }

    ReturnType callPostprocessing(PlanRep &PG, const List<edge> &origEdges) {
        return doCallPostprocessing(PG, origEdges, false, 0, 0, 0);
    }



    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;
    }


    int runsPostprocessing() const {
        return m_runsPostprocessing;
    }


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

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

    edge crossedEdge(adjEntry adj) const;
    int costCrossed(edge eOrig) const;
        
    bool                   m_forbidCrossingGens;
    const EdgeArray<int>  *m_costOrig;
    const EdgeArray<bool> *m_forbiddenEdgeOrig;
    const EdgeArray<unsigned int>  *m_edgeSubgraph;
    Graph::EdgeType        m_typeOfCurrentEdge;

    void insert(node s, node t, SList<adjEntry> &eip);
    void blockInsert(const BiconnectedComponent &G,
        node s,
        node t,
        List<adjEntry> &L);

    bool dfsVertex(node v, int parent);
    bool dfsComp(int i, node parent, node &repT);

    PlanRep *m_pPG;
    node   m_s, m_t;
    edge   m_st;
    SList<adjEntry> *m_pEip;

    static int m_bigM;  // used for SimDraw

    NodeArray<SList<int> > m_compV;
    Array<SList<node> >    m_nodeB;
    Array<SList<edge> >    m_edgeB;
    NodeArray<node>        m_GtoBC;

    bool pathSearch(node v, edge parent, List<edge> &path);
    void buildSubpath(node v,
        edge eIn,
        edge eOut,
        List<adjEntry> &L,
        ExpandedGraph &Exp,
        node s,
        node t);
    edge insertEdge(node v, node w, Graph &Exp,
        NodeArray<node> &GtoExp, List<node> &nodesG);

    node m_v1, m_v2;

    RemoveReinsertType m_rrOption; 
    double m_percentMostCrossed;   

    int m_runsPostprocessing; 
};

} // end namespace ogdf

#endif