BoyerMyrvoldPlanar.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
 
#include <iostream>
#include <random>
 
namespace ogdf {
template<class E, class INDEX>
class ArrayBuffer;
 
enum class BoyerMyrvoldEdgeType {
    Undefined = 0, 
    Selfloop = 1, 
    Back = 2, 
    Dfs = 3, 
    DfsParallel = 4, 
    BackDeleted = 5 
};
 
class FindKuratowskis;
class KuratowskiStructure;
 
namespace boyer_myrvold {
class BoyerMyrvoldInit;
}
 
class BoyerMyrvoldPlanar {
    friend class BoyerMyrvold;
    friend class boyer_myrvold::BoyerMyrvoldInit;
    friend class FindKuratowskis;
    friend class ExtractKuratowskis;
 
public:
    const static int DirectionCCW;
 
    const static int DirectionCW;
 
    enum class EmbeddingGrade {
        doNotEmbed = -3, // and not find any kuratowski subdivisions
        doNotFind = -2, // but embed
        doFindUnlimited = -1, // and embed
        doFindZero = 0 // and embed
    };
 
    BoyerMyrvoldPlanar(Graph& g, bool bundles, int embeddingGrade, bool limitStructures,
            SListPure<KuratowskiStructure>& output, double randomness, bool avoidE2Minors,
            bool extractSubgraph, const EdgeArray<int>* edgeCosts = nullptr);
 
    BoyerMyrvoldPlanar(Graph& g, bool bundles, EmbeddingGrade embeddingGrade, bool limitStructures,
            SListPure<KuratowskiStructure>& output, double randomness, bool avoidE2Minors,
            bool extractSubgraph, const EdgeArray<int>* edgeCosts = nullptr)
        : BoyerMyrvoldPlanar(g, bundles, static_cast<int>(embeddingGrade), limitStructures, output,
                randomness, avoidE2Minors, extractSubgraph, edgeCosts) { }
 
    bool start();
 
 
    void flipBicomp(int c, int marker, NodeArray<int>& visited, bool wholeGraph,
            bool deleteFlipFlags);
 
    // avoid automatic creation of assignment operator
    BoyerMyrvoldPlanar& operator=(const BoyerMyrvoldPlanar&);
 
    void seed(const std::minstd_rand rand) { m_rand = rand; }
 
protected:
 
    inline bool pertinent(node w) const {
        OGDF_ASSERT(w != nullptr);
        return m_dfi[w] > 0 && (!m_backedgeFlags[w].empty() || !m_pertinentRoots[w].empty());
    }
 
    inline bool internallyActive(node w, int v) const {
        OGDF_ASSERT(w != nullptr);
        return m_dfi[w] > 0 && pertinent(w) && !externallyActive(w, v);
    }
 
    inline bool externallyActive(node w, int v) const {
        OGDF_ASSERT(w != nullptr);
        if (m_dfi[w] <= 0) {
            return false;
        }
        if (m_leastAncestor[w] < v) {
            return true;
        }
        return !m_separatedDFSChildList[w].empty()
                && m_lowPoint[m_separatedDFSChildList[w].front()] < v;
    }
 
    inline bool inactive(node w, int v) {
        OGDF_ASSERT(w != nullptr);
        if (m_dfi[w] <= 0) {
            return true;
        }
        if (!m_backedgeFlags[w].empty() || !m_pertinentRoots[w].empty() || m_leastAncestor[w] < v) {
            return false;
        }
        return m_separatedDFSChildList[w].empty()
                || m_lowPoint[m_separatedDFSChildList[w].front()] >= v;
    }
 
 
    inline int infoAboutNode(node w, int v) const {
        OGDF_ASSERT(w != nullptr);
        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) const {
        OGDF_ASSERT(w != nullptr);
        OGDF_ASSERT(w->degree() > 0);
        OGDF_ASSERT(m_link[BoyerMyrvoldPlanar::DirectionCW][w] != nullptr);
        OGDF_ASSERT(m_link[BoyerMyrvoldPlanar::DirectionCCW][w] != nullptr);
        adjEntry adj = m_link[direction][w];
        OGDF_ASSERT(adj->theNode() != nullptr);
 
        if (w->degree() > 1) {
            direction = adj
                    == beforeShortCircuitEdge(adj->theNode(), BoyerMyrvoldPlanar::DirectionCCW)->twin();
        }
        OGDF_ASSERT(direction
                || adj == beforeShortCircuitEdge(adj->theNode(), BoyerMyrvoldPlanar::DirectionCW)->twin());
        return adj->theNode();
    }
 
    inline node successorWithoutShortCircuit(node w, int& direction) {
        OGDF_ASSERT(w != nullptr);
        OGDF_ASSERT(w->degree() > 0);
        OGDF_ASSERT(m_link[BoyerMyrvoldPlanar::DirectionCW][w] != nullptr);
        OGDF_ASSERT(m_link[BoyerMyrvoldPlanar::DirectionCCW][w] != nullptr);
        adjEntry adj = beforeShortCircuitEdge(w, direction);
        OGDF_ASSERT(adj->theNode() != nullptr);
 
        if (w->degree() > 1) {
            direction = adj
                    == beforeShortCircuitEdge(adj->theNode(), BoyerMyrvoldPlanar::DirectionCCW)->twin();
        }
        OGDF_ASSERT(direction
                || adj == beforeShortCircuitEdge(adj->theNode(), BoyerMyrvoldPlanar::DirectionCW)->twin());
        return adj->theNode();
    }
 
 
    inline node constSuccessorOnExternalFace(node v, int direction) {
        OGDF_ASSERT(v != nullptr);
        OGDF_ASSERT(v->degree() > 0);
        return m_link[direction][v]->theNode();
    }
 
 
    inline node constSuccessorWithoutShortCircuit(node v, int direction) const {
        OGDF_ASSERT(v != nullptr);
        OGDF_ASSERT(v->degree() > 0);
        return beforeShortCircuitEdge(v, direction)->theNode();
    }
 
 
    inline adjEntry beforeShortCircuitEdge(node v, int direction) const {
        OGDF_ASSERT(v != nullptr);
        return (m_beforeSCE[direction][v] == nullptr) ? m_link[direction][v]
                                                      : m_beforeSCE[direction][v];
    }
 
 
    node activeSuccessor(node w, int& direction, int v, int& info) const;
 
 
    inline node constActiveSuccessor(node w, int direction, int v, int& info) const {
        return activeSuccessor(w, direction, v, info);
    }
 
 
    inline bool wNodesExist(node root, node stopx, node stopy) const {
        OGDF_ASSERT(root != stopx);
        OGDF_ASSERT(root != stopy);
        OGDF_ASSERT(stopx != stopy);
        int dir = BoyerMyrvoldPlanar::DirectionCCW;
        bool between = false;
        while (root != nullptr) {
            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) {
        std::cout
                << "\nprintNodeInfo(" << m_dfi[v] << "): "
                << "CCW=" << m_dfi[constSuccessorOnExternalFace(v, BoyerMyrvoldPlanar::DirectionCCW)]
                << ",CW=" << m_dfi[constSuccessorOnExternalFace(v, BoyerMyrvoldPlanar::DirectionCW)]
                << "\tCCWBefore="
                << m_dfi[constSuccessorWithoutShortCircuit(v, BoyerMyrvoldPlanar::DirectionCCW)]
                << ",CWBefore="
                << m_dfi[constSuccessorWithoutShortCircuit(v, BoyerMyrvoldPlanar::DirectionCW)]
                << "\tadjList: ";
        adjEntry adj;
        for (adj = v->firstAdj(); adj; adj = adj->succ()) {
            std::cout << adj->twinNode() << " ";
        }
    }
 
    void mergeBiconnectedComponent(ArrayBuffer<int>& stack);
 
    void embedBackedges(const node v, const int v_dir, const node w, const int w_dir);
 
    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();
 
 
    Graph& m_g;
 
    const bool m_bundles;
    const int m_embeddingGrade;
    const bool m_limitStructures;
    const double m_randomness;
    const bool m_avoidE2Minors;
    const EdgeArray<int>* m_edgeCosts;
    std::minstd_rand m_rand;
 
    bool m_extractSubgraph = true;
 
    int m_flippedNodes;
 
 
 
    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<BoyerMyrvoldEdgeType> m_edgeType;
 
    NodeArray<int> m_lowPoint;
 
    NodeArray<int> m_highestSubtreeDFI;
 
 
    NodeArray<ListPure<node>> m_separatedDFSChildList;
 
 
    NodeArray<ListIterator<node>> m_pNodeInParent;
 
 
    NodeArray<int> m_visited;
 
    EdgeArray<node> m_pointsToRoot;
 
    NodeArray<edge> m_visitedWithBackedge;
 
    NodeArray<int> m_numUnembeddedBackedgesInBicomp;
 
 
    NodeArray<bool> m_flipped;
 
 
    NodeArray<SListPure<adjEntry>> m_backedgeFlags;
 
    NodeArray<SListPure<node>> m_pertinentRoots;
 
    SListPure<KuratowskiStructure>& m_output;
 
};
 
inline bool operator>(int lhs, BoyerMyrvoldPlanar::EmbeddingGrade rhs) {
    return lhs > static_cast<int>(rhs);
}
 
inline bool operator==(int lhs, BoyerMyrvoldPlanar::EmbeddingGrade rhs) {
    return lhs == static_cast<int>(rhs);
}
 
inline bool operator!=(int lhs, BoyerMyrvoldPlanar::EmbeddingGrade rhs) {
    return lhs != static_cast<int>(rhs);
}
 
inline bool operator<=(int lhs, BoyerMyrvoldPlanar::EmbeddingGrade rhs) {
    return lhs <= static_cast<int>(rhs);
}
 
}