Graph_d.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/Observer.h>
#include <ogdf/basic/RegisteredArray.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/comparer.h>
#include <ogdf/basic/internal/config_autogen.h>
#include <ogdf/basic/internal/copy_move.h>
#include <ogdf/basic/internal/graph_iterators.h>
#include <ogdf/basic/memory.h>
 
#include <algorithm>
#include <array>
#include <functional>
#include <iterator>
#include <ostream>
#include <utility>
 
#ifdef OGDF_DEBUG
#   include <set>
#endif
 
namespace ogdf {
class OGDF_EXPORT AdjElement; // IWYU pragma: keep
class OGDF_EXPORT ClusterElement; // IWYU pragma: keep
class OGDF_EXPORT EdgeElement; // IWYU pragma: keep
class OGDF_EXPORT FaceElement; // IWYU pragma: keep
class OGDF_EXPORT Graph; // IWYU pragma: keep
class OGDF_EXPORT NodeElement; // IWYU pragma: keep
 
using node = NodeElement*;
 
using edge = EdgeElement*;
 
using adjEntry = AdjElement*;
 
 
#if __cpp_concepts >= 201907
// clang-format off
template<typename T>
concept OGDF_NODE_FILTER = requires(T f) {
    { f(node()) } -> std::convertible_to<bool>;
};
template<typename T>
concept OGDF_EDGE_FILTER = requires(T f) {
    { f(edge()) } -> std::convertible_to<bool>;
};
template<typename T>
concept OGDF_NODE_ITER = std::forward_iterator<T> && requires(T i) {
    { *i } -> std::convertible_to<node>;
};
template<typename T>
concept OGDF_EDGE_ITER = std::forward_iterator<T> && requires(T i) {
    { *i } -> std::convertible_to<edge>;
};
using std::begin;
using std::end;
template<typename T>
concept OGDF_NODE_LIST = requires(T l) {
    OGDF_NODE_ITER<decltype(begin(l))>;
    OGDF_NODE_ITER<decltype(end(l))>;
};
template<typename T>
concept OGDF_EDGE_LIST = requires(T l) {
    OGDF_EDGE_ITER<decltype(begin(l))>;
    OGDF_EDGE_ITER<decltype(end(l))>;
};
// clang-format on
 
#   define OGDF_HAS_CONCEPTS
#   define OGDF_CHECK_CONCEPT static_assert
 
OGDF_CHECK_CONCEPT(OGDF_NODE_ITER<internal::GraphIterator<node>>);
OGDF_CHECK_CONCEPT(OGDF_EDGE_ITER<internal::GraphIterator<edge>>);
OGDF_CHECK_CONCEPT(OGDF_NODE_ITER<internal::GraphReverseIterator<node>>);
OGDF_CHECK_CONCEPT(OGDF_EDGE_ITER<internal::GraphReverseIterator<edge>>);
OGDF_CHECK_CONCEPT(OGDF_NODE_LIST<internal::GraphObjectContainer<NodeElement>>);
OGDF_CHECK_CONCEPT(OGDF_EDGE_LIST<internal::GraphObjectContainer<EdgeElement>>);
OGDF_CHECK_CONCEPT(OGDF_NODE_ITER<ListIteratorBase<node, false, false>>);
OGDF_CHECK_CONCEPT(OGDF_EDGE_ITER<ListIteratorBase<edge, false, true>>);
OGDF_CHECK_CONCEPT(OGDF_NODE_ITER<ListIteratorBase<node, true, false>>);
OGDF_CHECK_CONCEPT(OGDF_EDGE_ITER<ListIteratorBase<edge, true, false>>);
#else
#   define OGDF_NODE_FILTER typename
#   define OGDF_EDGE_FILTER typename
#   define OGDF_NODE_ITER typename
#   define OGDF_EDGE_ITER typename
#   define OGDF_NODE_LIST typename
#   define OGDF_EDGE_LIST typename
 
#   define OGDF_CHECK_CONCEPT(...)
#endif
 
 
class OGDF_EXPORT AdjElement : private internal::GraphElement {
    friend class Graph;
    friend class internal::GraphListBase;
    friend class internal::GraphList<AdjElement>;
 
    AdjElement* m_twin; 
    edge m_edge; 
    node m_node; 
    int m_id; 
 
    explicit AdjElement(node v) : m_twin(nullptr), m_edge(nullptr), m_node(v), m_id(0) { }
 
    AdjElement(edge e, int id) : m_twin(nullptr), m_edge(e), m_node(nullptr), m_id(id) { }
 
public:
    edge theEdge() const { return m_edge; }
 
    operator edge() const { return m_edge; }
 
    node theNode() const { return m_node; }
 
    operator node() const { return m_node; }
 
    adjEntry twin() const { return m_twin; }
 
    node twinNode() const { return m_twin->m_node; }
 
    int index() const { return m_id; }
 
    bool isSource() const;
 
    bool isBetween(adjEntry adjBefore, adjEntry adjAfter) const;
 
    // traversing faces in clockwise (resp. counter-clockwise) order
    // (if face is an interior face)
 
    adjEntry clockwiseFaceSucc() const { return m_twin->cyclicPred(); }
 
    adjEntry clockwiseFacePred() const { return cyclicSucc()->m_twin; }
 
    adjEntry counterClockwiseFaceSucc() const { return m_twin->cyclicSucc(); }
 
    adjEntry counterClockwiseFacePred() const { return cyclicPred()->m_twin; }
 
    // default is traversing faces in clockwise order
    adjEntry faceCycleSucc() const { return clockwiseFaceSucc(); }
 
    adjEntry faceCyclePred() const { return clockwiseFacePred(); }
 
    adjEntry succ() const { return static_cast<adjEntry>(m_next); }
 
    adjEntry pred() const { return static_cast<adjEntry>(m_prev); }
 
    adjEntry cyclicSucc() const;
    adjEntry cyclicPred() const;
 
#ifdef OGDF_DEBUG
    const Graph* graphOf() const;
#endif
 
    static int compare(const AdjElement& x, const AdjElement& y) { return x.m_id - y.m_id; }
    OGDF_AUGMENT_STATICCOMPARER(AdjElement)
 
    OGDF_NEW_DELETE
};
 
class OGDF_EXPORT NodeElement : private internal::GraphElement {
    friend class Graph;
    friend class internal::GraphList<NodeElement>;
 
    //GraphList<AdjElement> m_adjEdges; //!< The adjacency list of the node.
    int m_indeg; 
    int m_outdeg; 
    int m_id; 
 
#ifdef OGDF_DEBUG
    // we store the graph containing this node for debugging purposes
    const Graph* m_pGraph; 
#endif
 
 
#ifdef OGDF_DEBUG
 
    NodeElement(const Graph* pGraph, int id)
        : m_indeg(0), m_outdeg(0), m_id(id), m_pGraph(pGraph) { }
#else
    NodeElement(int id) : m_indeg(0), m_outdeg(0), m_id(id) { }
#endif
 
 
public:
    internal::GraphObjectContainer<AdjElement> adjEntries;
 
    int index() const { return m_id; }
 
    int indeg() const { return m_indeg; }
 
    int outdeg() const { return m_outdeg; }
 
    int degree() const { return m_indeg + m_outdeg; }
 
    adjEntry firstAdj() const { return adjEntries.head(); }
 
    adjEntry lastAdj() const { return adjEntries.tail(); }
 
    node succ() const { return static_cast<node>(m_next); }
 
    node pred() const { return static_cast<node>(m_prev); }
 
 
    template<class ADJLIST>
    void allAdjEntries(ADJLIST& adjList) const {
        adjList.clear();
        for (adjEntry adj : this->adjEntries) {
            adjList.pushBack(adj);
        }
    }
 
 
    template<class EDGELIST>
    void adjEdges(EDGELIST& edgeList) const {
        edgeList.clear();
        for (adjEntry adj : this->adjEntries) {
            edgeList.pushBack(adj->theEdge());
        }
    }
 
 
    template<class EDGELIST>
    void inEdges(EDGELIST& edgeList) const;
 
 
    template<class EDGELIST>
    void outEdges(EDGELIST& edgeList) const;
 
#ifdef OGDF_DEBUG
    const Graph* graphOf() const { return m_pGraph; }
#endif
 
    static int compare(const NodeElement& x, const NodeElement& y) { return x.m_id - y.m_id; }
    OGDF_AUGMENT_STATICCOMPARER(NodeElement)
 
    OGDF_NEW_DELETE
};
 
inline adjEntry AdjElement::cyclicSucc() const {
    return (m_next) ? static_cast<adjEntry>(m_next) : m_node->firstAdj();
}
 
inline adjEntry AdjElement::cyclicPred() const {
    return (m_prev) ? static_cast<adjEntry>(m_prev) : m_node->lastAdj();
}
 
class OGDF_EXPORT EdgeElement : private internal::GraphElement {
    friend class Graph;
    friend class internal::GraphList<EdgeElement>;
 
    node m_src; 
    node m_tgt; 
    AdjElement* m_adjSrc; 
    AdjElement* m_adjTgt; 
    int m_id; // The (unique) index of the edge.
 
 
    EdgeElement(node src, node tgt, AdjElement* adjSrc, AdjElement* adjTgt, int id)
        : m_src(src), m_tgt(tgt), m_adjSrc(adjSrc), m_adjTgt(adjTgt), m_id(id) { }
 
 
    EdgeElement(node src, node tgt, int id)
        : m_src(src), m_tgt(tgt), m_adjSrc(nullptr), m_adjTgt(nullptr), m_id(id) { }
 
public:
    int index() const { return m_id; }
 
    node source() const { return m_src; }
 
    node target() const { return m_tgt; }
 
    std::array<node, 2> nodes() const { return std::array<node, 2> {{m_src, m_tgt}}; }
 
    adjEntry adjSource() const { return m_adjSrc; }
 
    adjEntry adjTarget() const { return m_adjTgt; }
 
    node opposite(node v) const {
        OGDF_ASSERT(isIncident(v));
        return v == m_src ? m_tgt : m_src;
    }
 
    bool isSelfLoop() const { return m_src == m_tgt; }
 
    bool isInvertedDirected(edge e) const { return m_src == e->target() && m_tgt == e->source(); }
 
    bool isParallelDirected(edge e) const { return m_src == e->source() && m_tgt == e->target(); }
 
    bool isParallelUndirected(edge e) const {
        return isParallelDirected(e) || isInvertedDirected(e);
    }
 
    edge succ() const { return static_cast<edge>(m_next); }
 
    edge pred() const { return static_cast<edge>(m_prev); }
 
#ifdef OGDF_DEBUG
    const Graph* graphOf() const { return m_src->graphOf(); }
#endif
 
    bool isIncident(node v) const { return v == m_src || v == m_tgt; }
 
    bool isAdjacent(edge e) const { return isIncident(e->m_src) || isIncident(e->m_tgt); }
 
    node commonNode(edge e) const {
        return (m_src == e->m_src || m_src == e->m_tgt)
                ? m_src
                : ((m_tgt == e->m_src || m_tgt == e->m_tgt) ? m_tgt : nullptr);
    }
 
    adjEntry getAdj(node v) const {
        OGDF_ASSERT(this->isIncident(v));
        return v == m_src ? m_adjSrc : m_adjTgt;
    }
 
    static int compare(const EdgeElement& x, const EdgeElement& y) { return x.m_id - y.m_id; }
    OGDF_AUGMENT_STATICCOMPARER(EdgeElement)
 
    OGDF_NEW_DELETE
 
#ifdef OGDF_DEBUG
private:
    bool m_hidden = false;
#endif
};
 
#ifdef OGDF_DEBUG
inline const Graph* AdjElement::graphOf() const { return m_node->graphOf(); }
#endif
 
inline bool AdjElement::isSource() const { return this == m_edge->adjSource(); }
 
inline bool AdjElement::isBetween(adjEntry adjBefore, adjEntry adjAfter) const {
#ifdef OGDF_DEBUG
    node v = this->theNode();
    OGDF_ASSERT(adjBefore->theNode() == v);
    OGDF_ASSERT(adjAfter->theNode() == v);
#endif
    bool result = this != adjBefore && this != adjAfter && adjBefore != adjAfter;
 
    if (result) {
        adjEntry adj = adjBefore;
        for (; adj != this && adj != adjAfter; adj = adj->cyclicSucc()) {
            ;
        }
        result = adj == this;
    }
 
    return result;
}
 
template<class EDGELIST>
void NodeElement::inEdges(EDGELIST& edgeList) const {
    edgeList.clear();
    for (adjEntry adj : this->adjEntries) {
        edge e = adj->theEdge();
        if (adj == e->adjTarget()) {
            edgeList.pushBack(e);
        }
    }
}
 
template<class EDGELIST>
void NodeElement::outEdges(EDGELIST& edgeList) const {
    edgeList.clear();
    for (adjEntry adj : this->adjEntries) {
        edge e = adj->theEdge();
        if (adj == e->adjSource()) {
            edgeList.pushBack(e);
        }
    }
}
 
class OGDF_EXPORT GraphAdjIterator {
    Graph* m_pGraph;
    adjEntry m_entry;
 
public:
    using iterator = GraphAdjIterator;
    using value_type = adjEntry;
 
    GraphAdjIterator(Graph* graph = nullptr, adjEntry entry = nullptr);
 
    GraphAdjIterator begin();
 
    GraphAdjIterator end() { return GraphAdjIterator(m_pGraph); }
 
    void next();
 
    void prev();
 
    adjEntry operator*() const { return m_entry; }
 
    AdjElement& operator->() const { return *m_entry; }
 
    bool operator==(const GraphAdjIterator& iter) const {
        return m_pGraph == iter.m_pGraph && m_entry == iter.m_entry;
    }
 
    bool operator!=(const GraphAdjIterator& iter) const { return !operator==(iter); }
 
    GraphAdjIterator& operator++() {
        next();
        return *this;
    }
 
    GraphAdjIterator operator++(int) {
        GraphAdjIterator iter = *this;
        next();
        return iter;
    }
 
    GraphAdjIterator& operator--() {
        prev();
        return *this;
    }
 
    GraphAdjIterator operator--(int) {
        GraphAdjIterator iter = *this;
        prev();
        return iter;
    }
};
 
namespace internal {
 
template<typename Key, typename Iterable = GraphObjectContainer<Key>, int Factor = 1>
class GraphRegistry
    : public RegistryBase<Key*, GraphRegistry<Key, Iterable, Factor>, typename Iterable::iterator> {
    Graph* m_pGraph;
    int* m_nextKeyIndex;
 
public:
    using iterator = typename Iterable::iterator;
 
    GraphRegistry(Graph* graph, int* nextKeyIndex)
        : m_pGraph(graph), m_nextKeyIndex(nextKeyIndex) { }
 
    static inline int keyToIndex(Key* key) { return key->index(); }
 
    bool isKeyAssociated(Key* key) const {
        if (key == nullptr) {
            return false;
        }
#ifdef OGDF_DEBUG
        if (key->graphOf() == m_pGraph) {
            OGDF_ASSERT(keyToIndex(key) < this->getArraySize());
            return true;
        } else {
            return false;
        }
#else
        return true;
#endif
    }
 
    int calculateArraySize(int add) const {
        return calculateTableSize((*m_nextKeyIndex + add) * Factor);
    }
 
    int maxKeyIndex() const { return ((*m_nextKeyIndex) * Factor) - 1; }
 
    Graph* graphOf() const { return m_pGraph; }
};
 
using GraphNodeRegistry = GraphRegistry<NodeElement>;
using GraphEdgeRegistry = GraphRegistry<EdgeElement>;
using GraphAdjRegistry = GraphRegistry<AdjElement, GraphAdjIterator, 2>;
 
#ifndef DOXYGEN_IGNORE
// doxygen has problems keeping these methods apart
OGDF_EXPORT GraphNodeRegistry::iterator begin(const GraphNodeRegistry&);
 
OGDF_EXPORT GraphNodeRegistry::iterator end(const GraphNodeRegistry&);
 
OGDF_EXPORT GraphEdgeRegistry::iterator begin(const GraphEdgeRegistry&);
 
OGDF_EXPORT GraphEdgeRegistry::iterator end(const GraphEdgeRegistry&);
 
OGDF_EXPORT GraphAdjRegistry::iterator begin(const GraphAdjRegistry&);
 
OGDF_EXPORT GraphAdjRegistry::iterator end(const GraphAdjRegistry&);
#endif
 
template<typename Key, typename Value, bool WithDefault, typename Registry = GraphRegistry<Key>>
class GraphRegisteredArray : public RegisteredArray<Registry, Value, WithDefault, Graph> {
    using RA = RegisteredArray<Registry, Value, WithDefault, Graph>;
 
public:
    using RA::RA;
 
    Graph* graphOf() const {
        if (RA::registeredAt() == nullptr) {
            return nullptr;
        } else {
            return RA::registeredAt()->graphOf();
        }
    }
};
 
template<typename Value, bool WithDefault>
class EdgeArrayBase1 : public GraphRegisteredArray<EdgeElement, Value, WithDefault> {
    using GRA = GraphRegisteredArray<EdgeElement, Value, WithDefault>;
 
public:
    using GRA::GRA;
 
    using GRA::operator[];
    using GRA::operator();
 
    const Value& operator[](adjEntry adj) const {
        OGDF_ASSERT(adj != nullptr);
        OGDF_ASSERT(GRA::getRegistry().isKeyAssociated(adj->theEdge()));
        return GRA::operator[](adj->index() >> 1);
    }
 
    Value& operator[](adjEntry adj) {
        OGDF_ASSERT(adj != nullptr);
        OGDF_ASSERT(GRA::getRegistry().isKeyAssociated(adj->theEdge()));
        return GRA::operator[](adj->index() >> 1);
    }
 
    const Value& operator()(adjEntry adj) const {
        OGDF_ASSERT(adj != nullptr);
        OGDF_ASSERT(GRA::getRegistry().isKeyAssociated(adj->theEdge()));
        return GRA::operator[](adj->index() >> 1);
    }
 
    Value& operator()(adjEntry adj) {
        OGDF_ASSERT(adj != nullptr);
        OGDF_ASSERT(GRA::getRegistry().isKeyAssociated(adj->theEdge()));
        return GRA::operator[](adj->index() >> 1);
    }
};
 
template<typename Value, bool WithDefault>
class EdgeArrayBase2 : public EdgeArrayBase1<Value, WithDefault> {
public:
    using EdgeArrayBase1<Value, WithDefault>::EdgeArrayBase1;
};
 
template<bool WithDefault>
class EdgeArrayBase2<edge, WithDefault> : public EdgeArrayBase1<edge, WithDefault> {
    using EA = EdgeArrayBase1<edge, WithDefault>;
 
public:
    using EA::EA;
 
    adjEntry mapEndpoint(adjEntry adj) const {
        OGDF_ASSERT(adj != nullptr);
        OGDF_ASSERT(EA::getRegistry().isKeyAssociated(adj->theEdge()));
        edge e = EA::operator[](adj->index() >> 1);
        return adj->isSource() ? e->adjSource() : e->adjTarget();
    }
};
}
 
#define OGDF_DECL_REG_ARRAY_TYPE(v, c) internal::GraphRegisteredArray<NodeElement, v, c>
OGDF_DECL_REG_ARRAY(NodeArray)
#undef OGDF_DECL_REG_ARRAY_TYPE
 
#define OGDF_DECL_REG_ARRAY_TYPE(v, c) internal::EdgeArrayBase2<v, c>
OGDF_DECL_REG_ARRAY(EdgeArray)
#undef OGDF_DECL_REG_ARRAY_TYPE
 
#define OGDF_DECL_REG_ARRAY_TYPE(v, c) \
    internal::GraphRegisteredArray<AdjElement, v, c, internal::GraphAdjRegistry>
OGDF_DECL_REG_ARRAY(AdjEntryArray)
#undef OGDF_DECL_REG_ARRAY_TYPE
 
template<bool>
class EdgeSet;
 
 
class OGDF_EXPORT GraphObserver : public Observer<Graph, GraphObserver> {
public:
    GraphObserver() = default;
 
    explicit GraphObserver(const Graph* G) { reregister(G); }
 
    virtual void nodeDeleted(node v) = 0;
 
    virtual void nodeAdded(node v) = 0;
 
    virtual void edgeDeleted(edge e) = 0;
 
    virtual void edgeAdded(edge e) = 0;
 
    virtual void cleared() = 0;
 
    const Graph* getGraph() const { return getObserved(); }
};
 
namespace internal {
template<typename CONTAINER>
inline void getAllNodes(const Graph& G, CONTAINER& nodes);
template<typename CONTAINER>
inline void getAllEdges(const Graph& G, CONTAINER& edges);
 
inline node adjToNode(adjEntry adj) { return adj->theNode(); }
 
inline node adjToNode(node n) { return n; }
}
 
OGDF_EXPORT bool filter_any_edge(edge e); // { return true; }
 
OGDF_EXPORT bool filter_any_node(node n); // { return true; }
 
 
class OGDF_EXPORT Graph : public Observable<GraphObserver, Graph> {
public:
    class CCsInfo; // IWYU pragma: keep
    class HiddenEdgeSet; // IWYU pragma: keep
 
    friend class GraphObserver;
 
private:
    int m_nodeIdCount; 
    int m_edgeIdCount; 
 
    internal::GraphNodeRegistry m_regNodeArrays; 
    internal::GraphEdgeRegistry m_regEdgeArrays; 
    internal::GraphAdjRegistry m_regAdjArrays; 
 
    List<HiddenEdgeSet*> m_hiddenEdgeSets; 
 
public:
 
    using node_iterator = internal::GraphIterator<node>;
    using edge_iterator = internal::GraphIterator<edge>;
    using adjEntry_iterator = internal::GraphIterator<adjEntry>;
 
 
 
    enum class EdgeType { association = 0, generalization = 1, dependency = 2 };
 
    enum class NodeType {
        vertex = 0,
        dummy = 1,
        generalizationMerger = 2,
        generalizationExpander = 3,
        highDegreeExpander = 4,
        lowDegreeExpander = 5,
        associationClass = 6
    };
 
 
 
 
    internal::GraphObjectContainer<NodeElement> nodes;
 
    internal::GraphObjectContainer<EdgeElement> edges;
 
 
 
    Graph();
 
 
    OGDF_COPY_CONSTR(Graph);
 
 
    OGDF_COPY_OP(Graph);
 
    OGDF_NO_MOVE(Graph);
 
    virtual ~Graph();
 
    OGDF_MALLOC_NEW_DELETE
 
 
    bool empty() const { return nodes.empty(); }
 
    int numberOfNodes() const { return nodes.size(); }
 
    int numberOfEdges() const { return edges.size(); }
 
    int maxNodeIndex() const { return m_nodeIdCount - 1; }
 
    int maxEdgeIndex() const { return m_edgeIdCount - 1; }
 
    int maxAdjEntryIndex() const { return (m_edgeIdCount << 1) - 1; }
 
    node firstNode() const { return nodes.head(); }
 
    node lastNode() const { return nodes.tail(); }
 
    edge firstEdge() const { return edges.head(); }
 
    edge lastEdge() const { return edges.tail(); }
 
    node chooseNode(
            std::function<bool(node)> includeNode = [](node) { return true; },
            bool isFastTest = true) const;
 
    edge chooseEdge(
            std::function<bool(edge)> includeEdge = [](edge) { return true; },
            bool isFastTest = true) const;
 
 
    template<class CONTAINER>
    void allNodes(CONTAINER& nodeContainer) const {
        internal::getAllNodes<CONTAINER>(*this, nodeContainer);
    }
 
 
    template<class CONTAINER>
    void allEdges(CONTAINER& edgeContainer) const {
        internal::getAllEdges<CONTAINER>(*this, edgeContainer);
    }
 
 
 
 
    node newNode(int index = -1) {
        node v = pureNewNode(index);
        m_regNodeArrays.keyAdded(v);
        for (GraphObserver* obs : getObservers()) {
            obs->nodeAdded(v);
        }
        return v;
    }
 
 
    inline edge newEdge(node v, node w, int index = -1) {
        return newEdge(v, Direction::after, w, Direction::after, index);
    }
 
 
    inline edge newEdge(node v, adjEntry adjTgt, int index = -1) {
        return newEdge(v, Direction::after, adjTgt, Direction::after, index);
    }
 
 
    inline edge newEdge(adjEntry adjSrc, node w, int index = -1) {
        return newEdge(adjSrc, Direction::after, w, Direction::after, index);
    }
 
 
    inline edge newEdge(adjEntry adjSrc, adjEntry adjTgt, Direction dir = Direction::after,
            int index = -1) {
        return newEdge(adjSrc, dir, adjTgt, dir, index);
    }
 
 
    template<typename S, typename T>
    edge newEdge(S src, Direction dirSrc, T tgt, Direction dirTgt, int index = -1) {
        OGDF_ASSERT(src != nullptr);
        OGDF_ASSERT(tgt != nullptr);
        edge e = pureNewEdge(internal::adjToNode(src), internal::adjToNode(tgt), index);
 
        insertAdjEntry(tgt, e->m_adjTgt, dirTgt);
        insertAdjEntry(src, e->m_adjSrc, dirSrc);
 
        m_regEdgeArrays.keyAdded(e);
        m_regAdjArrays.keyAdded(e->adjSource());
        for (GraphObserver* obs : getObservers()) {
            obs->edgeAdded(e);
        }
 
        return e;
    }
 
 
 
    virtual void delNode(node v);
 
    virtual void delEdge(edge e);
 
    virtual void clear();
 
    void restoreAllEdges();
 
 
    class OGDF_EXPORT HiddenEdgeSet {
        friend class Graph;
        friend class EdgeElement;
 
    public:
        explicit HiddenEdgeSet(Graph& graph) : m_graph(&graph) {
            m_it = m_graph->m_hiddenEdgeSets.pushFront(this);
        }
 
        ~HiddenEdgeSet() {
            if (m_graph) {
                restore();
                m_graph->m_hiddenEdgeSets.del(m_it);
            }
        }
 
        void hide(edge e);
 
        void restore(edge e);
 
        void restore();
 
        int size();
 
        bool empty();
 
        internal::GraphList<EdgeElement>::iterator begin();
 
        internal::GraphList<EdgeElement>::iterator end();
 
    private:
        internal::GraphList<EdgeElement> m_edges;
        ListIterator<HiddenEdgeSet*> m_it;
        Graph* m_graph;
 
        OGDF_NO_COPY(HiddenEdgeSet)
    };
 
 
 
    virtual edge split(edge e);
 
 
    void unsplit(node u);
 
 
    virtual void unsplit(edge eIn, edge eOut);
 
 
    node splitNode(adjEntry adjStartLeft, adjEntry adjStartRight);
 
 
    node contract(edge e, bool keepSelfLoops = false);
 
 
    void move(edge e, adjEntry adjSrc, Direction dirSrc, adjEntry adjTgt, Direction dirTgt);
 
 
    void moveTarget(edge e, node w);
 
 
    void moveTarget(edge e, adjEntry adjTgt, Direction dir);
 
 
    void moveSource(edge e, node w);
 
 
    void moveSource(edge e, adjEntry adjSrc, Direction dir);
 
 
    edge searchEdge(node v, node w, bool directed = false) const;
 
    void reverseEdge(edge e);
 
    void reverseAllEdges();
 
 
    template<class NODELIST>
    void collapse(NODELIST& nodesToCollapse) {
        node v = nodesToCollapse.popFrontRet();
        while (!nodesToCollapse.empty()) {
            node w = nodesToCollapse.popFrontRet();
            adjEntry adj = w->firstAdj();
            while (adj != nullptr) {
                adjEntry succ = adj->succ();
                edge e = adj->theEdge();
                if (e->source() == v || e->target() == v) {
                    delEdge(e);
                } else if (e->source() == w) {
                    moveSource(e, v);
                } else {
                    moveTarget(e, v);
                }
                adj = succ;
            }
            delNode(w);
        }
    }
 
 
    template<class ADJ_ENTRY_LIST>
    void sort(node v, const ADJ_ENTRY_LIST& newOrder) {
        using std::begin;
        using std::end;
        sort(v, begin(newOrder), end(newOrder));
    }
 
 
    template<class IT>
    void sort(node v, IT begin, IT end) {
#ifdef OGDF_DEBUG
        std::set<int> entries;
        int counter = 0;
 
        for (auto it = begin; it != end; ++it) {
            adjEntry adj = *it;
            entries.insert(adj->index());
            OGDF_ASSERT(adj->theNode() == v);
            counter++;
        }
 
        OGDF_ASSERT(counter == v->degree());
        OGDF_ASSERT(entries.size() == static_cast<unsigned int>(v->degree()));
#endif
        v->adjEntries.sort(begin, end);
    }
 
 
    void reverseAdjEdges(node v) { v->adjEntries.reverse(); }
 
 
    void moveAdj(adjEntry adjMove, Direction dir, adjEntry adjPos) {
        OGDF_ASSERT(adjMove != nullptr);
        OGDF_ASSERT(adjPos != nullptr);
        OGDF_ASSERT(adjMove->graphOf() == this);
        OGDF_ASSERT(adjPos->graphOf() == this);
        internal::GraphList<AdjElement>& adjList = adjMove->m_node->adjEntries;
        adjList.move(adjMove, adjList, adjPos, dir);
    }
 
 
    void moveAdjAfter(adjEntry adjMove, adjEntry adjAfter) {
        OGDF_ASSERT(adjMove != nullptr);
        OGDF_ASSERT(adjAfter != nullptr);
        OGDF_ASSERT(adjMove->graphOf() == this);
        OGDF_ASSERT(adjAfter->graphOf() == this);
        adjMove->m_node->adjEntries.moveAfter(adjMove, adjAfter);
    }
 
 
    void moveAdjBefore(adjEntry adjMove, adjEntry adjBefore) {
        OGDF_ASSERT(adjMove != nullptr);
        OGDF_ASSERT(adjBefore != nullptr);
        OGDF_ASSERT(adjMove->graphOf() == this);
        OGDF_ASSERT(adjBefore->graphOf() == this);
        adjMove->m_node->adjEntries.moveBefore(adjMove, adjBefore);
    }
 
    void reverseAdjEdges();
 
 
    void swapAdjEdges(adjEntry adj1, adjEntry adj2) {
        OGDF_ASSERT(adj1->theNode() == adj2->theNode());
        OGDF_ASSERT(adj1->graphOf() == this);
 
        adj1->theNode()->adjEntries.swap(adj1, adj2);
    }
 
 
 
 
    int genus() const;
 
 
    bool representsCombEmbedding() const { return genus() == 0; }
 
#ifdef OGDF_DEBUG
    void consistencyCheck() const;
#endif
 
 
 
    internal::GraphNodeRegistry& nodeRegistry() { return m_regNodeArrays; }
 
    const internal::GraphNodeRegistry& nodeRegistry() const { return m_regNodeArrays; }
 
    operator const internal::GraphNodeRegistry&() const { return m_regNodeArrays; }
 
    internal::GraphEdgeRegistry& edgeRegistry() { return m_regEdgeArrays; }
 
    const internal::GraphEdgeRegistry& edgeRegistry() const { return m_regEdgeArrays; }
 
    operator const internal::GraphEdgeRegistry&() const { return m_regEdgeArrays; }
 
    internal::GraphAdjRegistry& adjEntryRegistry() { return m_regAdjArrays; }
 
    const internal::GraphAdjRegistry& adjEntryRegistry() const { return m_regAdjArrays; }
 
    operator const internal::GraphAdjRegistry&() const { return m_regAdjArrays; }
 
 
    void resetEdgeIdCount(int maxId);
 
    void resetNodeIdCount(int maxId);
 
 
 
 
    template<OGDF_NODE_ITER NI, OGDF_EDGE_ITER EI, bool copyEmbedding = true, bool copyIDs = false,
            bool notifyObservers = true>
    std::pair<int, int> insert(const NI& nodesBegin, const NI& nodesEnd, const EI& edgesBegin,
            const EI& edgesEnd, NodeArray<node>& nodeMap, EdgeArray<edge>& edgeMap);
 
    template<OGDF_NODE_ITER NI, OGDF_EDGE_FILTER EF, bool copyIDs = false, bool notifyObservers = true>
    std::pair<int, int> insert(const NI& nodesBegin, const NI& nodesEnd, const EF& edgeFilter,
            NodeArray<node>& nodeMap, EdgeArray<edge>& edgeMap);
 
    // List short-cuts
 
    template<OGDF_NODE_LIST NL>
    std::pair<int, int> insert(const NL& nodeList, const EdgeSet<true>& edgeSet,
            NodeArray<node>& nodeMap, EdgeArray<edge>& edgeMap);
 
    template<OGDF_NODE_LIST NL>
    std::pair<int, int> insert(const NL& nodeList, const EdgeSet<false>& edgeSet,
            NodeArray<node>& nodeMap, EdgeArray<edge>& edgeMap);
 
    template<OGDF_NODE_LIST NL, OGDF_EDGE_LIST EL>
    std::pair<int, int> insert(const NL& nodeList, const EL& edgeList, NodeArray<node>& nodeMap,
            EdgeArray<edge>& edgeMap) {
        m_regNodeArrays.reserveSpace(nodeList.size());
        m_regEdgeArrays.reserveSpace(edgeList.size());
        m_regAdjArrays.reserveSpace(edgeList.size());
        using std::begin;
        using std::end;
        return insert(begin(nodeList), end(nodeList), begin(edgeList), end(edgeList), nodeMap,
                edgeMap);
    }
 
    // Often-used special cases
 
    std::pair<int, int> insert(const CCsInfo& info, int cc, NodeArray<node>& nodeMap,
            EdgeArray<edge>& edgeMap) {
        OGDF_ASSERT(&(info.constGraph()) == nodeMap.registeredAt()->graphOf());
        OGDF_ASSERT(&(info.constGraph()) == edgeMap.registeredAt()->graphOf());
        m_regNodeArrays.reserveSpace(info.numberOfNodes(cc));
        m_regEdgeArrays.reserveSpace(info.numberOfEdges(cc));
        m_regAdjArrays.reserveSpace(info.numberOfEdges(cc));
        auto count = insert(info.nodes(cc).begin(), info.nodes(cc).end(), filter_any_edge, nodeMap,
                edgeMap);
        OGDF_ASSERT(count.first == info.numberOfNodes(cc));
        OGDF_ASSERT(count.second == info.numberOfEdges(cc));
        return count;
    }
 
    std::pair<int, int> insert(const Graph& G, NodeArray<node>& nodeMap, EdgeArray<edge>& edgeMap) {
        if (!nodeMap.registeredAt()) {
            nodeMap.init(G);
        }
        OGDF_ASSERT(nodeMap.registeredAt()->graphOf() == &G);
        if (!edgeMap.registeredAt()) {
            edgeMap.init(G);
        }
        OGDF_ASSERT(edgeMap.registeredAt()->graphOf() == &G);
        m_regNodeArrays.reserveSpace(G.numberOfNodes());
        m_regEdgeArrays.reserveSpace(G.numberOfEdges());
        m_regAdjArrays.reserveSpace(G.numberOfEdges());
        auto count = insert(G.nodes.begin(), G.nodes.end(), filter_any_edge, nodeMap, edgeMap);
        OGDF_ASSERT(count.first == G.numberOfNodes());
        OGDF_ASSERT(count.second == G.numberOfEdges());
        return count;
    }
 
    std::pair<int, int> insert(const Graph& G) {
        NodeArray<node> nodeMap(G, nullptr);
        EdgeArray<edge> edgeMap(G, nullptr);
        return insert(G, nodeMap, edgeMap);
    }
 
private:
    template<OGDF_NODE_ITER NI, bool notifyObservers, bool copyIDs>
    void insertNodes(const NI& nodesBegin, const NI& nodesEnd, NodeArray<node, true>& nodeMap,
            int& newNodes, void* cbData);
 
protected:
    virtual void* preInsert(bool copyEmbedding, bool copyIDs, bool notifyObservers, bool edgeFilter,
            NodeArray<node>& nodeMap, EdgeArray<edge>& edgeMap, int* newNodes, int* newEdges) {
        return nullptr;
    };
 
    virtual void nodeInserted(void* userData, node original, node copy) {};
 
    virtual void edgeInserted(void* userData, edge original, edge copy) {};
 
    virtual void postInsert(void* userData, int newNodes, int newEdges) {};
 
public:
    class OGDF_EXPORT CCsInfo {
        const Graph* m_graph; 
        int m_numCC; 
 
        Array<node> m_nodes; 
        Array<edge> m_edges; 
        Array<int> m_startNode; 
        Array<int> m_startEdge; 
 
    public:
        CCsInfo() : m_graph(nullptr), m_numCC(0) { }
 
        explicit CCsInfo(const Graph& G);
 
        const Graph& constGraph() const { return *m_graph; }
 
        int numberOfCCs() const { return m_numCC; }
 
        int numberOfNodes(int cc) const { return stopNode(cc) - startNode(cc); }
 
        int numberOfEdges(int cc) const { return stopEdge(cc) - startEdge(cc); }
 
        int startNode(int cc) const { return m_startNode[cc]; }
 
        int stopNode(int cc) const { return m_startNode[cc + 1]; }
 
        internal::SimpleRange<Array<node>::const_iterator> nodes(int cc) const {
            return {m_nodes.begin() + startNode(cc), m_nodes.begin() + stopNode(cc)};
        }
 
        internal::SimpleRange<Array<edge>::const_iterator> edges(int cc) const {
            return {m_edges.begin() + startEdge(cc), m_edges.begin() + stopEdge(cc)};
        }
 
        int startEdge(int cc) const { return m_startEdge[cc]; }
 
        int stopEdge(int cc) const { return m_startEdge[cc + 1]; }
 
        node v(int i) const { return m_nodes[i]; }
 
        edge e(int i) const { return m_edges[i]; }
    };
 
private:
    inline node pureNewNode(int index) {
        if (index < 0) {
            index = m_nodeIdCount++;
        } else {
            m_nodeIdCount = max(m_nodeIdCount, index + 1);
        }
 
        // simple check against illegal index reuse
        OGDF_ASSERT(nodes.empty() || index != nodes.head()->index());
        OGDF_ASSERT(nodes.empty() || index != nodes.tail()->index());
 
#ifdef OGDF_DEBUG
        node v = new NodeElement(this, index);
#else
        node v = new NodeElement(index);
#endif
        nodes.pushBack(v);
        return v;
    }
 
    edge pureNewEdge(node src, node tgt, int index) {
        OGDF_ASSERT(src != nullptr);
        OGDF_ASSERT(tgt != nullptr);
        OGDF_ASSERT(src->graphOf() == this);
        OGDF_ASSERT(tgt->graphOf() == this);
 
        if (index < 0) {
            index = m_edgeIdCount++;
        } else {
            m_edgeIdCount = max(m_edgeIdCount, index + 1);
        }
 
        // simple check against illegal index reuse
        OGDF_ASSERT(edges.empty() || index != edges.head()->index());
        OGDF_ASSERT(edges.empty() || index != edges.tail()->index());
 
        edge e = new EdgeElement(src, tgt, index);
        edges.pushBack(e);
 
        e->m_adjSrc = new AdjElement(e, index << 1);
        e->m_adjTgt = new AdjElement(e, (index << 1) | 1);
 
        e->m_adjSrc->m_twin = e->m_adjTgt;
        e->m_adjSrc->m_node = src;
        src->m_outdeg++;
 
        e->m_adjTgt->m_twin = e->m_adjSrc;
        e->m_adjTgt->m_node = tgt;
        tgt->m_indeg++;
 
        return e;
    }
 
    static inline void insertAdjEntry(adjEntry oldAdj, adjEntry newAdj, Direction dir) {
        if (dir == Direction::after) {
            oldAdj->theNode()->adjEntries.insertAfter(newAdj, oldAdj);
        } else {
            oldAdj->theNode()->adjEntries.insertBefore(newAdj, oldAdj);
        }
    }
 
    static inline void insertAdjEntry(node n, adjEntry newAdj, Direction dir) {
        if (dir == Direction::after || n->adjEntries.empty()) {
            n->adjEntries.pushBack(newAdj);
        } else {
            n->adjEntries.insertBefore(newAdj, n->adjEntries.head());
        }
    }
 
    void moveAdj(adjEntry adj, node w);
};
 
OGDF_EXPORT std::ostream& operator<<(std::ostream& os, const Graph::EdgeType& et);
 
class OGDF_EXPORT BucketSourceIndex : public BucketFunc<edge> {
public:
    int getBucket(const edge& e) override { return e->source()->index(); }
};
 
class OGDF_EXPORT BucketTargetIndex : public BucketFunc<edge> {
public:
    int getBucket(const edge& e) override { return e->target()->index(); }
};
 
namespace internal {
 
template<typename CONTAINER>
inline void getAllNodes(const Graph& G, CONTAINER& nodes) {
    nodes.clear();
    for (node v : G.nodes) {
        nodes.pushBack(v);
    }
}
 
template<>
inline void getAllNodes(const Graph& G, Array<node>& nodes) {
    nodes.init(G.numberOfNodes());
    int i = 0;
    for (node v : G.nodes) {
        nodes[i++] = v;
    }
}
 
template<typename CONTAINER>
inline void getAllEdges(const Graph& G, CONTAINER& edges) {
    edges.clear();
    for (edge v : G.edges) {
        edges.pushBack(v);
    }
}
 
template<>
inline void getAllEdges(const Graph& G, Array<edge>& edges) {
    edges.init(G.numberOfEdges());
    int i = 0;
    for (edge v : G.edges) {
        edges[i++] = v;
    }
}
 
}
 
struct NodePair {
    node source = nullptr;
    node target = nullptr;
    NodePair() = default;
 
    NodePair(node src, node tgt) : source(src), target(tgt) { }
};
 
inline std::ostream& operator<<(std::ostream& os, const NodePair& np) {
    os << "(" << np.source << "," << np.target << ")";
    return os;
}
 
}
 
#include <ogdf/basic/InducedSubgraph.h>