HyperGraph.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 *
 * last checkin:
 *   $Author: gutwenger $
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $
 ***************************************************************/

#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_HYPER_GRAPH_H
#define OGDF_HYPER_GRAPH_H

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

namespace ogdf {

class HyperGraph
{
public:
    class AdjElement;

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

        inline 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;
    public:
        inline int index() const { return m_index; }

        inline 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;
    public:
        inline AdjElement() : m_pNode(0),
                              m_pEdge(0) {};

        inline NodeElement* theNode() { return m_pNode; };

        inline EdgeElement* theEdge() { return m_pEdge; };

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

        inline 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;

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

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

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

    typedef EList<
                EdgeElement, AdjElement,
                &EdgeElement::m_numAdj,
                &EdgeElement::m_pFirstAdj,
                &EdgeElement::m_pLastAdj,
                &AdjElement::m_pPrev_edgeAdj,
                &AdjElement::m_pNext_edgeAdj
            > EdgeAdjList;
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);
        }

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

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

        inline 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 ArrayController
    {
    public:
        ArrayController() : m_tableSize(0)
        {
            ArrayListType::init(this);
        }

        ~ArrayController()
        {
            // Unregister all arrays, but do not delete them.
            while (!ArrayListType::empty(this))
                unregisterArray(ArrayListType::front(this));
        }

        inline void registerArray(GraphArrayBase<ElementType>* pArray)
        {
            ArrayListType::pushBack(this, pArray);
            pArray->setSize(m_tableSize);
        }

        inline void unregisterArray(GraphArrayBase<ElementType>* pArray)
        {
            ArrayListType::remove(this, pArray);
            pArray->setSize(0);
        }

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

        inline void 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 ArrayListType::iterator it = ArrayListType::begin(this);
                     it.valid(); it++)
                {
                    // and resize them
                    (*it)->setSize(m_tableSize);
                };
            };
        }

    protected:
        GraphArrayBase<ElementType>* m_first;

        GraphArrayBase<ElementType>* m_last;

        int m_numArrays;

        int m_tableSize;

        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); };

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

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

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

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

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

    inline 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()
    {
        NodeList::init( this );
        EdgeList::init( this );
    }

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

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

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


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

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

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

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

    inline 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;
    }


    inline 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);
            };
        }
    }


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

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

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

    inline int numberOfNodes() const {  return NodeList::size(this);  };
    inline int numberOfEdges() const {  return EdgeList::size(this);  };

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

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

    void toCliqueGraph(Graph* pG,
                       ogdf::NodeArray<NodeElement*>* pNodeMap = 0,
                       ogdf::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;
            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();
                    ogdf::node gNode  = hgNode_to_gNode[ hgNode ];
                    ogdf::node gNode2  = hgNode_to_gNode[ hgNode2 ];

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

    void toStarGraph(Graph* pG,
                     ogdf::NodeArray<NodeElement*>* pNodeMap = 0,
                     ogdf::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;
            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;
            ogdf::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();
                ogdf::node gNode  = hgNode_to_gNode[ hgNode ];
                ogdf::edge gEdge = pG->newEdge(gNodeDummy, gNode);
                if (pEdgeMap)
                    (*pEdgeMap)[gEdge] = hgEdge;
            };
        };
    };
}; // end of class HyperGraph

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<HyperGraph::NodeList, HyperGraph::NodeArray<T> >(outStream, array);
    return outStream;
};

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

template<typename T>
static std::ostream& operator<<(std::ostream& outStream, HyperGraph::AdjArray<T>& array)
{
    for (HyperGraph::EdgeList::iterator it = HyperGraph::EdgeList::begin(array.graph());it.valid(); it++)
    {
        HyperGraph::edge e = *it;
        for (HyperGraph::EdgeAdjList::iterator adj_it = HyperGraph::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<HyperGraph::NodeList, HyperGraph::NodeArray<T> >(inStream, array);
    return inStream;
};

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

template<typename T>
static std::ostream& operator>>(std::istream& inStream, HyperGraph::AdjArray<T>& array)
{
    for (HyperGraph::EdgeList::iterator it = HyperGraph::EdgeList::begin(array.graph());it.valid(); it++)
    {
        HyperGraph::edge e = *it;
        for (HyperGraph::EdgeAdjList::iterator adj_it = HyperGraph::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 (HyperGraph::NodeList::iterator it = HyperGraph::NodeList::begin(&graph);it.valid(); it++)
    {
        packed_index[*it] = i++;
    };

    for (HyperGraph::EdgeList::iterator it = HyperGraph::EdgeList::begin(&graph);it.valid(); it++)
    {
        HyperGraph::edge e = *it;
        outStream << e->cardinality() << std::endl;
        for (HyperGraph::EdgeAdjList::iterator adj_it = HyperGraph::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;
    int numAdjElements;
    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_ */