BoyerMyrvoldPlanar.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_BOYER_MYRVOLD_PLANAR_H
#define OGDF_BOYER_MYRVOLD_PLANAR_H

#include <ogdf/basic/Graph_d.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/Stack.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>


namespace ogdf {

enum enumDirection {
    CCW=0,
    CW=1
};


enum enumEdgeType {
    EDGE_UNDEFINED=0,
    EDGE_SELFLOOP=1,
    EDGE_BACK=2,
    EDGE_DFS=3,
    EDGE_DFS_PARALLEL=4,
    EDGE_BACK_DELETED=5
};

class KuratowskiStructure;
class FindKuratowskis;

class BoyerMyrvoldPlanar
{
    friend class BoyerMyrvold;
    friend class BoyerMyrvoldInit;
    friend class FindKuratowskis;
    friend class ExtractKuratowskis;
        
public:
    BoyerMyrvoldPlanar(
        Graph& g,
        bool bundles,
        int m_embeddingGrade,
        bool limitStructures,
        SListPure<KuratowskiStructure>& output,
        bool randomDFSTree,
        bool avoidE2Minors);

    ~BoyerMyrvoldPlanar() { };
    
    bool start();
    
    enum enumEmbeddingGrade {
        doNotEmbed=-3, // and not find any kuratowski subdivisions
        doNotFind=-2, // but embed
        doFindUnlimited=-1, // and embed
        doFindZero=0 // and embed
    };
    

    void flipBicomp(
        int c,
        int marker,
        NodeArray<int>& visited,
        bool wholeGraph,
        bool deleteFlipFlags);
    
    // avoid automatic creation of assignment operator
    BoyerMyrvoldPlanar &operator=(const BoyerMyrvoldPlanar &);

protected:
    /***** Methods for Walkup and Walkdown ******/
    
    inline bool pertinent(node w) {
        OGDF_ASSERT(w!=NULL);
        if (m_dfi[w] <= 0) return false;
        return (!m_backedgeFlags[w].empty() || !m_pertinentRoots[w].empty());
    }
    
    inline bool internallyActive(node w, int v) {
        OGDF_ASSERT(w!=NULL);
        if (m_dfi[w] <= 0) return false;
        return (pertinent(w) && !externallyActive(w,v));
    }
    
    inline bool externallyActive(node w, int v) {
        OGDF_ASSERT(w!=NULL);
        if (m_dfi[w] <= 0) return false;
        if (m_leastAncestor[w] < v) return true;
        if (m_separatedDFSChildList[w].empty()) return false;
        return (m_lowPoint[m_separatedDFSChildList[w].front()] < v);
    }
    
    inline bool inactive(node w, int v) {
        OGDF_ASSERT(w!=NULL);
        if (m_dfi[w] <= 0) return true;
        if (!m_backedgeFlags[w].empty() || !m_pertinentRoots[w].empty()
            || m_leastAncestor[w] < v) return false;
        if (m_separatedDFSChildList[w].empty()) return true;
        return (m_lowPoint[m_separatedDFSChildList[w].front()] >= v);
    }
    

    inline int infoAboutNode(node w, int v) {
        OGDF_ASSERT(w!=NULL);
        if (m_dfi[w] <= 0) return 0;
        if (!m_pertinentRoots[w].empty() || !m_backedgeFlags[w].empty()) {
            // pertinent
            if (m_leastAncestor[w] < v) return 2;
            if (m_separatedDFSChildList[w].empty()) return 1;
            return (m_lowPoint[m_separatedDFSChildList[w].front()] < v
                    ? 2 : 1);
        } else {
            // not pertinent
            if (m_leastAncestor[w] < v) return 3;
            if (m_separatedDFSChildList[w].empty()) return 0;
            return (m_lowPoint[m_separatedDFSChildList[w].front()] < v
                    ? 3 : 0);
        }
    }
    

    inline node successorOnExternalFace(node w, int& direction) {
        OGDF_ASSERT(w!=NULL);
        OGDF_ASSERT(w->degree()>0);
        OGDF_ASSERT(m_link[CW][w]!=NULL && m_link[CCW][w]!=NULL);
        adjEntry adj = m_link[direction][w];
        OGDF_ASSERT(adj->theNode()!=NULL);
        
        if (w->degree() > 1) direction =
                adj==beforeShortCircuitEdge(adj->theNode(),CCW)->twin();
        OGDF_ASSERT(direction || adj==beforeShortCircuitEdge(adj->theNode(),CW)->twin());
        return adj->theNode();
    }
    
    inline node successorWithoutShortCircuit(node w, int& direction) {
        OGDF_ASSERT(w!=NULL);
        OGDF_ASSERT(w->degree()>0);
        OGDF_ASSERT(m_link[CW][w]!=NULL && m_link[CCW][w]!=NULL);
        adjEntry adj = beforeShortCircuitEdge(w,direction);
        OGDF_ASSERT(adj->theNode()!=NULL);
        
        if (w->degree() > 1) direction =
                adj==beforeShortCircuitEdge(adj->theNode(),CCW)->twin();
        OGDF_ASSERT(direction || adj==beforeShortCircuitEdge(adj->theNode(),CW)->twin());
        return adj->theNode();
    }
    

    inline node constSuccessorOnExternalFace(node v, int direction) {
        OGDF_ASSERT(v!=NULL);
        OGDF_ASSERT(v->degree()>0);
        return m_link[direction][v]->theNode();
    }
    

    inline node constSuccessorWithoutShortCircuit(node v, int direction) {
        OGDF_ASSERT(v!=NULL);
        OGDF_ASSERT(v->degree()>0);
        return beforeShortCircuitEdge(v,direction)->theNode();
    }
    

    inline adjEntry beforeShortCircuitEdge(node v, int direction) {
        OGDF_ASSERT(v!=NULL);
        return (m_beforeSCE[direction][v]==NULL) ? m_link[direction][v] : m_beforeSCE[direction][v];
    }
    

    node activeSuccessor(node w, int& direction, int v, int& info);
    

    inline node constActiveSuccessor(node w, int direction, int v, int& info) {
        return activeSuccessor(w,direction,v,info);
    }
    

    inline bool wNodesExist(node root, node stopx, node stopy) {
        OGDF_ASSERT(root != stopx && root != stopy && stopx != stopy);
        int dir = CCW;
        bool between = false;
        while (root != NULL) {
            root = successorOnExternalFace(root,dir);
            if (between && pertinent(root)) {
                return true;
            }
            if (root == stopx || root == stopy) {
                if (between) {
                    return false;
                }
                between = true;
            }
        }
        return false;
    }
    
    inline void printNodeInfo(node v) {
        cout << "\nprintNodeInfo(" << m_dfi[v] << "): ";
        cout << "CCW=" << m_dfi[constSuccessorOnExternalFace(v,CCW)];
        cout << ",CW=" << m_dfi[constSuccessorOnExternalFace(v,CW)];
        cout << "\tCCWBefore=" << m_dfi[constSuccessorWithoutShortCircuit(v,CCW)];
        cout << ",CWBefore=" << m_dfi[constSuccessorWithoutShortCircuit(v,CW)];
        cout << "\tadjList: ";
        adjEntry adj;
        for (adj = v->firstAdj(); adj; adj = adj->succ()) {
            cout << adj->twinNode() << " ";
        }
    }
    

    void mergeBiconnectedComponent(StackPure<int>& stack, const int j);
    

    void mergeBiconnectedComponentOnlyPlanar(StackPure<int>& stack, const int j);
    

    void embedBackedges(const node v, const int v_dir,
                        const node w, const int w_dir, const int i);
    

    void embedBackedgesOnlyPlanar(const node v, const int v_dir,
                                const node w, const int w_dir, const int i);
    
    void createShortCircuitEdge(const node v, const int v_dir,
                                const node w, const int w_dir);
    

    node walkup(const node v, const node w, const int marker, const edge back);
    

    int walkdown(const int i, const node v, FindKuratowskis* findKuratowskis);
    
    void mergeUnprocessedNodes();
    

    void postProcessEmbedding();
    

    bool embed();
    
    
    /***** Members ******/
    Graph& m_g;
    
    const bool m_bundles;
    const int m_embeddingGrade;
    const bool m_limitStructures;
    const bool m_randomDFSTree;
    const bool m_avoidE2Minors;
    
    int m_flippedNodes;
    
    /***** Members from Boyer Myrvold-Init ******/

    NodeArray<node> m_realVertex;
    
    NodeArray<int> m_dfi;
    
    Array<node> m_nodeFromDFI;
    

    NodeArray<adjEntry> m_link[2];
    

    NodeArray<adjEntry> m_beforeSCE[2];
    
    NodeArray<adjEntry> m_adjParent;
    

    NodeArray<int> m_leastAncestor;
    

    EdgeArray<int> m_edgeType;
    
    NodeArray<int> m_lowPoint;
    
    NodeArray<int> m_highestSubtreeDFI;
    

    NodeArray<ListPure<node> > m_separatedDFSChildList;
    

    NodeArray<ListIterator<node> > m_pNodeInParent;
    
    /***** Members for Walkup and Walkdown ******/
    NodeArray<int> m_visited;
    
    EdgeArray<node> m_pointsToRoot;
    

    NodeArray<int> m_visitedWithBackedge;
    

    NodeArray<bool> m_flipped;
    

    NodeArray<SListPure<adjEntry> > m_backedgeFlags;
    
    NodeArray<SListPure<node> > m_pertinentRoots;
    
    SListPure<KuratowskiStructure>& m_output;
};


}

#endif