VariableEmbeddingInserter2.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_2_H
#define OGDF_VARIABLE_EMBEDDING_INSERTER_2_H


#include <ogdf/module/EdgeInsertionModule.h>


namespace ogdf {

class OGDF_EXPORT BCandSPQRtrees;
class OGDF_EXPORT ExpandedGraph2;


//---------------------------------------------------------
// VariableEmbeddingInserter2
// edge insertion module that inserts each edge optimally
// into a given embedding.
//---------------------------------------------------------
class OGDF_EXPORT VariableEmbeddingInserter2 : public EdgeInsertionModule
{
public:
    // construction
    VariableEmbeddingInserter2();
    // destruction
    virtual ~VariableEmbeddingInserter2() { }

    //
    // options
    //

    // sets remove-reinsert option (postprocessing)
    // possible values: (see EdgeInsertionModule)
    //    rrNone, rrInserted, rrMostCrossed, rrAll
    void removeReinsert(RemoveReinsertType rrOption) {
        m_rrOption = rrOption;
    }

    // returns remove-reinsert option
    RemoveReinsertType removeReinsert() const {
        return m_rrOption;
    }


    // sets the portion of most crossed edges used if remove-reinsert option
    // is set to rrMostCrossed
    // this portion no. of edges * percentMostCrossed() / 100
    void percentMostCrossed(double percent) {
        m_percentMostCrossed = percent;
    }

    // returns option percentMostCrossed
    double percentMostCrossed() const {
        return m_percentMostCrossed;
    }


    // returns the number of runs performed by the postprocessing
    // after algoithm has been called
    int runsPostprocessing() const {
        return m_runsPostprocessing;
    }

private:
    // performs actual call
    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 is 0 all costs are 1
        const EdgeArray<bool> *forbiddenEdgeOrig); // pointer to array deciding
                        // which original edges are forbidden to cross; if pointer
                        // is 0 no edges are explicitly forbidden to cross

    edge crossedEdge(adjEntry adj) const;
    int costCrossed(edge eOrig) const;

    bool                   m_forbidCrossingGens;
    const EdgeArray<int>  *m_costOrig;
    const EdgeArray<bool> *m_forbiddenEdgeOrig;
    Graph::EdgeType        m_typeOfCurrentEdge;

    void insert(edge eOrig, SList<adjEntry> &eip);
    void blockInsert(node s, node t, List<adjEntry> &L);

    PlanRep *m_pPG;

    BCandSPQRtrees *m_pBC;

    void buildSubpath(node v,
        node vPred,
        node vSucc,
        List<adjEntry> &L,
        ExpandedGraph2 &Exp,
        node s,
        node t);
    edge insertEdge(node v, node w, Graph &Exp,
        NodeArray<node> &GtoExp, List<node> &nodesG);


    // options
    RemoveReinsertType m_rrOption;
    double m_percentMostCrossed;

    // results
    int m_runsPostprocessing;

}; // class VariableEmbeddingInserter2


} // end namespace ogdf


#endif