MMVariableEmbeddingInserter.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_VARIABLE_EMBEDDING_INSERTER_H
#define OGDF_MM_VARIABLE_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 NodeSet;
class OGDF_EXPORT StaticPlanarSPQRTree;


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

    // destruction
    virtual ~MMVariableEmbeddingInserter() { }


    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:
    class Block;
    class ExpandedSkeleton;

    typedef PlanRepExpansion::Crossing Crossing;

    struct AnchorNodeInfo {
        AnchorNodeInfo() { m_adj_1 = m_adj_2 = 0; }
        AnchorNodeInfo(adjEntry adj) {
            m_adj_1 = adj;
            m_adj_2 = 0;
        }
        AnchorNodeInfo(adjEntry adj_1, adjEntry adj_2) {
            m_adj_1 = adj_1;
            m_adj_2 = adj_2;
        }

        adjEntry m_adj_1;
        adjEntry m_adj_2;
    };

    enum PathType { pathToEdge = 0, pathToSource = 1, pathToTarget = 2 };

    struct Paths {
        Paths() :
            m_addPartLeft(3), m_addPartRight(3),
            m_paths(3),
            m_src(0,2,0), m_tgt(0,2,0),
            m_pred(0,2,0)
        { }

        Array<SList<adjEntry> > m_addPartLeft;
        Array<SList<adjEntry> > m_addPartRight;
        Array<List<Crossing> >  m_paths;
        Array<AnchorNodeInfo>   m_src;
        Array<AnchorNodeInfo>   m_tgt;
        Array<int>              m_pred;
    };

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

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

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

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

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

    void insert(List<Crossing> &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd);

    node prepareAnchorNode(
        const AnchorNodeInfo &anchor,
        node vOrig,
        bool isSrc,
        edge &eExtra);

    void preprocessInsertionPath(
        const AnchorNodeInfo &srcInfo,
        const AnchorNodeInfo &tgtInfo,
        node srcOrig,
        node tgtOrig,
        node &src,
        node &tgt,
        edge &eSrc,
        edge &eTgt);

    node preparePath(
        node vAnchor, 
        adjEntry adjPath, 
        bool bOrigEdge,
        node vOrig);

    void findPseudos(
        node vDummy,
        adjEntry adjSrc, 
        AnchorNodeInfo &infoSrc, 
        SListPure<node> &pseudos);

    void insertWithCommonDummy(
        edge eOrig, 
        node vDummy, 
        node &src, 
        node &tgt);

    bool dfsVertex(node v,
        int parent,
        List<Crossing> &eip, 
        AnchorNodeInfo &vStart,
        AnchorNodeInfo &vEnd);

    bool dfsBlock(int i,
        node parent,
        node &repS,
        List<Crossing> &eip,
        AnchorNodeInfo &vStart,
        AnchorNodeInfo &vEnd);

    bool pathSearch(node v, edge parent, const Block &BC, List<edge> &path);

    void blockInsert(
        Block &BC,
        List<Crossing> &L,
        AnchorNodeInfo &srcInfo,
        AnchorNodeInfo &tgtInfo);

    void buildSubpath(
        node v,
        edge eIn,
        edge eOut,
        Paths &paths,
        bool &bPathToEdge,
        bool &bPathToSrc,
        bool &bPathToTgt,
        ExpandedSkeleton &Exp);

    void contractSplitIfReq(node u);
    void convertDummy(
        node u,
        node vOrig,
        PlanRepExpansion::nodeSplit ns_0);

    void writeEip(const List<Crossing> &eip);

    RemoveReinsertType m_rrOption; 
    double m_percentMostCrossed;   

    PlanRepExpansion *m_pPG; 

    NodeSet *m_pSources; 
    NodeSet *m_pTargets; 

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

    bool m_conFinished; 
    const EdgeArray<bool> *m_forbiddenEdgeOrig;
};

} // end namespace ogdf

#endif