Hypergraph.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/List.h>
#include <ogdf/basic/GraphList.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);
};
 
}