MMFixedEmbeddingInserter.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_MM_FIXED_EMBEDDING_INSERTER_H
#define OGDF_MM_FIXED_EMBEDDING_INSERTER_H



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



namespace ogdf {


class OGDF_EXPORT FaceSetSimple;
class OGDF_EXPORT NodeSetPure;
class OGDF_EXPORT NodeSet;


class OGDF_EXPORT MMFixedEmbeddingInserter : public MMEdgeInsertionModule
{
public:
    MMFixedEmbeddingInserter();

    // destruction
    virtual ~MMFixedEmbeddingInserter() { }


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


private:
    ReturnType doCall(
        PlanRepExpansion &PG,
        const List<edge> &origEdges,
        const EdgeArray<bool> *forbiddenEdgeOrig);


    void constructDual(
        const PlanRepExpansion &PG,
        const CombinatorialEmbedding &E);


    void findShortestPath(
        const PlanRepExpansion &PG,
        const CombinatorialEmbedding &E,
        const List<node> &sources,
        const List<node> &targets,
        List<Tuple2<adjEntry,adjEntry> > &crossed,
        const EdgeArray<bool> *forbiddenEdgeOrig);

    void prepareAnchorNode(
        PlanRepExpansion &PG,
        CombinatorialEmbedding &E,
        adjEntry &adjStart,
        node srcOrig);

    void preprocessInsertionPath(
        PlanRepExpansion &PG,
        CombinatorialEmbedding &E,
        node srcOrig,
        node tgtOrig,
        //PlanRepExpansion::nodeSplit ns,
        List<Tuple2<adjEntry,adjEntry> > &crossed);

    void insertEdge(
        PlanRepExpansion &PG,
        CombinatorialEmbedding &E,
        edge eOrig,
        node srcOrig,
        node tgtOrig,
        PlanRepExpansion::NodeSplit *nodeSplit,
        List<Tuple2<adjEntry,adjEntry> > &crossed);

    void removeEdge(
        PlanRepExpansion &PG,
        CombinatorialEmbedding &E,
        edge eOrig,
        PlanRepExpansion::NodeSplit *nodeSplit,
        node &oldSrc,
        node &oldTgt);

    void insertDualEdge(node vDual, adjEntry adj, const CombinatorialEmbedding &E);

    void insertDualEdges(node v, const CombinatorialEmbedding &E);

    void contractSplit(
        PlanRepExpansion &PG,
        CombinatorialEmbedding &E,
        PlanRepExpansion::NodeSplit *nodeSplit);

    void contractSplitIfReq(
        PlanRepExpansion &PG,
        CombinatorialEmbedding &E,
        node u,
        const PlanRepExpansion::nodeSplit nsCurrent = 0);

    void convertDummy(
        PlanRepExpansion &PG,
        CombinatorialEmbedding &E,
        node u,
        node vOrig,
        PlanRepExpansion::nodeSplit ns);

    void collectAnchorNodes(
        node v, 
        NodeSet &nodes, 
        const PlanRepExpansion::NodeSplit *nsParent,
        const PlanRepExpansion &PG) const;

    void anchorNodes(
        node vOrig,
        NodeSet &nodes,
        const PlanRepExpansion &PG) const;

    void findSourcesAndTargets(
        node src, node tgt,
        NodeSet &sources,
        NodeSet &targets,
        const PlanRepExpansion &PG) const;

    node commonDummy(
        NodeSet &sources,
        NodeSet &targets);

    bool checkDualGraph(PlanRepExpansion &PG, const CombinatorialEmbedding &E) const;

    bool checkSplitDeg(
        PlanRepExpansion &PG);

    bool origOfDualForbidden(
        edge e, 
        const PlanRepExpansion &PG, 
        const EdgeArray<bool> *forbiddenEdgeOrig) const
    {
        if(forbiddenEdgeOrig == 0)
            return false;

        if(e->source() == m_vS || e->target() == m_vT)
            return false;

        if(m_primalNode[e->source()] != 0)
            return false;
        if(m_primalNode[e->target()] != 0)
            return false;

        adjEntry adj = m_primalAdj[e];
        if(adj == 0) return false;
        
        edge eOrig = PG.originalEdge(adj->theEdge());
        if(eOrig != 0) {
            //if((*forbiddenEdgeOrig)[eOrig] == true)
            //  cout << "forbidden: " << eOrig << ", dual: " << e << endl;
            return (*forbiddenEdgeOrig)[eOrig];
        } else return false;
    }

    void drawDual(
        const PlanRepExpansion &PG,
        const EdgeArray<bool> *forbiddenEdgeOrig);

    RemoveReinsertType m_rrOption; 
    double m_percentMostCrossed;   

    Graph m_dual;                      
    FaceArray<node>     m_dualOfFace;  
    NodeArray<node>     m_dualOfNode;  
    NodeArray<node>     m_primalNode;  
    EdgeArray<adjEntry> m_primalAdj;   
    AdjEntryArray<edge> m_dualEdge;    
    EdgeArray<int>      m_dualCost;    

    node m_vS; 
    node m_vT; 
    int m_maxCost; 

    FaceSetSimple      *m_delFaces;
    FaceSetPure        *m_newFaces;
    NodeSetPure        *m_mergedNodes;
};

} // end namespace ogdf

#endif