PlanarSeparatorModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/extended_graph_alg.h>
#include <ogdf/basic/simple_graph_alg.h>
 
#include <functional>
#include <map>
#include <memory>
#include <string>
#include <utility>
#include <vector>
 
namespace ogdf {
template<class E>
class SListPure;
 
namespace planar_separators {
 
class OGDF_EXPORT BFSTree {
public:
    virtual ~BFSTree() = default;
 
    virtual GraphCopy* getGraph() const = 0;
 
    virtual node getRoot() const = 0;
 
    virtual int getGraphSize() const = 0;
 
    virtual bool isInTree(edge e) const = 0;
 
    virtual int getLevelOfNode(node n) const = 0;
 
    virtual node getParentOfNode(node n) const = 0;
 
    virtual int getDescendantsOfNode(node n) const = 0;
 
    virtual List<node> getChildrenOfNode(node n) const = 0;
 
    virtual adjEntry getAdjToParent(node n) const = 0;
};
 
class OGDF_EXPORT ArrayBFSTree : public BFSTree {
public:
    ArrayBFSTree(GraphCopy& G, node rootNode) : pGraph {&G}, root {rootNode} { init(); }
 
    void init() {
        // init arrays
        levelOfNode.init(*pGraph, -1);
        parentOfNode.init(*pGraph, nullptr);
        childrenOfNode.init(*pGraph);
        edgeToParent.init(*pGraph, nullptr);
        descendantsOfNode.init(*pGraph,
                1); // number of descendants of a node, the node itself counts as its own descendant
        inTree.init(*pGraph, false);
        mark.init(*pGraph, false); // records if that node was visited by BFS
 
        // mark root node
        mark[root] = true;
    }
 
    GraphCopy* getGraph() const override { return pGraph; }
 
    node getRoot() const override { return root; }
 
    int getGraphSize() const override {
        OGDF_ASSERT(pGraph != nullptr);
        return pGraph->numberOfNodes();
    }
 
    bool isInTree(edge e) const override { return inTree[e]; }
 
    int getLevelOfNode(node n) const override { return levelOfNode[n]; }
 
    node getParentOfNode(node n) const override { return parentOfNode[n]; }
 
    int getDescendantsOfNode(node n) const override { return descendantsOfNode[n]; }
 
    List<node> getChildrenOfNode(node n) const override { return childrenOfNode[n]; }
 
    adjEntry getAdjToParent(node n) const override { return edgeToParent[n]; }
 
#ifdef OGDF_HEAVY_DEBUG
    // this is very expensive
    void assertTreeConsistency() const {
        NodeArray<int> marked;
        marked.init(*pGraph);
        for (node no : pGraph->nodes) {
            marked[no] = no->index();
        }
 
        for (edge e : pGraph->edges) {
            if (isInTree(e)) {
                node s = e->source();
                node t = e->target();
                OGDF_ASSERT(marked[s] != marked[t]);
                int newIdx = marked[s] < marked[t] ? marked[s] : marked[t];
                int otherIdx = marked[s] < marked[t] ? marked[t] : marked[s];
 
                for (node no : pGraph->nodes) {
                    if (marked[no] == otherIdx) {
                        marked[no] = newIdx;
                    }
                }
            }
        }
 
        // afterwards, assert that all nodes are in fact marked
        int lowest = marked[pGraph->firstNode()];
        for (edge e : pGraph->edges) {
            if (!isInTree(e)) {
                OGDF_ASSERT(marked[e->source()] == lowest && marked[e->target()] == lowest);
            }
        }
    }
#endif
 
 
protected:
    GraphCopy* pGraph;
    node root; // root node
 
    NodeArray<int> levelOfNode; // holds for each node on which level it is
    NodeArray<node> parentOfNode; // holds for each node which node is his parent in the tree
    NodeArray<List<node>> childrenOfNode; // holds for each node a list of children in the tree
    NodeArray<adjEntry> edgeToParent; // holds for each node the edge which connects it to its parent
    NodeArray<int> descendantsOfNode; // holds for each node how many descendants it has in the tree
    NodeArray<bool> mark;
    EdgeArray<bool> inTree; // hold for each edge whether it is in the BFS tree
};
 
class OGDF_EXPORT BFSTreeClassical : public ArrayBFSTree {
public:
    BFSTreeClassical(GraphCopy& G, node rootNode, unsigned int heightMaxIterations,
            bool findLevelsSimple = false);
 
    ~BFSTreeClassical() { }
 
    void construct(node rootNode, unsigned int numIterations);
 
    void reconstruct();
 
    void createNewRoot(bool useTriBFS = false);
 
    int getSizeOfLevel(int level) const;
 
    List<node> getLevel(int level) const;
 
    List<node> getNodesFromTo(int start, int end) const;
 
    List<node> getNodesFrom(int start) const;
 
    void restructure(List<node>& separator, List<node>& second, bool useTriBFS = false);
 
    void removeSeparatorLevels(List<node>& separator, List<node>& second);
 
    bool isVisited(node n) const { return mark[n]; }
 
    int getSeparatorLevel() const { return currentLevel; }
 
    int get_t0() const { return t0; }
 
    int get_t1() const { return t1; }
 
    int get_t2() const { return t2; }
 
protected:
    void findLevels();
 
    void findLevelsSimple();
 
 
private:
    List<List<node>> levels; // contains all levels, each as a list of nodes
 
    unsigned int heightMaxIterations;
    bool simple; // stupid workaround for being able to change generation of level t0 and t2
 
    // construction
    int currentLevel = 0;
    bool belowMiddle = true;
    double m_ratio;
 
    // separator levels
    int t0;
    int t1;
    int t2;
    int k; // number of nodes in levels 0 through t1
 
    void visit(node v, node parent, adjEntry adj, SListPure<node>& bfs);
};
 
class OGDF_EXPORT Postprocessor {
public:
    Postprocessor() {};
 
    virtual ~Postprocessor() {};
 
    virtual bool apply(const Graph& G, List<node>& separator, List<node>& first,
            List<node>& second) = 0;
 
    virtual std::string getName() const = 0;
};
 
class OGDF_EXPORT NodeExpulsor : public Postprocessor {
public:
    NodeExpulsor(bool balance = true) : keepBalance {balance} { }
 
    bool apply(const Graph& G, List<node>& separator, List<node>& first, List<node>& second) override;
 
    std::string getName() const override { return "NE"; }
 
private:
    bool keepBalance;
};
 
class OGDF_EXPORT DMDecomposer : public Postprocessor {
public:
    bool apply(const Graph& G, List<node>& separator, List<node>& first, List<node>& second) override;
 
    std::string getName() const override { return "DMD"; }
 
private:
    NodeArray<short> assignments; // assigns numbers to nodes: 0 = n is in separator, 1 = n is in shorter list, 2 = n is in longer list
 
    List<node> bipartSep; // clones of separator nodes in the bipartite graph
    List<node> bipartB; // clones of B-nodes in the bipartite graph
 
    // arrays from original graph G
    NodeArray<bool> isInS; // contains whether a node is in the separator or not
    NodeArray<node> clone; // maps from G to bipartite graph
 
    // arrays from bipartite graph
    NodeArray<node> unclone; // maps from bipartite graph to G
    EdgeArray<bool> flow; // contains whether an edge is in the matching or not
 
    // Dulmage Mendelsohn Decomposition
    List<node> SI;
    List<node> SX;
    List<node> SR;
 
    List<node> BI;
    List<node> BX;
    List<node> BR;
 
    void reset();
 
    void setupAssignments(const Graph& G, const List<node>& separator, const List<node>& first,
            const List<node>& second);
 
    void bipartiteGraph(Graph& graph, const List<node>& separator);
 
    void translateAssignments(const Graph& G, List<node>& separator, List<node>& first,
            List<node>& second) const;
 
    void calculateRemainders(const Graph& graph);
 
    void chooseBalancedDecomposition(const Graph& G, List<node>& separator, List<node>& first,
            List<node>& second);
 
    bool alternatingBFS(const Graph& G, const List<node>& startNodes, List<node>& reachableSep,
            List<node>& reachableB);
 
    void decompose(const Graph& graph, const List<node>& bipart, List<node>& reachableSep,
            List<node>& reachableB);
};
 
class OGDF_EXPORT Cycle {
public:
    Cycle(BFSTree* tree, edge startEdge);
 
    Cycle& operator=(Cycle&& other) {
        tree = other.tree;
        nodes = std::move(other.nodes);
        edges = std::move(other.edges);
        isOnCycle = std::move(other.isOnCycle);
        isEdgeOnCycle = std::move(other.isEdgeOnCycle);
        cycleRoot = other.cycleRoot;
        costClock = other.costClock;
        costCounter = other.costCounter;
        isClockwise = other.isClockwise;
 
        other.tree = nullptr;
        other.cycleRoot = nullptr;
 
        return *this;
    }
 
    Cycle(Cycle&& other)
        : tree {other.tree}
        , nodes(std::move(other.nodes))
        , edges(std::move(other.edges))
        , isOnCycle(std::move(other.isOnCycle))
        , isEdgeOnCycle(std::move(other.isEdgeOnCycle))
        , cycleRoot {other.cycleRoot}
        , costClock {other.costClock}
        , costCounter {other.costCounter}
        , isClockwise {other.isClockwise} {
        other.tree = nullptr;
        other.cycleRoot = nullptr;
    }
 
    int getSize() const { return nodes.size(); }
 
    bool getClockwise() const { return isClockwise; }
 
    const List<node>& getNodes() const { return nodes; }
 
    const List<adjEntry>& getEdges() const { return edges; }
 
    const node& getRoot() const { return cycleRoot; }
 
    int getInsideCost() const;
 
    int getOutsideCost() const;
 
    Cycle expandCycle();
 
    void print() const;
 
    void fillLists(List<node>& separator, List<node>& first, List<node>& second,
            bool useRoot = false);
 
private:
    class Iterator {
    private:
        const Cycle* cycle;
        adjEntry m_current;
        const bool isClockwise;
 
        adjEntry next(adjEntry current) const {
            adjEntry next;
 
            if (isClockwise) {
                if (cycle->isEdgeOnCycle[m_current->theEdge()]) {
                    next = current->twin()->cyclicSucc();
                } else {
                    next = current->cyclicSucc();
                }
            } else {
                if (cycle->isEdgeOnCycle[m_current->theEdge()]) {
                    next = current->twin()->cyclicPred();
                } else {
                    next = current->cyclicPred();
                }
            }
            if (next->theEdge() == cycle->getCurrentExpandEdge()->theEdge()) {
                return nullptr;
            }
            return next;
        }
 
    public:
        Iterator(const Cycle* cyc, bool clockwise)
            : cycle {cyc}, m_current {cyc->getCurrentExpandEdge()}, isClockwise {clockwise} {
            ++(*this);
        }
 
        Iterator(const Cycle* cyc) : cycle(cyc), m_current(nullptr), isClockwise {false} { }
 
        bool isOutEdge() {
            return m_current->theNode() == cycle->cycleRoot
                    && m_current == cycle->tree->getAdjToParent(cycle->cycleRoot);
        }
 
        adjEntry operator*() const { return m_current; }
 
        Iterator& operator++() {
            m_current = next(m_current);
            while (m_current != nullptr
                    && cycle->isEdgeOnCycle[m_current->theEdge()]) { //m_current == cycle->sep.edgeToParent[m_current->theNode()]) {
                m_current = next(m_current);
            }
            return *this;
        }
 
        Iterator operator++(int) {
            Iterator tmp = *this;
            ++(*this);
            return tmp;
        }
 
        friend bool operator==(const Iterator& a, const Iterator& b) {
            return a.m_current == b.m_current;
        };
 
        friend bool operator!=(const Iterator& a, const Iterator& b) {
            return a.m_current != b.m_current;
        };
    };
 
    BFSTree* tree; // the BFS-Tree with which this cycle is associated
 
    List<node> nodes; // nodes on the cycle
    List<adjEntry> edges; // edges on the cycle
    NodeArray<bool> isOnCycle; // holds for each node whether it is on the cycle or not
    EdgeArray<bool> isEdgeOnCycle; // holds for each edge whether it is on the cycle or not
 
    node cycleRoot; // root node of the cycle, i.e. node in which its two arms meet
 
    int costClock {0}; // cost of clockwise nodes
    int costCounter {0}; // cost of counter-clockwise nodes
    bool isClockwise;
 
    Cycle(BFSTree* tree, List<node>& nodeList, List<adjEntry>& edgeList, node root, bool clockwise);
 
    Cycle(BFSTree* tree, bool clockwise);
 
    void init(List<node>& nodeList, List<adjEntry>& edgeList, node root);
 
    Iterator begin() const { return Iterator(this, isClockwise); }
 
    Iterator end() const { return Iterator(this); }
 
    void popBackNode();
 
    void popBackEdge();
 
    void popFrontNode();
 
    void popFrontEdge();
 
    void pushFrontEdge(adjEntry adj);
 
    adjEntry getCurrentExpandEdge() const;
 
    void expandWithTreeEdge(node y, node v, node w, adjEntry vy, adjEntry yw);
 
    Cycle expandWithoutTreeEdges(node y, const node v, const node w, const adjEntry vy,
            const adjEntry yw);
 
    std::pair<node, node> findPathToCycle(node& y, List<node>& pathNodes,
            List<adjEntry>& pathAdjEntries) const;
 
    bool findAlphaCycle(Cycle& cyc, const List<node>& pathNodes,
            const List<adjEntry>& pathAdjEntries, const node z, const node propRoot,
            const adjEntry yw, List<node>& oldNodes, List<adjEntry>& oldEdges) const;
 
    void findBetaCycle(Cycle& cyc, const List<node>& pathNodes, const List<adjEntry>& pathAdjEntries,
            const node z, const node propRoot, const adjEntry vy, List<node>& oldNodes,
            List<adjEntry>& oldEdges, bool foundRootOnAlpha) const;
 
    void increaseCost(adjEntry adj, bool clockwise);
 
    void collectChildrenOfNode(const node no, NodeArray<bool>& marked, List<node>& list,
            bool useRoot = false) const;
 
    void computeCosts();
};
 
} // namespace planar_separators
 
using namespace planar_separators;
 
 
class OGDF_EXPORT PlanarSeparatorModule {
public:
    PlanarSeparatorModule() { }
 
    virtual ~PlanarSeparatorModule() { }
 
    void addPostProcessor(Postprocessor& post) { postProcessors.push_back(&post); }
 
    void clearPostProcessors() { postProcessors.clear(); }
 
    void setStartIndex(int index) { startNodeIndex = index; }
 
    virtual bool separate(const Graph& G, List<node>& separator, List<node>& first,
            List<node>& second, bool checkPreconditions = true) final {
        if (setup(G, separator, first, second, checkPreconditions)) {
            return true;
        }
 
        reset(); // reset everything to ensure the module can be reused
 
        bool result = doSeparate(G, separator, first, second); // call core algorithm
 
        if (result) {
            cleanup(G, separator, first, second);
 
            postProcess(G, separator, first, second);
        }
 
        return result;
    }
 
    virtual bool separate(const Graph& G, NodeArray<short>& assignments,
            bool checkPreconditions = true) final {
        OGDF_ASSERT(assignments.graphOf() == &G);
 
        List<node> separator;
        List<node> first;
        List<node> second;
 
        bool result = separate(G, separator, first, second, checkPreconditions);
 
        if (!result) {
            return false;
        }
 
        for (node n : separator) {
            assignments[n] = 0;
        }
        for (node n : first) {
            assignments[n] = 1;
        }
        for (node n : second) {
            assignments[n] = 2;
        }
        return true;
    }
 
    virtual std::string getName() const {
        std::string name = getSpecificName();
        for (const auto& post : postProcessors) {
            name += "_" + post->getName();
        }
        return name;
    }
 
    std::string getExitPoint() const { return exitPoint; }
 
    virtual double getMaxSeparatorSize(int n) const = 0;
 
protected:
    std::vector<Postprocessor*> postProcessors;
 
    std::shared_ptr<GraphCopy> graph;
 
    int startNodeIndex = -1;
 
    // the algorithms can return at different points - this variable stores where that happened, for analysis only
    std::string exitPoint;
 
    node getStartNode(const Graph& G) const {
        if (startNodeIndex == -1) {
            return G.chooseNode();
        } else {
            return G.chooseNode([&](node n) { return (n->index() == startNodeIndex); });
        }
    }
 
    virtual bool doSeparate(const Graph& G, List<node>& separator, List<node>& first,
            List<node>& second) = 0;
 
    bool setup(const Graph& G, List<node>& separator, List<node>& first, List<node>& second,
            bool checkPreconditions = true) {
        exitPoint = "graph_trivial";
        if (G.empty()) {
            return true; // an empty graph is separated without us doing anything
        }
 
        OGDF_ASSERT(isPlanar(G));
 
        graph = std::make_shared<GraphCopy>(G);
 
        // call separateComponents to check if we even need to do anything, return success if not
        if (separateComponents(*graph, separator, first, second)) {
            return true;
        }
 
        // even checking these conditions is expensive, so if you know that they all hold, you can skip this
        if (checkPreconditions) {
            if (!graph->representsCombEmbedding()) {
                planarEmbedPlanarGraph(*graph);
            }
            if (!isSimpleUndirected(*graph)) {
                makeSimpleUndirected(*graph);
            }
        }
 
        OGDF_ASSERT(graph->representsCombEmbedding());
        OGDF_ASSERT(isConnected(*graph));
        OGDF_ASSERT(isSimpleUndirected(*graph));
 
        return false;
    }
 
    bool cleanup(const Graph& G, List<node>& separator, List<node>& first, List<node>& second) {
        if (first.empty() && second.empty()) {
            for (int i = 0; i < G.numberOfNodes() / 2.0; i++) {
                first.pushBack(separator.popFrontRet());
            }
            return true;
        }
        return false;
    }
 
    bool separateComponents(GraphCopy& G, List<node>& separator, List<node>& first,
            List<node>& second, bool skip = false) const;
 
    bool postProcess(const Graph& G, List<node>& separator, List<node>& first, List<node>& second) {
        for (Postprocessor* post : postProcessors) {
            post->apply(G, separator, first, second);
        }
        return true;
    }
 
    virtual std::string getSpecificName() const = 0;
 
    virtual void reset() {};
 
private:
    int connectedComponents(const Graph& G, NodeArray<int>& component,
            std::map<int, int>& compSizes) const;
};
 
 
}