Hypergraph.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/Observer.h>
#include <ogdf/basic/RegisteredArray.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/memory.h>
 
#include <iosfwd>
#include <string>
 
namespace ogdf {
template<class E>
class List;
} // namespace ogdf
 
#define forall_adj_elements(adj, ge) for ((adj) = (v)->firstAdj(); (adj); (adj) = (adj)->succ())
 
#define forall_hypernodes(v, H) for ((v) = (H).firstHypernode(); (v); (v) = (v)->succ())
 
#define forall_rev_hypernodes(v, H) for ((v) = (H).lastHypernode(); (v); (v) = (v)->pred())
 
#define forall_hyperedges(e, H) for ((e) = (H).firstHyperedge(); (e); (e) = (e)->succ())
 
#define forall_rev_hyperedges(e, H) for ((e) = (H).lastHyperedge(); (e); (e) = (e)->pred())
 
namespace ogdf {
 
class OGDF_EXPORT AdjHypergraphElement; // IWYU pragma: keep
class OGDF_EXPORT HyperedgeElement; // IWYU pragma: keep
class OGDF_EXPORT Hypergraph; // IWYU pragma: keep
class OGDF_EXPORT HypernodeElement; // IWYU pragma: keep
 
using hypernode = HypernodeElement*;
 
using hyperedge = HyperedgeElement*;
 
using adjHypergraphEntry = AdjHypergraphElement*;
 
 
class OGDF_EXPORT AdjHypergraphElement : private internal::GraphElement {
    friend class Hypergraph;
    friend class GraphListBase;
    friend class internal::GraphList<AdjHypergraphElement>;
 
private:
    GraphElement* m_element;
 
 
    adjHypergraphEntry m_twin;
 
    int m_index;
 
    explicit AdjHypergraphElement(GraphElement* pElement)
        : m_element(pElement), m_twin(nullptr), m_index(0) { }
 
    AdjHypergraphElement(GraphElement* pElement, int pIndex)
        : m_element(pElement), m_twin(nullptr), m_index(pIndex) { }
 
public:
    int index() const { return m_index; }
 
 
    GraphElement* element() const { return m_element; }
 
    adjHypergraphEntry twin() const { return m_twin; }
 
    adjHypergraphEntry succ() const { return static_cast<adjHypergraphEntry>(m_next); }
 
    adjHypergraphEntry pred() const { return static_cast<adjHypergraphEntry>(m_prev); }
 
    adjHypergraphEntry cyclicSucc() const;
 
    adjHypergraphEntry cyclicPred() const;
 
    OGDF_NEW_DELETE;
};
 
class OGDF_EXPORT HyperedgeElement : private internal::GraphElement {
    friend class Hypergraph;
    friend class GraphListBase;
    friend class internal::GraphList<HyperedgeElement>;
 
private:
    internal::GraphList<AdjHypergraphElement> m_adjHypernodes;
 
    int m_index;
 
    int m_cardinality;
 
    Hypergraph* m_hypergraph;
 
 
    explicit HyperedgeElement(int pIndex)
        : m_index(pIndex), m_cardinality(0), m_hypergraph(nullptr) { }
 
public:
    int index() const { return m_index; }
 
    int cardinality() const { return m_cardinality; }
 
    Hypergraph* hypergraph() const { return m_hypergraph; }
 
    adjHypergraphEntry firstAdj() const { return m_adjHypernodes.head(); }
 
    adjHypergraphEntry lastAdj() const { return m_adjHypernodes.tail(); }
 
    internal::GraphList<AdjHypergraphElement> incidentHypernodes() const { return m_adjHypernodes; }
 
    template<class NODELIST>
    void allHypernodes(NODELIST& hypernodes) const {
        hypernodes.clear();
        for (adjHypergraphEntry adj = firstAdj(); adj; adj = adj->succ()) {
            hypernodes.pushBack(reinterpret_cast<hypernode>(adj->element()));
        }
    }
 
    bool incident(hypernode v) const {
        for (adjHypergraphEntry adj = firstAdj(); adj; adj = adj->succ()) {
            if (reinterpret_cast<hypernode>(adj->element()) == v) {
                return true;
            }
        }
        return false;
    }
 
    hyperedge succ() const { return static_cast<hyperedge>(m_next); }
 
    hyperedge pred() const { return static_cast<hyperedge>(m_prev); }
 
    bool operator==(const hyperedge e) const {
        return e->index() == m_index && e->hypergraph() == m_hypergraph;
    }
 
    friend std::ostream& operator<<(std::ostream& os, ogdf::hyperedge e);
 
    OGDF_NEW_DELETE;
};
 
class OGDF_EXPORT HypernodeElement : private internal::GraphElement {
    friend class Hypergraph;
    friend class GraphListBase;
    friend class internal::GraphList<HypernodeElement>;
 
public:
    enum class Type {
        normal = 0x0000001, 
        dummy = 0x0000002, 
        OR = 0x0000003, 
        BUF = 0x0000004, 
        AND = 0x0000005, 
        NOR = 0x0000006, 
        NOT = 0x0000007, 
        XOR = 0x0000008, 
        DFF = 0x0000009, 
        NAND = 0x0000010, 
        INPUT = 0x0000011, 
        OUTPUT = 0x0000012 
    };
 
private:
    internal::GraphList<AdjHypergraphElement> m_adjHyperedges;
 
    int m_index;
 
    int m_degree;
 
    Type m_type;
 
    Hypergraph* m_hypergraph;
 
    explicit HypernodeElement(int pIndex)
        : m_index(pIndex), m_degree(0), m_type(Type::normal), m_hypergraph(nullptr) { }
 
    HypernodeElement(int pIndex, Type pType)
        : m_index(pIndex), m_degree(0), m_type(pType), m_hypergraph(nullptr) { }
 
public:
    int index() const { return m_index; }
 
    int degree() const { return m_degree; }
 
    Hypergraph* hypergraph() const { return m_hypergraph; }
 
    Type type() const { return m_type; }
 
    void type(Type pType) { m_type = pType; }
 
    adjHypergraphEntry firstAdj() const { return m_adjHyperedges.head(); }
 
    adjHypergraphEntry lastAdj() const { return m_adjHyperedges.tail(); }
 
    template<class NODELIST>
    void allHyperedges(NODELIST& hyperedges) const {
        hyperedges.clear();
        for (adjHypergraphEntry adj = firstAdj(); adj; adj = adj->succ()) {
            hyperedges.pushBack(reinterpret_cast<hyperedge>(adj->element()));
        }
    }
 
    bool adjacent(hypernode v) const {
        for (adjHypergraphEntry adj = firstAdj(); adj; adj = adj->succ()) {
            if (reinterpret_cast<hyperedge>(adj->element())->incident(v)) {
                return true;
            }
        }
        return false;
    }
 
    hypernode succ() const { return static_cast<hypernode>(m_next); }
 
    hypernode pred() const { return static_cast<hypernode>(m_prev); }
 
    bool operator==(const hypernode v) const {
        return v->index() == m_index && v->hypergraph() == m_hypergraph;
    }
 
    OGDF_NEW_DELETE;
};
 
template<typename Key>
class HypergraphRegistry
    : public RegistryBase<Key*, HypergraphRegistry<Key>, internal::GraphIterator<Key*>> {
    Hypergraph* m_pGraph;
    int* m_nextKeyIndex;
 
public:
    using iterator = internal::GraphIterator<Key*>;
 
    HypergraphRegistry(Hypergraph* 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->hypergraph() == 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); }
 
    int maxKeyIndex() const { return (*m_nextKeyIndex) - 1; }
 
    Hypergraph* graphOf() const { return m_pGraph; }
};
 
OGDF_EXPORT HypergraphRegistry<HypernodeElement>::iterator begin(
        const HypergraphRegistry<HypernodeElement>& self);
 
OGDF_EXPORT HypergraphRegistry<HypernodeElement>::iterator end(
        const HypergraphRegistry<HypernodeElement>& self);
 
OGDF_EXPORT HypergraphRegistry<HyperedgeElement>::iterator begin(
        const HypergraphRegistry<HyperedgeElement>& self);
 
OGDF_EXPORT HypergraphRegistry<HyperedgeElement>::iterator end(
        const HypergraphRegistry<HyperedgeElement>& self);
 
template<typename Key, typename Value, bool WithDefault, typename Registry = HypergraphRegistry<Key>>
class HypergraphRegisteredArray : public RegisteredArray<Registry, Value, WithDefault, Hypergraph> {
    using RA = RegisteredArray<Registry, Value, WithDefault, Hypergraph>;
 
public:
    using RA::RA;
 
    Hypergraph* hypergraphOf() const {
        if (RA::registeredAt() == nullptr) {
            return nullptr;
        } else {
            return RA::registeredAt()->graphOf();
        }
    }
};
 
#define OGDF_DECL_REG_ARRAY_TYPE(v, c) HypergraphRegisteredArray<HypernodeElement, v, c>
OGDF_DECL_REG_ARRAY(HypernodeArray)
#undef OGDF_DECL_REG_ARRAY_TYPE
 
#define OGDF_DECL_REG_ARRAY_TYPE(v, c) HypergraphRegisteredArray<HyperedgeElement, v, c>
OGDF_DECL_REG_ARRAY(HyperedgeArray)
#undef OGDF_DECL_REG_ARRAY_TYPE
 
class OGDF_EXPORT HypergraphObserver;
 
class OGDF_EXPORT Hypergraph : public Observable<HypergraphObserver, Hypergraph> {
    HypergraphRegistry<HypernodeElement> m_regHypernodeArrays;
 
    HypergraphRegistry<HyperedgeElement> m_regHyperedgeArrays;
 
    internal::GraphList<HypernodeElement> m_hypernodes;
 
    internal::GraphList<HyperedgeElement> m_hyperedges;
 
    int m_nHypernodes;
 
    int m_nHyperedges;
 
    int m_hypernodeIdCount;
 
    int m_hyperedgeIdCount;
 
public:
    Hypergraph();
 
    Hypergraph(const Hypergraph& H);
 
    ~Hypergraph();
 
    bool empty() const { return m_nHypernodes == 0; }
 
    const internal::GraphList<HypernodeElement>& hypernodes() const { return m_hypernodes; }
 
    const internal::GraphList<HyperedgeElement>& hyperedges() const { return m_hyperedges; }
 
    int numberOfHypernodes() const { return m_nHypernodes; }
 
    int numberOfHyperedges() const { return m_nHyperedges; }
 
    int maxHypernodeIndex() const { return m_hypernodeIdCount - 1; }
 
    int maxHyperedgeIndex() const { return m_hyperedgeIdCount - 1; }
 
    hypernode firstHypernode() const { return m_hypernodes.head(); }
 
    hypernode lastHypernode() const { return m_hypernodes.tail(); }
 
    hyperedge firstHyperedge() const { return m_hyperedges.head(); }
 
    hyperedge lastHyperEdge() const { return m_hyperedges.tail(); }
 
    hypernode newHypernode();
 
    hypernode newHypernode(int pIndex);
 
    hypernode newHypernode(HypernodeElement::Type pType);
 
    hypernode newHypernode(int pIndex, HypernodeElement::Type pType);
 
 
    hyperedge newHyperedge(List<hypernode>& hypernodes);
 
 
    hyperedge newHyperedge(int pIndex, List<hypernode>& hypernodes);
 
 
    void delHypernode(hypernode v);
 
 
    void delHyperedge(hyperedge e);
 
    void clear();
 
    hypernode randomHypernode() const;
 
    hyperedge randomHyperedge() const;
 
    template<class LIST>
    void allHypernodes(LIST& hypernodeList) const {
        hypernodeList.clear();
        for (hypernode v = m_hypernodes.head(); v; v = v->succ()) {
            hypernodeList.pushBack(v);
        }
    }
 
    template<class LIST>
    void allHyperedges(LIST& hyperedgeList) const {
        hyperedgeList.clear();
        for (hyperedge e = m_hyperedges.head(); e; e = e->succ()) {
            hyperedgeList.pushBack(e);
        }
    }
 
    void readBenchHypergraph(std::istream& is);
 
    void readBenchHypergraph(const char* filename);
 
    void readPlaHypergraph(std::istream& is);
 
    void loadPlaHypergraph(const char* fileName);
 
    bool consistency() const;
 
    HypergraphRegistry<HypernodeElement>& hypernodeRegistry() { return m_regHypernodeArrays; }
 
    const HypergraphRegistry<HypernodeElement>& hypernodeRegistry() const {
        return m_regHypernodeArrays;
    }
 
    operator const HypergraphRegistry<HypernodeElement>&() const { return m_regHypernodeArrays; }
 
    HypergraphRegistry<HyperedgeElement>& hyperedgeRegistry() { return m_regHyperedgeArrays; }
 
    const HypergraphRegistry<HyperedgeElement>& hyperedgeRegistry() const {
        return m_regHyperedgeArrays;
    }
 
    operator const HypergraphRegistry<HyperedgeElement>&() const { return m_regHyperedgeArrays; }
 
    Hypergraph& operator=(const Hypergraph& H);
 
    friend std::ostream& operator<<(std::ostream& os, ogdf::Hypergraph& H);
 
    friend std::istream& operator>>(std::istream& is, ogdf::Hypergraph& H);
 
    OGDF_MALLOC_NEW_DELETE;
 
private:
    void initArrays();
 
    int nextEntry(char* buffer, int from, string stop);
 
    HypernodeElement::Type gateType(string gate);
};
 
}