Hypergraph.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
 
#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 Hypergraph;
class OGDF_EXPORT HypernodeElement;
class OGDF_EXPORT HyperedgeElement;
class OGDF_EXPORT AdjHypergraphElement;
 
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;
};
 
class HypergraphArrayBase;
template<class T>
class HypernodeArray;
template<class T>
class HyperedgeArray;
class OGDF_EXPORT HypergraphObserver;
 
class OGDF_EXPORT Hypergraph {
    internal::GraphList<HypernodeElement> m_hypernodes;
 
    internal::GraphList<HyperedgeElement> m_hyperedges;
 
    int m_nHypernodes;
 
    int m_nHyperedges;
 
    int m_hypernodeIdCount;
 
    int m_hyperedgeIdCount;
 
    int m_hypernodeArrayTableSize;
 
    int m_hyperedgeArrayTableSize;
 
    mutable ListPure<HypergraphArrayBase*> m_hypernodeArrays;
    mutable ListPure<HypergraphArrayBase*> m_hyperedgeArrays;
    mutable ListPure<HypergraphObserver*> m_observers;
 
public:
    Hypergraph();
 
    Hypergraph(const Hypergraph& H);
 
    ~Hypergraph();
 
    bool empty() const { return m_nHypernodes == 0; }
 
    internal::GraphList<HypernodeElement> hypernodes() const { return m_hypernodes; }
 
    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(); }
 
    int hypernodeArrayTableSize() const { return m_hypernodeArrayTableSize; }
 
    int hyperedgeArrayTableSize() const { return m_hyperedgeArrayTableSize; }
 
    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;
 
    ListIterator<HypergraphArrayBase*> registerHypernodeArray(
            HypergraphArrayBase* pHypernodeArray) const;
 
    ListIterator<HypergraphArrayBase*> registerHyperedgeArray(
            HypergraphArrayBase* pHyperedgeArray) const;
 
    ListIterator<HypergraphObserver*> registerObserver(HypergraphObserver* pObserver) const;
 
    void unregisterHypernodeArray(ListIterator<HypergraphArrayBase*> it) const;
 
    void unregisterHyperedgeArray(ListIterator<HypergraphArrayBase*> it) const;
 
    void unregisterObserver(ListIterator<HypergraphObserver*> it) const;
 
    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();
 
    void initObservers();
 
    int nextEntry(char* buffer, int from, string stop);
 
    HypernodeElement::Type gateType(string gate);
};
 
}