EdgePairPartition.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/GraphSets.h>
#include <ogdf/basic/basic.h>
 
#include <list>
#include <memory>
#include <set>
#include <stack>
#include <vector>
 
namespace ogdf::oneplan_backtracking {
 
template<typename GraphElementPointer>
class OrderedPair {
private:
    GraphElementPointer m_first, m_second;
 
public:
    OrderedPair(GraphElementPointer a, GraphElementPointer b) {
        OGDF_ASSERT(a && b);
        OGDF_ASSERT(a->graphOf() == b->graphOf());
        OGDF_ASSERT(a != b);
        if (a->index() < b->index()) {
            m_first = a;
            m_second = b;
        } else {
            m_first = b;
            m_second = a;
        }
    }
 
    GraphElementPointer first() const { return m_first; }
 
    GraphElementPointer second() const { return m_second; }
 
    bool contains(GraphElementPointer el) const { return m_first == el || m_second == el; }
 
    bool operator==(const OrderedPair& rhs) const {
        OGDF_ASSERT(graphOf() == rhs.graphOf());
        OGDF_ASSERT(m_first->index() <= m_second->index());
        OGDF_ASSERT(rhs.m_first->index() <= rhs.m_second->index());
 
        return m_first == rhs.m_first && m_second == rhs.m_second;
    }
 
    bool operator!=(const OrderedPair& rhs) const { return !operator==(rhs); }
 
    bool operator<(const OrderedPair& rhs) const {
        OGDF_ASSERT(graphOf() == rhs.graphOf());
        OGDF_ASSERT(m_first->index() <= m_second->index());
        OGDF_ASSERT(rhs.m_first->index() <= rhs.m_second->index());
 
        return m_first->index() < rhs.m_first->index()
                || ((m_first->index() == rhs.m_first->index())
                        && (m_second->index() < rhs.m_second->index()));
    }
 
#ifdef OGDF_DEBUG
    const Graph* graphOf() const { return m_first->graphOf(); }
#endif
};
 
using VertexPair = OrderedPair<node>;
using EdgePair = OrderedPair<edge>;
 
enum class OGDF_EXPORT OneplanMode {
    Normal, 
    NIC, 
    IC 
};
 
 
class OGDF_EXPORT EdgePairPartition {
private:
    struct UndoInformation {
        std::set<EdgePair> m_crossings;
        std::set<VertexPair> m_kiteEdges;
        std::set<EdgePair> m_nonCrossingPairs;
        std::list<EdgePair> m_todoCrossings;
        std::unique_ptr<EdgePair> m_previousCrossing = nullptr;
    };
 
    OneplanMode m_mode = OneplanMode::Normal;
    const Graph& m_graph;
    EdgeSet m_crossedEdges;
    std::set<VertexPair> m_kiteEdges;
    std::set<EdgePair> m_crossingEdgePairs;
    std::set<EdgePair> m_freeEdgePairs;
 
    std::stack<UndoInformation> m_undoInformation;
 
public:
 
    explicit EdgePairPartition(const Graph& g, OneplanMode m = OneplanMode::Normal)
        : m_mode(m), m_graph(g), m_crossedEdges(m_graph) {
        for (edge e1 : m_graph.edges) {
            for (edge e2 : m_graph.edges) {
                if (!e1->isAdjacent(e2)) {
                    m_freeEdgePairs.emplace(e1, e2);
                }
            }
        }
    }
 
    EdgePairPartition(const EdgePairPartition& other)
        : m_mode(other.m_mode)
        , m_graph(other.m_graph)
        , m_crossedEdges(other.m_crossedEdges)
        , m_kiteEdges(other.m_kiteEdges)
        , m_crossingEdgePairs(other.m_crossingEdgePairs)
        , m_freeEdgePairs(other.m_freeEdgePairs) { }
 
    const Graph& graph() const { return m_graph; }
 
    const std::set<VertexPair>& kiteEdges() const { return m_kiteEdges; }
 
    const std::set<EdgePair>& crossingEdgePairs() const { return m_crossingEdgePairs; }
 
    void startTransaction() { m_undoInformation.emplace(); }
 
    void startTransaction(std::vector<EdgePair>& todoCrossings) {
        UndoInformation& ui = m_undoInformation.emplace();
        ui.m_todoCrossings.assign(todoCrossings.begin(), todoCrossings.end());
    }
 
    void undoTransaction();
 
    bool hasTodoCrossing() {
        if (m_undoInformation.empty()) {
            return false;
        }
        return !m_undoInformation.top().m_todoCrossings.empty();
    }
 
    EdgePair getNextTodoCrossing() {
        OGDF_ASSERT(hasTodoCrossing());
        EdgePair ep = m_undoInformation.top().m_todoCrossings.front();
        m_undoInformation.top().m_todoCrossings.pop_front();
        m_undoInformation.top().m_previousCrossing = std::make_unique<EdgePair>(ep);
        return ep;
    }
 
    void crossEdgePair(const EdgePair& pair);
 
    void setNonCrossing(const EdgePair& pair) {
        if (m_freeEdgePairs.count(pair) > 0) {
            m_freeEdgePairs.erase(pair);
            m_undoInformation.top().m_nonCrossingPairs.insert(pair);
        }
    }
 
    bool isFree(const EdgePair& pair) const {
        OGDF_ASSERT(pair.graphOf() == &m_graph);
        if (m_crossedEdges.contains(pair.first()) || m_crossedEdges.contains(pair.second())) {
            return false;
        }
        if (m_kiteEdges.count({pair.first()->source(), pair.first()->target()}) > 0
                || m_kiteEdges.count({pair.second()->source(), pair.second()->target()}) > 0) {
            return false;
        }
        return m_freeEdgePairs.count(pair) > 0;
    }
 
    bool isFree(edge e) const {
        if (m_kiteEdges.count({e->source(), e->target()}) > 0 || m_crossedEdges.contains(e)) {
            return false;
        }
        for (EdgePair ep : m_freeEdgePairs) {
            if (ep.contains(e)) {
                return true;
            }
        }
        return false;
    }
 
    bool isCrossed(edge e) const {
        for (EdgePair ep : m_crossingEdgePairs) {
            if (ep.contains(e)) {
                return true;
            }
        }
        return false;
    }
 
    static edge getEdgeBetween(node a, node b) {
        for (adjEntry adj : a->adjEntries) {
            if (adj->twinNode() == b) {
                return adj->theEdge();
            }
        }
        return nullptr;
    }
 
private:
    void computeKiteEdges(const EdgePair& crossedPair);
 
    void addKiteEdge(edge e) {
        OGDF_ASSERT(e->graphOf() == &m_graph);
        if (!m_crossedEdges.contains(e)) {
            addKiteEdge({e->source(), e->target()});
        }
    }
 
    void addKiteEdge(const VertexPair& vp) {
        if (m_kiteEdges.count(vp) == 0) {
            m_kiteEdges.insert(vp);
            m_undoInformation.top().m_kiteEdges.insert(vp);
        }
    }
};
}