HyperGraph.h

Go to the documentation of this file.

/*
 * $Revision: 2615 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2012-07-16 14:23:36 +0200 (Mo, 16. Jul 2012) $
 ***************************************************************/

#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_HYPER_GRAPH_H
#define OGDF_HYPER_GRAPH_H

#include <ogdf/basic/GraphAttributes.h>
#include <ogdf/basic/EList.h>
#include <ogdf/basic/EFreeList.h>

namespace ogdf {

class OGDF_EXPORT HyperGraph
{
    friend class HyperGraphTypes;

public:
    // forward declaration to make AdjElement pointers available
    class AdjElement;

    class NodeElement
    {
        friend class HyperGraph;
        friend class HyperGraphTypes;
    public:
        int index() const { return m_index; }

        int degree() const { return m_numAdj; }

    private:
        NodeElement* m_pPrev;
        NodeElement* m_pNext;
        AdjElement* m_pFirstAdj;
        AdjElement* m_pLastAdj;
        int m_numAdj;
        int m_index;
    }; // class NodeElement


    class EdgeElement
    {
        friend class HyperGraph;
        friend class HyperGraphTypes;
    public:
        int index() const { return m_index; }

        int cardinality() const { return m_numAdj; }

    private:
        EdgeElement* m_pPrev;
        EdgeElement* m_pNext;
        AdjElement* m_pFirstAdj;
        AdjElement* m_pLastAdj;
        int m_numAdj;
        int m_index;
    }; // class EdgeElement


    class AdjElement
    {
        friend class HyperGraph;
        friend class HyperGraphTypes;
    public:
        AdjElement() : m_pNode(0), m_pEdge(0) { }

        NodeElement* theNode() { return m_pNode; }

        EdgeElement* theEdge() { return m_pEdge; }

        int index() const { return m_index; }
    private:

        AdjElement(NodeElement* pNode, EdgeElement* pEdge) :
            m_pNode(pNode),
            m_pEdge(pEdge),
            m_pPrev_nodeAdj(0),
            m_pNext_nodeAdj(0),
            m_pPrev_edgeAdj(0),
            m_pNext_edgeAdj(0)
        { }

        NodeElement* m_pNode;
        EdgeElement* m_pEdge;

        AdjElement* m_pPrev_nodeAdj;
        AdjElement* m_pNext_nodeAdj;

        AdjElement* m_pPrev_edgeAdj;
        AdjElement* m_pNext_edgeAdj;
        int m_index;
    };

    typedef NodeElement* node;
    typedef EdgeElement* edge;

protected:
    NodeElement* m_pFirstNode;
    NodeElement* m_pLastNode;
    int m_numNodes;

    EdgeElement* m_pFirstEdge;
    EdgeElement* m_pLastEdge;
    int m_numEdges;

protected:
    EFreeListIndexPool<
        NodeElement,
        &NodeElement::m_pNext,
        &NodeElement::m_index
    > m_nodeAllocator;

    EFreeListIndexPool<
        EdgeElement,
        &EdgeElement::m_pNext,
        &EdgeElement::m_index
    > m_edgeAllocator;

    EFreeListIndexPool<
        AdjElement,
        &AdjElement::m_pNext_nodeAdj, // note: we just need one next pointer, nobody cares which one.
        &AdjElement::m_index
    > m_adjAllocator;


    template<typename E>
    class GraphArrayBase
    {
        friend class HyperGraph;
    public:
        virtual void setSize(int numElements) = 0;

        GraphArrayBase<E>* m_prev; 
        GraphArrayBase<E>* m_next; 
    };


    template<typename T, typename E>
    class GraphArray : protected Array<T>, GraphArrayBase<E>
    {
        friend class HyperGraph;
    public:
        // Creates an empty graph array not attached to a graph.
        GraphArray() : m_pGraph(0), Array<T>() { }

        GraphArray(HyperGraph* pGraph) : m_pGraph(pGraph), m_initialValue(), Array<T>()
        {
            if (m_pGraph)
                m_pGraph->registerArray(this);
        }

        GraphArray(HyperGraph* pGraph, const T& initialValue) : m_pGraph(pGraph), m_initialValue(initialValue), Array<T>()
        {
            if (m_pGraph)
                m_pGraph->registerArray(this);
        }


        virtual ~GraphArray()
        {
            if (m_pGraph)
                m_pGraph->unregisterArray(this);
        }

        const T& operator[](const E* e) const
        {
            return Array<T>::operator [](e->index());
        }

        T& operator[](const E* e)
        {
            return Array<T>::operator [](e->index());
        }

        HyperGraph* graph() const
        {
            return m_pGraph;
        }

    protected:

        virtual void setSize(int numElements)
        {
            if (numElements > Array<T>::size())
                Array<T>::grow(numElements-Array<T>::size(),m_initialValue);
        }

        HyperGraph* m_pGraph;

        T m_initialValue;

    }; // end of class GraphArray


    template<typename ElementType> class ArrayControllerTypes;

    template<typename ElementType>
    class ArrayController
    {
        friend class ArrayControllerTypes<ElementType>;
    public:
        ArrayController() : m_tableSize(0)
        {
            ArrayControllerTypes<ElementType>::ArrayListType::init(this);
        }

        ~ArrayController();

        void registerArray(GraphArrayBase<ElementType>* pArray);

        void unregisterArray(GraphArrayBase<ElementType>* pArray);

        int newTableSize(int minSize)
        {
            int res = 1;
            while (res < minSize)
                res = res << 1;
            return res;
        }

        void numUsedIndicesChanged(int numUsedIndices);

    protected:
        GraphArrayBase<ElementType>* m_first;

        GraphArrayBase<ElementType>* m_last;

        int m_numArrays;

        int m_tableSize;
    };


    template<typename ElementType>
    class ArrayControllerTypes
    {
    public:
        typedef EList< ArrayController<ElementType>, GraphArrayBase<ElementType>,
            &ArrayController<ElementType>::m_numArrays,
            &ArrayController<ElementType>::m_first,
            &ArrayController<ElementType>::m_last,
            &GraphArrayBase<ElementType>::m_prev,
            &GraphArrayBase<ElementType>::m_next> ArrayListType;
    };


    ArrayController<NodeElement>  m_nodeArrayController;    
    ArrayController<EdgeElement>  m_edgeArrayController;    
    ArrayController<AdjElement>   m_adjArrayController;     

    void registerArray(GraphArrayBase<NodeElement>* pArray) { m_nodeArrayController.registerArray(pArray); }
    void registerArray(GraphArrayBase<EdgeElement>* pArray) { m_edgeArrayController.registerArray(pArray); }
    void registerArray(GraphArrayBase<AdjElement>* pArray) { m_adjArrayController.registerArray(pArray); }


    void unregisterArray(GraphArrayBase<NodeElement>* pArray) { m_nodeArrayController.unregisterArray(pArray); }
    void unregisterArray(GraphArrayBase<EdgeElement>* pArray) { m_edgeArrayController.unregisterArray(pArray); }
    void unregisterArray(GraphArrayBase<AdjElement>* pArray) { m_adjArrayController.unregisterArray(pArray); }

    NodeElement* allocateNodeElement()
    {
        NodeElement* pResult = m_nodeAllocator.alloc();
        m_nodeArrayController.numUsedIndicesChanged(m_nodeAllocator.numUsedIndices());
        return pResult;
    }

    EdgeElement* allocateEdgeElement()
    {
        EdgeElement* pResult = m_edgeAllocator.alloc();
        m_edgeArrayController.numUsedIndicesChanged(m_edgeAllocator.numUsedIndices());
        return pResult;
    }

    AdjElement* allocateAdjElement()
    {
        AdjElement* pResult = m_adjAllocator.alloc();
        m_adjArrayController.numUsedIndicesChanged(m_adjAllocator.numUsedIndices());
        return pResult;
    }

    void freeNodeElement(NodeElement* pNode)
    {
        m_nodeAllocator.free(pNode);
    }

    void freeEdgeElement(EdgeElement* pEdge)
    {
        m_edgeAllocator.free(pEdge);
    }

    void freeAdjElement(AdjElement* pAdj)
    {
        m_adjAllocator.free(pAdj);
    }

public:

    template<typename T>
    class NodeArray : public GraphArray<T, NodeElement>
    {
    public:
        NodeArray(HyperGraph* pGraph) : GraphArray<T, NodeElement>(pGraph) {}
        NodeArray(HyperGraph* pGraph, const T& initValue) : GraphArray<T, NodeElement>(pGraph, initValue) {}
    };

    template<typename T>
    class EdgeArray : public GraphArray<T, EdgeElement>
    {
    public:
        EdgeArray(HyperGraph* pGraph) : GraphArray<T, EdgeElement>(pGraph) {}
        EdgeArray(HyperGraph* pGraph, const T& initValue) : GraphArray<T, EdgeElement>(pGraph, initValue) {}
    };

    template<typename T>
    class AdjArray : public GraphArray<T, AdjElement>
    {
    public:
        AdjArray(HyperGraph* pGraph) : GraphArray<T, AdjElement>(pGraph) {}
        AdjArray(HyperGraph* pGraph, const T& initValue) : GraphArray<T, AdjElement>(pGraph, initValue) {}
    };


    HyperGraph();

    NodeElement* newNode();

    EdgeElement* newEdge();

    EdgeElement* newEdge(NodeElement* pNode1, NodeElement* pNode2)
    {
        EdgeElement* pEdge = newEdge();
        newAdjElement( pNode1, pEdge );
        newAdjElement( pNode2, pEdge );
        return pEdge;
    }


    AdjElement* newAdjElement(NodeElement* pNode, EdgeElement* pEdge);

    void delAdjElement(AdjElement* pAdj);

    void delAdjElement(NodeElement* pNode, EdgeElement* pEdge)
    {
        AdjElement* pAdj = findAdjElement(pNode, pEdge);
        if (pAdj) delAdjElement(pAdj);
    }

    AdjElement* addNode(NodeElement* pNode, EdgeElement* pEdge, bool checkIfAlreadyExists = false)
    {
        if (!checkIfAlreadyExists)
            return newAdjElement( pNode, pEdge );

        AdjElement* pAdj = findAdjElement(pNode, pEdge);
        if (!pAdj)
            pAdj = newAdjElement( pNode, pEdge );
        return pAdj;
    }


    void removeNode(NodeElement* pNode, EdgeElement* pEdge, bool removeDuplicates = false)
    {
        AdjElement* pAdj = findAdjElement(pNode, pEdge);
        if (!removeDuplicates && pAdj)
        {
            delAdjElement(pAdj);
        } else
        {
            while (pAdj)
            {
                delAdjElement(pAdj);
                pAdj = findAdjElement(pNode, pEdge);
            }
        }
    }


    AdjElement* findAdjElement(NodeElement* pNode, EdgeElement* pEdge) const;

    void delEdge(EdgeElement* pEdge);

    void delNode(NodeElement* pNode);

    int numberOfNodes() const;
    int numberOfEdges() const;

    void clear();

    /* void toCliqueGraph(
        Graph* pG,
        NodeArray<HyperGraph::NodeElement*>* pNodeMap = 0,
        EdgeArray<HyperGraph::EdgeElement*>* pEdgeMap = 0)
    {
        HyperGraph::NodeArray<ogdf::node> hgNode_to_gNode(this);
        for (NodeList::iterator it = HyperGraph::NodeList::begin(this); it.valid(); it++)
        {
            HyperGraph::NodeElement* hgNode = *it;
            ogdf::node gNode  = pG->newNode();
            hgNode_to_gNode[ hgNode ] = gNode;
            if (pNodeMap)
                (*pNodeMap)[gNode] = hgNode;
        }

        for (HyperGraph::EdgeList::iterator it = HyperGraph::EdgeList::begin(this); it.valid(); it++)
        {
            EdgeElement* hgEdge = *it;
            for (HyperGraph::EdgeAdjList::iterator adj_it = HyperGraph::EdgeAdjList::begin(hgEdge); adj_it.valid(); adj_it++)
            {
                for (HyperGraph::EdgeAdjList::iterator adj_it2 = adj_it.succ(); adj_it2.valid(); adj_it2++)
                {
                    NodeElement* hgNode = (*adj_it)->theNode();
                    NodeElement* hgNode2 = (*adj_it2)->theNode();
                    node gNode  = hgNode_to_gNode[ hgNode ];
                    node gNode2  = hgNode_to_gNode[ hgNode2 ];

                    edge gEdge = pG->newEdge(gNode, gNode2);
                    if (pEdgeMap)
                        (*pEdgeMap)[gEdge] = hgEdge;
                }
            }
        }
    }

    void toStarGraph(
        Graph* pG,
        NodeArray<NodeElement*>* pNodeMap = 0,
        EdgeArray<EdgeElement*>* pEdgeMap = 0)
    {
        HyperGraph::NodeArray<ogdf::node> hgNode_to_gNode(this);
        for (NodeList::iterator it = HyperGraph::NodeList::begin(this); it.valid(); it++)
        {
            NodeElement* hgNode = *it;
            node gNode  = pG->newNode();
            hgNode_to_gNode[ hgNode ] = gNode;
            if (pNodeMap)
                (*pNodeMap)[gNode] = hgNode;
        }

        for (HyperGraph::EdgeList::iterator it = HyperGraph::EdgeList::begin(this); it.valid(); it++)
        {
            EdgeElement* hgEdge = *it;
            node gNodeDummy  = pG->newNode();
            if (pNodeMap)
                (*pNodeMap)[gNodeDummy] = 0;

            for (HyperGraph::EdgeAdjList::iterator adj_it = HyperGraph::EdgeAdjList::begin(hgEdge); adj_it.valid(); adj_it++)
            {
                NodeElement* hgNode = (*adj_it)->theNode();
                node gNode  = hgNode_to_gNode[ hgNode ];
                edge gEdge = pG->newEdge(gNodeDummy, gNode);
                if (pEdgeMap)
                    (*pEdgeMap)[gEdge] = hgEdge;
            }
        }
    } */
}; // end of class HyperGraph


class HyperGraphTypes
{
public:
    typedef EList<
                HyperGraph, HyperGraph::NodeElement,
                &HyperGraph::m_numNodes,
                &HyperGraph::m_pFirstNode,
                &HyperGraph::m_pLastNode,
                &HyperGraph::NodeElement::m_pPrev,
                &HyperGraph::NodeElement::m_pNext
            > NodeList;

    typedef EList<
                HyperGraph, HyperGraph::EdgeElement,
                &HyperGraph::m_numEdges,
                &HyperGraph::m_pFirstEdge,
                &HyperGraph::m_pLastEdge,
                &HyperGraph::EdgeElement::m_pPrev,
                &HyperGraph::EdgeElement::m_pNext
            > EdgeList;

    typedef EList<
                HyperGraph::NodeElement, HyperGraph::AdjElement,
                &HyperGraph::NodeElement::m_numAdj,
                &HyperGraph::NodeElement::m_pFirstAdj,
                &HyperGraph::NodeElement::m_pLastAdj,
                &HyperGraph::AdjElement::m_pPrev_nodeAdj,
                &HyperGraph::AdjElement::m_pNext_nodeAdj
            > NodeAdjList;

    typedef EList<
                HyperGraph::EdgeElement, HyperGraph::AdjElement,
                &HyperGraph::EdgeElement::m_numAdj,
                &HyperGraph::EdgeElement::m_pFirstAdj,
                &HyperGraph::EdgeElement::m_pLastAdj,
                &HyperGraph::AdjElement::m_pPrev_edgeAdj,
                &HyperGraph::AdjElement::m_pNext_edgeAdj
            > EdgeAdjList;
};


template<typename ElementType>
HyperGraph::ArrayController<ElementType>::~ArrayController()
{
    // Unregisters all arrays, but does not delete them.
    while (!ArrayControllerTypes<ElementType>::ArrayListType::empty(this))
        unregisterArray(ArrayControllerTypes<ElementType>::ArrayListType::front(this));
}


// Registers a new graph array and sets the size to \a m_tableSize.
template<typename ElementType>
inline void HyperGraph::ArrayController<ElementType>::registerArray(GraphArrayBase<ElementType>* pArray)
{
    ArrayControllerTypes<ElementType>::ArrayListType::pushBack(this, pArray);
    pArray->setSize(m_tableSize);
}


// Unregisters an array by removing it from the list.
template<typename ElementType>
inline void HyperGraph::ArrayController<ElementType>::unregisterArray(GraphArrayBase<ElementType>* pArray)
{
    ArrayControllerTypes<ElementType>::ArrayListType::remove(this, pArray);
    pArray->setSize(0);
}


template<typename ElementType>
inline void HyperGraph::ArrayController<ElementType>::numUsedIndicesChanged(int numUsedIndices)
{
    // check if we have to grow
    if (numUsedIndices > m_tableSize)
    {
        // we have to resize
        // calculate new table size
        m_tableSize = newTableSize(numUsedIndices);
        // iterate over all arrays
        for (typename ArrayControllerTypes<ElementType>::ArrayListType::iterator it = ArrayControllerTypes<ElementType>::ArrayListType::begin(this);
                it.valid(); it++)
        {
            // and resize them
            (*it)->setSize(m_tableSize);
        }
    }
}


inline HyperGraph::HyperGraph()
{
    HyperGraphTypes::NodeList::init( this );
    HyperGraphTypes::EdgeList::init( this );
}


inline HyperGraph::NodeElement* HyperGraph::newNode()
{
    NodeElement* pNode = allocateNodeElement();
    HyperGraphTypes::NodeList::pushBack( this, pNode );
    HyperGraphTypes::NodeAdjList::init( pNode );
    return pNode;
}


inline HyperGraph::EdgeElement* HyperGraph::newEdge()
{
    EdgeElement* pEdge = allocateEdgeElement();
    HyperGraphTypes::EdgeList::pushBack( this, pEdge );
    HyperGraphTypes::EdgeAdjList::init( pEdge );
    return pEdge;
}


inline HyperGraph::AdjElement* HyperGraph::newAdjElement(HyperGraph::NodeElement* pNode, HyperGraph::EdgeElement* pEdge)
{
    AdjElement* pAdj = allocateAdjElement();
    pAdj->m_pNode = pNode;
    pAdj->m_pEdge = pEdge;

    HyperGraphTypes::NodeAdjList::pushBack( pNode, pAdj );
    HyperGraphTypes::EdgeAdjList::pushBack( pEdge, pAdj );
    return pAdj;
}


inline void HyperGraph::delAdjElement(HyperGraph::AdjElement* pAdj)
{
    HyperGraphTypes::EdgeAdjList::remove( pAdj->theEdge(), pAdj );
    HyperGraphTypes::NodeAdjList::remove( pAdj->theNode(), pAdj );
    freeAdjElement( pAdj );
}


inline HyperGraph::AdjElement* HyperGraph::findAdjElement(HyperGraph::NodeElement* pNode, HyperGraph::EdgeElement* pEdge) const
{
    if (HyperGraphTypes::EdgeAdjList::size(pEdge) < HyperGraphTypes::NodeAdjList::size(pNode))
    {
        for (HyperGraphTypes::EdgeAdjList::iterator it = HyperGraphTypes::EdgeAdjList::begin(pEdge);
                it.valid(); it++)
        {
            if ((*it)->theNode() == pNode) return (*it);
        }
    } else
    {
        for (HyperGraphTypes::NodeAdjList::iterator it = HyperGraphTypes::NodeAdjList::begin(pNode);
                it.valid(); it++)
        {
            if ((*it)->theEdge() == pEdge) return (*it);
        }
    }
    return 0;
}


inline void HyperGraph::delEdge(HyperGraph::EdgeElement* pEdge)
{
    for (HyperGraphTypes::EdgeAdjList::iterator it = HyperGraphTypes::EdgeAdjList::begin(pEdge); it.valid();)
    {
        AdjElement* pAdj = *it;
        HyperGraphTypes::NodeAdjList::remove( pAdj->theNode(), pAdj );
        it = HyperGraphTypes::EdgeAdjList::remove( pEdge, it );
        freeAdjElement( pAdj );
    }
    HyperGraphTypes::EdgeList::remove( this, pEdge );
    freeEdgeElement( pEdge );
}


void HyperGraph::delNode(HyperGraph::NodeElement* pNode)
{
    for (HyperGraphTypes::NodeAdjList::iterator it = HyperGraphTypes::NodeAdjList::begin(pNode); it.valid();)
    {
        AdjElement* pAdj = *it;
        HyperGraphTypes::EdgeAdjList::remove( pAdj->theEdge(), pAdj );
        it = HyperGraphTypes::NodeAdjList::remove( pNode, it );
        freeAdjElement( pAdj );
    }
    HyperGraphTypes::NodeList::remove( this, pNode );
    freeNodeElement( pNode );
}


inline int HyperGraph::numberOfNodes() const { return HyperGraphTypes::NodeList::size(this); }

inline int HyperGraph::numberOfEdges() const { return HyperGraphTypes::EdgeList::size(this); }


inline void HyperGraph::clear()
{
    while (numberOfNodes())
    {
        delNode( HyperGraphTypes::NodeList::front(this) );
    }

    while (numberOfEdges())
    {
        delEdge( HyperGraphTypes::EdgeList::front(this) );
    }
}



template<typename ListType, typename ArrayType>
static void writeToStream(std::ostream& outStream, ArrayType& array)
{
    for (typename ListType::iterator it = ListType::begin(array.graph()); it.valid(); it++)
    {
        outStream << array[*it] << std::endl;
    }
}


template<typename ListType, typename ArrayType>
static void readFromStream(std::istream& inStream, ArrayType& array)
{
    for (typename ListType::iterator it = ListType::begin(array.graph());it.valid(); it++)
    {
        inStream >> array[(*it)];
    }
}

template<typename T>
static std::ostream& operator<<(std::ostream& outStream, HyperGraph::NodeArray<T>& array)
{
    writeToStream<HyperGraphTypes::NodeList, HyperGraph::NodeArray<T> >(outStream, array);
    return outStream;
}

template<typename T>
static std::ostream& operator<<(std::ostream& outStream, HyperGraph::EdgeArray<T>& array)
{
    writeToStream<HyperGraphTypes::EdgeList, HyperGraph::EdgeArray<T> >(outStream, array);
    return outStream;
}

template<typename T>
static std::ostream& operator<<(std::ostream& outStream, HyperGraph::AdjArray<T>& array)
{
    for (HyperGraphTypes::EdgeList::iterator it = HyperGraphTypes::EdgeList::begin(array.graph());it.valid(); it++)
    {
        HyperGraph::edge e = *it;
        for (HyperGraphTypes::EdgeAdjList::iterator adj_it = HyperGraphTypes::EdgeAdjList::begin(e); adj_it.valid(); adj_it++)
        {
            outStream << array[(*adj_it)] << std::endl;
        }
    }
    return outStream;
}


template<typename T>
static std::istream& operator>>(std::istream& inStream, HyperGraph::NodeArray<T>& array)
{
    readFromStream<HyperGraphTypes::NodeList, HyperGraph::NodeArray<T> >(inStream, array);
    return inStream;
}


template<typename T>
static std::istream& operator>>(std::istream& inStream, HyperGraph::EdgeArray<T>& array)
{
    readFromStream<HyperGraphTypes::EdgeList, HyperGraph::EdgeArray<T> >(inStream, array);
    return inStream;
}


template<typename T>
static std::istream& operator>>(std::istream& inStream, HyperGraph::AdjArray<T>& array)
{
    for (HyperGraphTypes::EdgeList::iterator it = HyperGraphTypes::EdgeList::begin(array.graph());it.valid(); it++)
    {
        HyperGraph::edge e = *it;
        for (HyperGraphTypes::EdgeAdjList::iterator adj_it = HyperGraphTypes::EdgeAdjList::begin(e); adj_it.valid(); adj_it++)
        {
            inStream >> array[(*adj_it)];
        }
    }
    return inStream;
}


static std::ostream& operator<<(std::ostream& outStream, HyperGraph& graph)
{
    outStream << graph.numberOfNodes() << std::endl;
    outStream << graph.numberOfEdges() << std::endl;

    HyperGraph::NodeArray<int> packed_index(&graph);

    int i=0;
    for (HyperGraphTypes::NodeList::iterator it = HyperGraphTypes::NodeList::begin(&graph);it.valid(); it++)
    {
        packed_index[*it] = i++;
    }

    for (HyperGraphTypes::EdgeList::iterator it = HyperGraphTypes::EdgeList::begin(&graph);it.valid(); it++)
    {
        HyperGraph::edge e = *it;
        outStream << e->cardinality() << std::endl;
        for (HyperGraphTypes::EdgeAdjList::iterator adj_it = HyperGraphTypes::EdgeAdjList::begin(e); adj_it.valid(); adj_it++)
        {
            outStream << packed_index[(*adj_it)->theNode()] << std::endl;
        }
    }
    return outStream;
}


static std::istream& operator>>(std::istream& inStream, HyperGraph& graph)
{
    int numNodes;
    int numEdges;
    inStream >> numNodes;
    inStream >> numEdges;

    HyperGraph::node* pNodes = new HyperGraph::node[numNodes];
    for (int i=0; i<numNodes;i++)
        pNodes[i] = graph.newNode();

    for (int i=0; i<numEdges;i++)
    {
        HyperGraph::edge e = graph.newEdge();
        int numAdj;
        inStream >> numAdj;
        for (int j=0; j<numAdj; j++)
        {
            int packedNodeIndex;
            inStream >> packedNodeIndex;
            graph.addNode(pNodes[packedNodeIndex], e);
        }
    }
    return inStream;
}

} // end of namespace ogdf

#endif /* HYPERGRAPH_H_ */