SeparatorDualHelper.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
 
#include <memory>
#include <unordered_set>
#include <utility>
 
namespace ogdf::planar_separators {
class BFSTree;
} // namespace ogdf::planar_separators
 
namespace ogdf {
class GraphCopy;
 
namespace planar_separators {
 
 
class OGDF_EXPORT SeparatorDualHelper {
public:
    SeparatorDualHelper(std::shared_ptr<GraphCopy> pGraph, std::shared_ptr<BFSTree> pTree)
        : graph {pGraph}, tree {pTree} { }
 
    struct CycleData {
        unsigned int inside; // contains number of nodes on the inside
 
        List<node> cycle;
 
        std::unordered_set<node> nodes;
 
        bool isInCycle(node n) { return nodes.find(n) != nodes.end(); }
 
        /* Methods to add and remove nodes from the cycle. */
 
        void pushBack(node n) {
            OGDF_ASSERT(!isInCycle(n));
            cycle.pushBack(n);
            nodes.insert(n);
        }
 
        void pushFront(node n) {
            OGDF_ASSERT(!isInCycle(n));
            cycle.pushFront(n);
            nodes.insert(n);
        }
 
        void popBack() {
            node x = cycle.popBackRet();
            nodes.erase(x);
        }
 
        void popFront() {
            node x = cycle.popFrontRet();
            nodes.erase(x);
        }
 
        CycleData() { }
 
        // case 1
        CycleData(const Graph& G, const face f, const adjEntry adj) : inside {0} {
            pushBack(adj->twinNode());
            pushBack(adj->faceCycleSucc()->twinNode());
            pushBack(adj->theNode());
        }
 
        // case 4
        CycleData(const Graph& G, CycleData& first, CycleData& second) {
            // find path
            List<node> path;
 
            auto firstIt = first.cycle.crbegin();
            auto secondIt = second.cycle.cbegin();
 
            OGDF_ASSERT(*firstIt == *secondIt);
 
            while (firstIt != first.cycle.crend() && secondIt != second.cycle.cend()
                    && *firstIt == *secondIt) {
                path.pushBack(*firstIt);
                ++firstIt;
                ++secondIt;
            }
            node x = path.back();
 
            // number of nodes on the inside
            inside = first.inside + second.inside + path.size() - 1;
 
            // join cycles
            for (auto it = first.cycle.cbegin(); *it != x; ++it) {
                pushBack(*it);
            }
 
            auto it = second.cycle.cbegin();
            while (*it != x) {
                ++it;
            }
            for (; it != second.cycle.cend(); ++it) {
                pushBack(*it);
            }
        }
 
        // case 2
        void addTriangle(adjEntry adj) {
            OGDF_ASSERT(!(isInCycle(adj->theNode()) && isInCycle(adj->twinNode())));
            if (isInCycle(adj->theNode())) {
                pushFront(adj->twinNode());
            } else {
                pushBack(adj->theNode());
            }
        }
 
        // case 3
        void removeTriangle(adjEntry adj) {
            // two different scenarios, depending on which adjacent triangle contains the cycle
            OGDF_ASSERT(isInCycle(adj->theNode()) && isInCycle(adj->twinNode()));
 
            if (cycle.back() == adj->theNode()) {
                popFront();
            } else if (cycle.front() == adj->twinNode()) {
                popBack();
            } else {
                OGDF_ASSERT(false); // Removing triangle was impossible because graph layout was illegitimate.
            }
 
            inside++;
        }
 
        bool checkSize(int n) const { return inside + cycle.size() > 1.0 / 3.0 * n; }
    };
 
    std::shared_ptr<GraphCopy> graph;
    std::shared_ptr<BFSTree> tree;
 
    // components needed for DFS
    CombinatorialEmbedding embedding;
    FaceArray<bool> marked;
 
    CycleData dfs();
 
    CycleData process(face f, adjEntry adj);
 
    List<std::pair<face, adjEntry>> getUnmarkedNeighbours(face f, adjEntry adj);
};
 
}
 
}