PlanRepExpansion.h

Go to the documentation of this file.

/*
 * $Revision: 2027 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2010-09-01 11:55:17 +0200 (Wed, 01 Sep 2010) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_PLAN_REP_EXPANSION_H
#define OGDF_PLAN_REP_EXPANSION_H


#include <ogdf/basic/Graph.h>
#include <ogdf/basic/tuples.h>
#include <ogdf/basic/SList.h>


namespace ogdf {


class OGDF_EXPORT CombinatorialEmbedding;
class OGDF_EXPORT FaceSetPure;
class OGDF_EXPORT NodeSetPure;


class OGDF_EXPORT PlanRepExpansion : public Graph
{
public:
    struct Crossing {
        Crossing() { m_adj = 0; }
        Crossing(adjEntry adj) { m_adj = adj; }

        adjEntry m_adj;
        SList<adjEntry> m_partitionLeft;
        SList<adjEntry> m_partitionRight;

        friend ostream &operator<<(ostream &os, const Crossing &c) {
            os << "(" << c.m_adj << ")";
            return os;
        }
    };


    class NodeSplit
    {
    public:
        NodeSplit() { }

        NodeSplit(ListIterator<NodeSplit> it) : m_nsIterator(it) { }

        node source() const { return m_path.front()->source(); }

        node target() const { return m_path.back ()->target(); }

        List<edge> m_path; 
        ListIterator<NodeSplit> m_nsIterator; 
    };

    typedef PlanRepExpansion::NodeSplit *nodeSplit;


    PlanRepExpansion(const Graph& G);

    PlanRepExpansion(const Graph& G, const List<node> &splittableNodes);

    ~PlanRepExpansion() {}



    const Graph &original() const { return *m_pGraph; }

    node original(node v) const { return m_vOrig[v]; }

    const List<node> &expansion(node vOrig) const { return m_vCopy[vOrig]; }

    node copy(node vOrig) const { return m_vCopy[vOrig].front(); }

    edge originalEdge(edge e) const { return m_eOrig[e]; }

    const List<edge> &chain(edge eOrig) const { return m_eCopy[eOrig]; }

    edge copy(edge eOrig) const { return m_eCopy[eOrig].front(); }

    bool splittable(node v) const { return m_splittable[v]; }

    bool splittableOrig(node vOrig) const { return m_splittableOrig[vOrig]; }

    NodeSplit *nodeSplitOf(edge e) const { return m_eNodeSplit[e]; }

    int numberOfNodeSplits() const { return m_nodeSplits.size(); }
    int numberOfSplittedNodes() const;

    List<NodeSplit> &nodeSplits() { return m_nodeSplits; }

    List<edge> &setOrigs(edge e, edge &eOrig, nodeSplit &ns);

    ListConstIterator<edge> position(edge e) const { return m_eIterator[e]; }

    bool isPseudoCrossing(node v) const;

    int computeNumberOfCrossings() const;




    int numberOfCCs() const {
        return m_nodesInCC.size();
    }

    int currentCC() const {
        return m_currentCC;
    }

    const List<node> &nodesInCC(int i) const {
        return m_nodesInCC[i];
    }

    const List<node> &nodesInCC() const {
        return m_nodesInCC[m_currentCC];
    }

    void initCC(int i);




    edge split(edge e);

    void unsplit(edge eIn, edge eOut);

    void delCopy(edge e);

    bool embed();

    void insertEdgePath(
        edge eOrig,
        nodeSplit ns,
        node vStart,
        node vEnd,
        List<Crossing> &eip,
        edge eSrc,
        edge eTgt);

    void insertEdgePathEmbedded(
        edge eOrig,
        nodeSplit ns,
        CombinatorialEmbedding &E,
        const List<Tuple2<adjEntry,adjEntry> > &crossedEdges);

    void removeEdgePathEmbedded(
        CombinatorialEmbedding &E,
        edge eOrig,
        nodeSplit ns,
        FaceSetPure &newFaces,
        NodeSetPure &mergedNodes,
        node &oldSrc,
        node &oldTgt);

    void removeEdgePath(
        edge eOrig,
        nodeSplit ns,
        node &oldSrc,
        node &oldTgt);

    void contractSplit(nodeSplit ns, CombinatorialEmbedding &E);

    void contractSplit(nodeSplit ns);

    edge unsplitExpandNode(
        node u,
        edge eContract,
        edge eExpand,
        CombinatorialEmbedding &E);

    edge unsplitExpandNode(
        node u,
        edge eContract,
        edge eExpand);

    edge enlargeSplit(node v, edge e, CombinatorialEmbedding &E);

    edge enlargeSplit(node v, edge e);

    edge splitNodeSplit(edge e, CombinatorialEmbedding &E);

    edge splitNodeSplit(edge e);

    void removeSelfLoop(edge e, CombinatorialEmbedding &E);

    void removeSelfLoop(edge e);

    PlanRepExpansion::nodeSplit convertDummy(
        node u,
        node vOrig,
        PlanRepExpansion::nodeSplit ns);

    edge separateDummy(
        adjEntry adj_1,
        adjEntry adj_2, 
        node vStraight, 
        bool isSrc);

    void resolvePseudoCrossing(node v);



    bool consistencyCheck() const;


private:
    void doInit(const Graph &G, const List<node> &splittableNodes);
    void prepareNodeSplit(
        const SList<adjEntry> &partitionLeft,
        adjEntry &adjLeft,
        adjEntry &adjRight);

    const Graph *m_pGraph;                      
    NodeArray<node> m_vOrig;                    
    EdgeArray<edge> m_eOrig;                    
    EdgeArray<ListIterator<edge> > m_eIterator; 
    EdgeArray<List<edge> > m_eCopy;             
    NodeArray<ListIterator<node> > m_vIterator; 
    NodeArray<List<node> > m_vCopy;             

    NodeArray<bool> m_splittable;
    NodeArray<bool> m_splittableOrig;
    EdgeArray<NodeSplit *> m_eNodeSplit;
    List<NodeSplit> m_nodeSplits;

    int m_currentCC; 
    int m_numCC;     

    Array<List<node> >  m_nodesInCC; 
    EdgeArray<edge>     m_eAuxCopy; // auxiliary
};


} // end namespace ogdf


#endif