Graph_d.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/internal/graph_iterators.h>
 
#include <array>
#include <mutex>
 
#ifdef OGDF_DEBUG
#   include <set>
#endif
 
namespace ogdf {
 
//
// in embedded graphs, adjacency lists are given in clockwise order.
//
 
 
class OGDF_EXPORT Graph;
class OGDF_EXPORT NodeElement;
class OGDF_EXPORT EdgeElement;
class OGDF_EXPORT AdjElement;
class OGDF_EXPORT FaceElement;
class OGDF_EXPORT ClusterElement;
 
 
using node = NodeElement*;
 
using edge = EdgeElement*;
 
using adjEntry = AdjElement*;
 
 
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 node.
 
 
    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 NodeArrayBase;
class EdgeArrayBase;
class AdjEntryArrayBase;
template<class T>
class NodeArray;
template<class T>
class EdgeArray;
template<class T>
class AdjEntryArray;
class OGDF_EXPORT GraphObserver;
 
namespace internal {
template<typename CONTAINER>
inline void getAllNodes(const Graph& G, CONTAINER& nodes);
template<typename CONTAINER>
inline void getAllEdges(const Graph& G, CONTAINER& edges);
}
 
 
class OGDF_EXPORT Graph {
public:
    class HiddenEdgeSet;
 
private:
    int m_nodeIdCount; 
    int m_edgeIdCount; 
 
    int m_nodeArrayTableSize; 
    int m_edgeArrayTableSize; 
 
    mutable ListPure<NodeArrayBase*> m_regNodeArrays; 
    mutable ListPure<EdgeArrayBase*> m_regEdgeArrays; 
    mutable ListPure<AdjEntryArrayBase*> m_regAdjArrays; 
    mutable ListPure<GraphObserver*> m_regStructures; 
 
#ifndef OGDF_MEMORY_POOL_NTS
    mutable std::mutex m_mutexRegArrays; 
#endif
 
    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();
 
 
    Graph(const Graph& G);
 
    virtual ~Graph();
 
 
    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; }
 
    int nodeArrayTableSize() const { return m_nodeArrayTableSize; }
 
    int edgeArrayTableSize() const { return m_edgeArrayTableSize; }
 
    int adjEntryArrayTableSize() const { return m_edgeArrayTableSize << 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();
 
 
    node newNode(int index);
 
 
    edge newEdge(node v, node w);
 
 
    edge newEdge(node v, node w, int index);
 
 
    edge newEdge(adjEntry adjSrc, adjEntry adjTgt, Direction dir = Direction::after);
 
 
    edge newEdge(node v, adjEntry adjTgt);
 
 
    edge newEdge(adjEntry adjSrc, node w);
 
 
 
 
    virtual void delNode(node v);
 
    virtual void delEdge(edge e);
 
    virtual void clear();
 
 
    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();
 
    private:
        internal::GraphList<EdgeElement> m_edges;
        ListIterator<HiddenEdgeSet*> m_it;
        Graph* m_graph;
 
        // prevent copying
        HiddenEdgeSet(const HiddenEdgeSet&);
        HiddenEdgeSet& operator=(const HiddenEdgeSet&);
    };
 
 
    void insert(const Graph& G, NodeArray<node>& nodeMap);
 
 
    void insert(const Graph& G);
 
 
    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) {
#ifdef OGDF_DEBUG
        std::set<int> entries;
        int counter = 0;
 
        for (adjEntry adj : newOrder) {
            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(newOrder);
    }
 
 
    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
 
 
 
 
    ListIterator<NodeArrayBase*> registerArray(NodeArrayBase* pNodeArray) const;
 
 
    ListIterator<EdgeArrayBase*> registerArray(EdgeArrayBase* pEdgeArray) const;
 
 
    ListIterator<AdjEntryArrayBase*> registerArray(AdjEntryArrayBase* pAdjArray) const;
 
 
    ListIterator<GraphObserver*> registerStructure(GraphObserver* pStructure) const;
 
 
    void unregisterArray(ListIterator<NodeArrayBase*> it) const;
 
 
    void unregisterArray(ListIterator<EdgeArrayBase*> it) const;
 
 
    void unregisterArray(ListIterator<AdjEntryArrayBase*> it) const;
 
 
    void unregisterStructure(ListIterator<GraphObserver*> it) const;
 
    template<class ArrayBase>
    void moveRegisterArray(ListIterator<ArrayBase*> it, ArrayBase* pArray) const {
#ifndef OGDF_MEMORY_POOL_NTS
        std::lock_guard<std::mutex> guard(m_mutexRegArrays);
#endif
        *it = pArray;
    }
 
 
    void resetEdgeIdCount(int maxId);
 
 
 
 
    Graph& operator=(const Graph& G);
 
    OGDF_MALLOC_NEW_DELETE
 
 
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]; }
 
        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]; }
    };
 
protected:
    void construct(const Graph& G, NodeArray<node>& mapNode, EdgeArray<edge>& mapEdge);
 
    void assign(const Graph& G, NodeArray<node>& mapNode, EdgeArray<edge>& mapEdge);
 
 
    void constructInitByNodes(const Graph& G, const List<node>& nodeList, NodeArray<node>& mapNode,
            EdgeArray<edge>& mapEdge);
 
    void constructInitByActiveNodes(const List<node>& nodeList, const NodeArray<bool>& activeNodes,
            NodeArray<node>& mapNode, EdgeArray<edge>& mapEdge);
 
    void constructInitByCC(const CCsInfo& info, int cc, NodeArray<node>& mapNode,
            EdgeArray<edge>& mapEdge);
 
private:
    void copy(const Graph& G, NodeArray<node>& mapNode, EdgeArray<edge>& mapEdge);
    void copy(const Graph& G);
 
    edge createEdgeElement(node v, node w, adjEntry adjSrc, adjEntry adjTgt);
    node pureNewNode();
 
    // moves adjacency entry to node w
    void moveAdj(adjEntry adj, node w);
 
    void resetTableSizes();
 
    void reinitArrays(bool doResetTableSizes = true);
    void resetAdjEntryIndex(int newIndex, int oldIndex);
 
    void restoreAllEdges();
};
 
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;
}
 
}