SeparatorHarPeled.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/PlanarSeparatorModule.h>
 
#include <cmath>
#include <memory>
#include <string>
 
namespace ogdf {
class GraphCopy;
 
namespace planar_separators {
 
class OGDF_EXPORT BFSTreeHP : public ArrayBFSTree {
public:
    BFSTreeHP(GraphCopy& G, node rootNode) : ArrayBFSTree(G, rootNode) { construct(); }
 
    void construct();
 
    void reconstruct(const Cycle& cycle);
 
    void calculateDescendants();
};
 
struct Ring; // see below
 
}
 
using namespace planar_separators;
 
 
class OGDF_EXPORT SeparatorHarPeled : public PlanarSeparatorModule {
    friend struct planar_separators::Ring;
 
public:
    SeparatorHarPeled() { }
 
    virtual double getMaxSeparatorSize(int n) const override { return sqrt(8) * sqrt(n); }
 
    virtual std::string getSpecificName() const override { return "HPN"; } // Har-Peled and Nayyeri
 
protected:
#ifdef OGDF_DEBUG
 
    void verifyRing(const Ring& ring) const;
 
#endif
 
    virtual bool doSeparate(const Graph& G, List<node>& separator, List<node>& first,
            List<node>& second) override;
 
    std::shared_ptr<BFSTreeHP> tree;
 
    virtual void reset() override;
 
    virtual void makeTree();
 
    edge findSeparatorEdge() const;
 
    void createDual(Graph& Dual, EdgeArray<edge>& oldEdge) const;
 
    void findFaceLevels(const node root);
 
    void buildRings(const Cycle& cycle);
 
    int find_i0(int delta) const;
 
    bool findRegions(List<node>& region, const Cycle& cycle, const Ring& inner, int outerIdx) const;
 
    void walkAlongSeparator(node startNode, node endNode, EdgeArray<bool>& regionBorder,
            List<node>& region) const;
 
    void walkAlongRing(const Ring& ring, bool firstSection, bool invert,
            EdgeArray<bool>& regionBorder, List<node>& region) const;
 
    bool testRegionSize(node startNode, const EdgeArray<bool>& regionBorder, bool inside,
            int regionSize) const;
 
    bool findRegion(List<node>& region, const Cycle& cycle, const Ring& inner, const Ring& outer,
            bool inside) const;
 
    bool constructK(List<node>& region, const Cycle& cycle, const Ring& inner,
            const Ring& outer) const;
 
    bool finalize(std::string exit, const List<node>& region, List<node>& separator,
            List<node>& first, List<node>& second);
 
private:
    ConstCombinatorialEmbedding E;
    node psi; // the deeper of the two endpoints of tree-separator u,v
 
    FaceArray<int> faceLevels; // holds for each face which level it inhabits
    EdgeArray<int> border; // holds for every edge for which value i it lies on the border of region P<=i
    List<List<face>> faceFrontiers; // for each level of the expansion, holds the list of faces that form the inner lining of the ring
 
    NodeArray<List<adjEntry>> ringIn;
    NodeArray<List<adjEntry>> ringOut;
    NodeArray<bool> isMultiNode; // holds whether this node has more than 2 connecting edges
 
    Array<Ring, int> rings; // the concentric rings of nodes around the root
 
    NodeArray<adjEntry> mainSeparator; // represents the big separator in a way that allows immediate access
};
 
namespace planar_separators {
 
struct Ring {
    List<node> nodes;
    List<adjEntry> entries;
 
    node in;
    node out;
 
    int faces; // number of faces inside this ring
 
    bool isDegenerate = false;
 
    Ring() { } // to be able to store them in arrays
 
    Ring(node n) : in {n}, out {n}, isDegenerate {true} { }
 
    Ring(node startNode, node endNode, adjEntry outPointer, const SeparatorHarPeled& separator) {
        OGDF_ASSERT(outPointer->theNode() == startNode);
 
        nodes.pushBack(startNode);
        in = startNode;
        out = endNode;
 
        node next; // the next node in the ring
        adjEntry nextEntry; // the adjEntry that points to the next node
 
        // handling edge case of a multinode as startnode
        if (separator.isMultiNode[startNode]) {
            adjEntry outP = outPointer;
            while (separator.ringOut[startNode].search(outP) == separator.ringOut[startNode].end()) {
                outP = outP->cyclicSucc();
            }
            nextEntry = outP;
        } else {
            nextEntry = separator.ringOut[startNode].front();
        }
        next = nextEntry->twinNode();
 
        // walk along ring until we arrive back at startNode
        while (next != startNode) {
            nodes.pushBack(next);
            entries.pushBack(nextEntry);
 
            // find next nextEntry
            if (separator.ringOut[next].size() > 1) {
                adjEntry candidate =
                        nextEntry->twin()->cyclicSucc(); // start checking at the entry via which we entered
                while (separator.ringOut[next].search(candidate) == separator.ringOut[next].end()) {
                    candidate = candidate->cyclicSucc();
                }
                nextEntry = candidate;
            } else if (separator.ringOut[next].size() == 1) {
                nextEntry = separator.ringOut[next].front();
            } else {
                OGDF_ASSERT(false); // this should not happen, only the root is not part of a ring
            }
            next = nextEntry->twinNode();
        }
        entries.pushBack(nextEntry); // to close the ring, point back to first node
    }
 
    int getFaces() const { return faces; }
 
    int getSize() const { return nodes.size(); }
 
    List<adjEntry> getSectionInSeparator(bool firstSection) const {
        List<adjEntry> list;
 
        if (isDegenerate) {
            return list; // degenerate ring is empty
        }
 
        auto adjIt = entries.cbegin();
 
        if (firstSection) {
            // go start to end
            while (adjIt != entries.cend() && (*adjIt)->theNode() != out) {
                list.pushBack(*adjIt);
                ++adjIt;
            }
        } else {
            // go end to start
            while ((*adjIt)->theNode() != out && adjIt != entries.cend()) {
                adjIt++;
            }
            while (adjIt != entries.cend()) {
                list.pushBack(*adjIt);
                ++adjIt;
            }
        }
        return list;
    }
};
 
}
}