Open
Graph Drawing
Framework

 v.2012.05
 

HyperGraph.h
Go to the documentation of this file.
00001 /*
00002  * $Revision: 2299 $
00003  *
00004  * last checkin:
00005  *   $Author: gutwenger $
00006  *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $
00007  ***************************************************************/
00008 
00043 #ifdef _MSC_VER
00044 #pragma once
00045 #endif
00046 
00047 #ifndef OGDF_HYPER_GRAPH_H
00048 #define OGDF_HYPER_GRAPH_H
00049 
00050 #include <ogdf/basic/EList.h>
00051 #include <ogdf/basic/EFreeList.h>
00052 #include <iostream>
00053 
00054 namespace ogdf {
00055 
00056 class HyperGraph
00057 {
00058 public:
00060     class AdjElement;
00061 
00063     class NodeElement
00064     {
00065         friend class HyperGraph;
00066     public:
00068         inline int index() const { return m_index; };
00069 
00071         inline int degree() const { return m_numAdj; };
00072 
00073     private:
00074         NodeElement* m_pPrev;
00075         NodeElement* m_pNext;
00076         AdjElement* m_pFirstAdj;
00077         AdjElement* m_pLastAdj;
00078         int m_numAdj;
00079         int m_index;
00080     }; // class NodeElement
00081 
00083     class EdgeElement
00084     {
00085         friend class HyperGraph;
00086     public:
00088         inline int index() const { return m_index; }
00089 
00091         inline int cardinality() const { return m_numAdj; };
00092 
00093     private:
00094         EdgeElement* m_pPrev;
00095         EdgeElement* m_pNext;
00096         AdjElement* m_pFirstAdj;
00097         AdjElement* m_pLastAdj;
00098         int m_numAdj;
00099         int m_index;
00100     }; // class EdgeElement
00101 
00103     class AdjElement
00104     {
00105         friend class HyperGraph;
00106     public:
00107         inline AdjElement() : m_pNode(0),
00108                               m_pEdge(0) {};
00109 
00111         inline NodeElement* theNode() { return m_pNode; };
00112 
00114         inline EdgeElement* theEdge() { return m_pEdge; };
00115 
00117         inline int index() const { return m_index; }
00118     private:
00119 
00120         inline AdjElement(NodeElement* pNode,
00121                           EdgeElement* pEdge) :
00122                             m_pNode(pNode),
00123                             m_pEdge(pEdge),
00124                             m_pPrev_nodeAdj(0),
00125                             m_pNext_nodeAdj(0),
00126                             m_pPrev_edgeAdj(0),
00127                             m_pNext_edgeAdj(0)
00128         {};
00129 
00130         NodeElement* m_pNode;
00131         EdgeElement* m_pEdge;
00132 
00133         AdjElement* m_pPrev_nodeAdj;
00134         AdjElement* m_pNext_nodeAdj;
00135 
00136         AdjElement* m_pPrev_edgeAdj;
00137         AdjElement* m_pNext_edgeAdj;
00138         int m_index;
00139     };
00140 
00141     typedef NodeElement* node;
00142     typedef EdgeElement* edge;
00143 
00144 protected:
00145     NodeElement* m_pFirstNode;
00146     NodeElement* m_pLastNode;
00147     int m_numNodes;
00148 
00149     EdgeElement* m_pFirstEdge;
00150     EdgeElement* m_pLastEdge;
00151     int m_numEdges;
00152 
00153 public:
00154     typedef EList<
00155                 HyperGraph, NodeElement,
00156                 &HyperGraph::m_numNodes,
00157                 &HyperGraph::m_pFirstNode,
00158                 &HyperGraph::m_pLastNode,
00159                 &NodeElement::m_pPrev,
00160                 &NodeElement::m_pNext
00161             > NodeList;
00162 
00164     typedef EList<
00165                 HyperGraph, EdgeElement,
00166                 &HyperGraph::m_numEdges,
00167                 &HyperGraph::m_pFirstEdge,
00168                 &HyperGraph::m_pLastEdge,
00169                 &EdgeElement::m_pPrev,
00170                 &EdgeElement::m_pNext
00171             > EdgeList;
00172 
00174     typedef EList<
00175                 NodeElement, AdjElement,
00176                 &NodeElement::m_numAdj,
00177                 &NodeElement::m_pFirstAdj,
00178                 &NodeElement::m_pLastAdj,
00179                 &AdjElement::m_pPrev_nodeAdj,
00180                 &AdjElement::m_pNext_nodeAdj
00181             > NodeAdjList;
00182 
00184     typedef EList<
00185                 EdgeElement, AdjElement,
00186                 &EdgeElement::m_numAdj,
00187                 &EdgeElement::m_pFirstAdj,
00188                 &EdgeElement::m_pLastAdj,
00189                 &AdjElement::m_pPrev_edgeAdj,
00190                 &AdjElement::m_pNext_edgeAdj
00191             > EdgeAdjList;
00192 protected:
00193     EFreeListIndexPool<
00194         NodeElement,
00195         &NodeElement::m_pNext,
00196         &NodeElement::m_index
00197     > m_nodeAllocator;
00198 
00199     EFreeListIndexPool<
00200         EdgeElement,
00201         &EdgeElement::m_pNext,
00202         &EdgeElement::m_index
00203     > m_edgeAllocator;
00204 
00205     EFreeListIndexPool<
00206         AdjElement,
00207         &AdjElement::m_pNext_nodeAdj, // note: we just need one next pointer, nobody cares which one.
00208         &AdjElement::m_index
00209     > m_adjAllocator;
00210 
00211     template<typename E>
00212     class GraphArrayBase
00213     {
00214         friend class HyperGraph;
00215     public:
00217         virtual void setSize(int numElements) = 0;
00218 
00220         GraphArrayBase<E>* m_prev;
00221         GraphArrayBase<E>* m_next;
00222     };
00223 
00224     template<typename T, typename E>
00225     class GraphArray : protected Array<T>, GraphArrayBase<E>
00226     {
00227         friend class HyperGraph;
00228     public:
00229         // Creates an empty graph array not attached to a graph.
00230         GraphArray() : m_pGraph(0), Array<T>() {};
00231 
00233         GraphArray(HyperGraph* pGraph) : m_pGraph(pGraph), m_initialValue(), Array<T>()
00234         {
00235             if (m_pGraph)
00236                 m_pGraph->registerArray(this);
00237         }
00238 
00240         GraphArray(HyperGraph* pGraph, const T& initialValue) : m_pGraph(pGraph), m_initialValue(initialValue), Array<T>()
00241         {
00242             if (m_pGraph)
00243                 m_pGraph->registerArray(this);
00244         }
00245 
00247         virtual ~GraphArray()
00248         {
00249             if (m_pGraph)
00250                 m_pGraph->unregisterArray(this);
00251         }
00252 
00254         inline const T& operator[](const E* e) const
00255         {
00256             return Array<T>::operator [](e->index());
00257         }
00258 
00260         inline T& operator[](const E* e)
00261         {
00262             return Array<T>::operator [](e->index());
00263         }
00264 
00266         inline HyperGraph* graph() const
00267         {
00268             return m_pGraph;
00269         }
00270 
00271     protected:
00272 
00274         virtual void setSize(int numElements)
00275         {
00276             if (numElements > Array<T>::size())
00277                 Array<T>::grow(numElements-Array<T>::size(),m_initialValue);
00278         }
00279 
00281         HyperGraph* m_pGraph;
00282 
00284         T m_initialValue;
00285 
00286     }; // end of class GraphArray
00287 
00289     template<typename ElementType>
00290     class ArrayController
00291     {
00292     public:
00294         ArrayController() : m_tableSize(0)
00295         {
00296             ArrayListType::init(this);
00297         }
00298 
00300         ~ArrayController()
00301         {
00302             // Unregister all arrays, but do not delete them.
00303             while (!ArrayListType::empty(this))
00304                 unregisterArray(ArrayListType::front(this));
00305         }
00306 
00308         inline void registerArray(GraphArrayBase<ElementType>* pArray)
00309         {
00310             ArrayListType::pushBack(this, pArray);
00311             pArray->setSize(m_tableSize);
00312         }
00313 
00315         inline void unregisterArray(GraphArrayBase<ElementType>* pArray)
00316         {
00317             ArrayListType::remove(this, pArray);
00318             pArray->setSize(0);
00319         }
00320 
00322         inline int newTableSize(int minSize)
00323         {
00324             int res = 1;
00325             while (res < minSize)
00326                 res = res << 1;
00327             return res;
00328         }
00329 
00331         inline void numUsedIndicesChanged(int numUsedIndices)
00332         {
00333             // check if we have to grow
00334             if (numUsedIndices > m_tableSize)
00335             {
00336                 // we have to resize
00337                 // calculate new table size
00338                 m_tableSize = newTableSize(numUsedIndices);
00339                 // iterate over all arrays
00340                 for (typename ArrayListType::iterator it = ArrayListType::begin(this);
00341                      it.valid(); it++)
00342                 {
00343                     // and resize them
00344                     (*it)->setSize(m_tableSize);
00345                 };
00346             };
00347         }
00348 
00349     protected:
00351         GraphArrayBase<ElementType>* m_first;
00352 
00354         GraphArrayBase<ElementType>* m_last;
00355 
00357         int m_numArrays;
00358 
00360         int m_tableSize;
00361 
00363         typedef EList< ArrayController<ElementType>, GraphArrayBase<ElementType>,
00364                        &ArrayController<ElementType>::m_numArrays,
00365                        &ArrayController<ElementType>::m_first,
00366                        &ArrayController<ElementType>::m_last,
00367                        &GraphArrayBase<ElementType>::m_prev,
00368                        &GraphArrayBase<ElementType>::m_next> ArrayListType;
00369     };
00370 
00371     ArrayController<NodeElement>  m_nodeArrayController;    
00372     ArrayController<EdgeElement>  m_edgeArrayController;    
00373     ArrayController<AdjElement>  m_adjArrayController;      
00374 
00375     void registerArray(GraphArrayBase<NodeElement>* pArray) { m_nodeArrayController.registerArray(pArray); }
00376     void registerArray(GraphArrayBase<EdgeElement>* pArray) { m_edgeArrayController.registerArray(pArray); };
00377     void registerArray(GraphArrayBase<AdjElement>* pArray) { m_adjArrayController.registerArray(pArray); };
00378 
00379 
00380     void unregisterArray(GraphArrayBase<NodeElement>* pArray) { m_nodeArrayController.unregisterArray(pArray); }
00381     void unregisterArray(GraphArrayBase<EdgeElement>* pArray) { m_edgeArrayController.unregisterArray(pArray); };
00382     void unregisterArray(GraphArrayBase<AdjElement>* pArray) { m_adjArrayController.unregisterArray(pArray); };
00383 
00385     inline NodeElement* allocateNodeElement()
00386     {
00387         NodeElement* pResult = m_nodeAllocator.alloc();
00388         m_nodeArrayController.numUsedIndicesChanged(m_nodeAllocator.numUsedIndices());
00389         return pResult;
00390     }
00391 
00393     inline EdgeElement* allocateEdgeElement()
00394     {
00395         EdgeElement* pResult = m_edgeAllocator.alloc();
00396         m_edgeArrayController.numUsedIndicesChanged(m_edgeAllocator.numUsedIndices());
00397         return pResult;
00398     }
00399 
00401     inline AdjElement* allocateAdjElement()
00402     {
00403         AdjElement* pResult = m_adjAllocator.alloc();
00404         m_adjArrayController.numUsedIndicesChanged(m_adjAllocator.numUsedIndices());
00405         return pResult;
00406     }
00407 
00409     inline void freeNodeElement(NodeElement* pNode)
00410     {
00411         m_nodeAllocator.free(pNode);
00412     }
00413 
00415     inline void freeEdgeElement(EdgeElement* pEdge)
00416     {
00417         m_edgeAllocator.free(pEdge);
00418     }
00419 
00421     inline void freeAdjElement(AdjElement* pAdj)
00422     {
00423         m_adjAllocator.free(pAdj);
00424     }
00425 
00426 public:
00427 
00429     template<typename T>
00430     class NodeArray : public GraphArray<T, NodeElement>
00431     {
00432     public:
00433         NodeArray(HyperGraph* pGraph) : GraphArray<T, NodeElement>(pGraph) {}
00434         NodeArray(HyperGraph* pGraph, const T& initValue) : GraphArray<T, NodeElement>(pGraph, initValue) {}
00435     };
00436 
00438     template<typename T>
00439     class EdgeArray : public GraphArray<T, EdgeElement>
00440     {
00441     public:
00442         EdgeArray(HyperGraph* pGraph) : GraphArray<T, EdgeElement>(pGraph) {}
00443         EdgeArray(HyperGraph* pGraph, const T& initValue) : GraphArray<T, EdgeElement>(pGraph, initValue) {}
00444     };
00445 
00447     template<typename T>
00448     class AdjArray : public GraphArray<T, AdjElement>
00449     {
00450     public:
00451         AdjArray(HyperGraph* pGraph) : GraphArray<T, AdjElement>(pGraph) {}
00452         AdjArray(HyperGraph* pGraph, const T& initValue) : GraphArray<T, AdjElement>(pGraph, initValue) {}
00453     };
00454 
00455 
00457     HyperGraph()
00458     {
00459         NodeList::init( this );
00460         EdgeList::init( this );
00461     }
00462 
00464     inline NodeElement* newNode()
00465     {
00466         NodeElement* pNode = allocateNodeElement();
00467         NodeList::pushBack( this, pNode );
00468         NodeAdjList::init( pNode );
00469         return pNode;
00470     }
00471 
00473     inline EdgeElement* newEdge()
00474     {
00475         EdgeElement* pEdge = allocateEdgeElement();
00476         EdgeList::pushBack( this, pEdge );
00477         EdgeAdjList::init( pEdge );
00478         return pEdge;
00479     }
00480 
00482     inline EdgeElement* newEdge(NodeElement* pNode1, NodeElement* pNode2)
00483     {
00484         EdgeElement* pEdge = newEdge();
00485         newAdjElement( pNode1, pEdge );
00486         newAdjElement( pNode2, pEdge );
00487         return pEdge;
00488     }
00489 
00491 
00498     AdjElement* newAdjElement(NodeElement* pNode, EdgeElement* pEdge)
00499     {
00500         AdjElement* pAdj = allocateAdjElement();
00501         pAdj->m_pNode = pNode;
00502         pAdj->m_pEdge = pEdge;
00503 
00504         NodeAdjList::pushBack( pNode, pAdj );
00505         EdgeAdjList::pushBack( pEdge, pAdj );
00506         return pAdj;
00507     }
00508 
00510     void delAdjElement(AdjElement* pAdj)
00511     {
00512         EdgeAdjList::remove( pAdj->theEdge(), pAdj );
00513         NodeAdjList::remove( pAdj->theNode(), pAdj );
00514         freeAdjElement( pAdj );
00515     }
00516 
00518     void delAdjElement(NodeElement* pNode, EdgeElement* pEdge)
00519     {
00520         AdjElement* pAdj = findAdjElement(pNode, pEdge);
00521         if (pAdj) delAdjElement(pAdj);
00522     }
00523 
00525     inline AdjElement* addNode(NodeElement* pNode, EdgeElement* pEdge, bool checkIfAlreadyExists = false)
00526     {
00527         if (!checkIfAlreadyExists)
00528             return newAdjElement( pNode, pEdge );
00529 
00530         AdjElement* pAdj = findAdjElement(pNode, pEdge);
00531         if (!pAdj)
00532             pAdj = newAdjElement( pNode, pEdge );
00533         return pAdj;
00534     }
00535 
00537 
00543     inline void removeNode(NodeElement* pNode, EdgeElement* pEdge, bool removeDuplicates = false)
00544     {
00545         AdjElement* pAdj = findAdjElement(pNode, pEdge);
00546         if (!removeDuplicates && pAdj)
00547         {
00548             delAdjElement(pAdj);
00549         } else
00550         {
00551             while (pAdj)
00552             {
00553                 delAdjElement(pAdj);
00554                 pAdj = findAdjElement(pNode, pEdge);
00555             };
00556         }
00557     }
00558 
00560 
00566     inline AdjElement* findAdjElement(NodeElement* pNode, EdgeElement* pEdge) const
00567     {
00568         if (EdgeAdjList::size(pEdge) < NodeAdjList::size(pNode))
00569         {
00570             for (EdgeAdjList::iterator it = EdgeAdjList::begin(pEdge);
00571                     it.valid(); it++)
00572             {
00573                 if ((*it)->theNode() == pNode) return (*it);
00574             };
00575         } else
00576         {
00577             for (NodeAdjList::iterator it = NodeAdjList::begin(pNode);
00578                     it.valid(); it++)
00579             {
00580                 if ((*it)->theEdge() == pEdge) return (*it);
00581             };
00582         }
00583         return 0;
00584     }
00585 
00587     void delEdge(EdgeElement* pEdge)
00588     {
00589         for (EdgeAdjList::iterator it = EdgeAdjList::begin(pEdge); it.valid();)
00590         {
00591             AdjElement* pAdj = *it;
00592             NodeAdjList::remove( pAdj->theNode(), pAdj );
00593             it = EdgeAdjList::remove( pEdge, it );
00594             freeAdjElement( pAdj );
00595         };
00596         EdgeList::remove( this, pEdge );
00597         freeEdgeElement( pEdge );
00598     }
00599 
00601     void delNode(NodeElement* pNode)
00602     {
00603         for (NodeAdjList::iterator it = NodeAdjList::begin(pNode); it.valid();)
00604         {
00605             AdjElement* pAdj = *it;
00606             EdgeAdjList::remove( pAdj->theEdge(), pAdj );
00607             it = NodeAdjList::remove( pNode, it );
00608             freeAdjElement( pAdj );
00609         };
00610         NodeList::remove( this, pNode );
00611         freeNodeElement( pNode );
00612     }
00613 
00614     inline int numberOfNodes() const {  return NodeList::size(this);  };
00615     inline int numberOfEdges() const {  return EdgeList::size(this);  };
00616 
00618     void clear()
00619     {
00620         while (numberOfNodes())
00621         {
00622             delNode( NodeList::front(this) );
00623         };
00624 
00625         while (numberOfEdges())
00626         {
00627             delEdge( EdgeList::front(this) );
00628         };
00629     };
00630 
00631     void toCliqueGraph(Graph* pG,
00632                        ogdf::NodeArray<NodeElement*>* pNodeMap = 0,
00633                        ogdf::EdgeArray<EdgeElement*>* pEdgeMap = 0)
00634     {
00635         HyperGraph::NodeArray<ogdf::node> hgNode_to_gNode(this);
00636         for (NodeList::iterator it = HyperGraph::NodeList::begin(this); it.valid(); it++)
00637         {
00638             NodeElement* hgNode = *it;
00639             ogdf::node gNode  = pG->newNode();
00640             hgNode_to_gNode[ hgNode ] = gNode;
00641             if (pNodeMap)
00642                 (*pNodeMap)[gNode] = hgNode;
00643         };
00644 
00645         for (HyperGraph::EdgeList::iterator it = HyperGraph::EdgeList::begin(this); it.valid(); it++)
00646         {
00647             EdgeElement* hgEdge = *it;
00648             for (HyperGraph::EdgeAdjList::iterator adj_it = HyperGraph::EdgeAdjList::begin(hgEdge); adj_it.valid(); adj_it++)
00649             {
00650                 for (HyperGraph::EdgeAdjList::iterator adj_it2 = adj_it.succ(); adj_it2.valid(); adj_it2++)
00651                 {
00652                     NodeElement* hgNode = (*adj_it)->theNode();
00653                     NodeElement* hgNode2 = (*adj_it2)->theNode();
00654                     ogdf::node gNode  = hgNode_to_gNode[ hgNode ];
00655                     ogdf::node gNode2  = hgNode_to_gNode[ hgNode2 ];
00656 
00657                     ogdf::edge gEdge = pG->newEdge(gNode, gNode2);
00658                     if (pEdgeMap)
00659                         (*pEdgeMap)[gEdge] = hgEdge;
00660                 };
00661             };
00662         };
00663     };
00664 
00665     void toStarGraph(Graph* pG,
00666                      ogdf::NodeArray<NodeElement*>* pNodeMap = 0,
00667                      ogdf::EdgeArray<EdgeElement*>* pEdgeMap = 0)
00668     {
00669         HyperGraph::NodeArray<ogdf::node> hgNode_to_gNode(this);
00670         for (NodeList::iterator it = HyperGraph::NodeList::begin(this); it.valid(); it++)
00671         {
00672             NodeElement* hgNode = *it;
00673             ogdf::node gNode  = pG->newNode();
00674             hgNode_to_gNode[ hgNode ] = gNode;
00675             if (pNodeMap)
00676                 (*pNodeMap)[gNode] = hgNode;
00677         };
00678 
00679         for (HyperGraph::EdgeList::iterator it = HyperGraph::EdgeList::begin(this); it.valid(); it++)
00680         {
00681             EdgeElement* hgEdge = *it;
00682             ogdf::node gNodeDummy  = pG->newNode();
00683             if (pNodeMap)
00684                 (*pNodeMap)[gNodeDummy] = 0;
00685 
00686             for (HyperGraph::EdgeAdjList::iterator adj_it = HyperGraph::EdgeAdjList::begin(hgEdge); adj_it.valid(); adj_it++)
00687             {
00688                 NodeElement* hgNode = (*adj_it)->theNode();
00689                 ogdf::node gNode  = hgNode_to_gNode[ hgNode ];
00690                 ogdf::edge gEdge = pG->newEdge(gNodeDummy, gNode);
00691                 if (pEdgeMap)
00692                     (*pEdgeMap)[gEdge] = hgEdge;
00693             };
00694         };
00695     };
00696 }; // end of class HyperGraph
00697 
00698 template<typename ListType, typename ArrayType>
00699 static void writeToStream(std::ostream& outStream, ArrayType& array)
00700 {
00701     for (typename ListType::iterator it = ListType::begin(array.graph());it.valid(); it++)
00702     {
00703         outStream << array[*it] << std::endl;
00704     };
00705 };
00706 
00707 template<typename ListType, typename ArrayType>
00708 static void readFromStream(std::istream& inStream, ArrayType& array)
00709 {
00710     for (typename ListType::iterator it = ListType::begin(array.graph());it.valid(); it++)
00711     {
00712         inStream >> array[(*it)];
00713     };
00714 };
00715 
00716 template<typename T>
00717 static std::ostream& operator<<(std::ostream& outStream, HyperGraph::NodeArray<T>& array)
00718 {
00719     writeToStream<HyperGraph::NodeList, HyperGraph::NodeArray<T> >(outStream, array);
00720     return outStream;
00721 };
00722 
00723 template<typename T>
00724 static std::ostream& operator<<(std::ostream& outStream, HyperGraph::EdgeArray<T>& array)
00725 {
00726     writeToStream<HyperGraph::EdgeList, HyperGraph::EdgeArray<T> >(outStream, array);
00727     return outStream;
00728 };
00729 
00730 template<typename T>
00731 static std::ostream& operator<<(std::ostream& outStream, HyperGraph::AdjArray<T>& array)
00732 {
00733     for (HyperGraph::EdgeList::iterator it = HyperGraph::EdgeList::begin(array.graph());it.valid(); it++)
00734     {
00735         HyperGraph::edge e = *it;
00736         for (HyperGraph::EdgeAdjList::iterator adj_it = HyperGraph::EdgeAdjList::begin(e); adj_it.valid(); adj_it++)
00737         {
00738             outStream << array[(*adj_it)] << std::endl;
00739         };
00740     };
00741     return outStream;
00742 };
00743 
00744 template<typename T>
00745 static std::istream& operator>>(std::istream& inStream, HyperGraph::NodeArray<T>& array)
00746 {
00747     readFromStream<HyperGraph::NodeList, HyperGraph::NodeArray<T> >(inStream, array);
00748     return inStream;
00749 };
00750 
00751 template<typename T>
00752 static std::istream& operator>>(std::istream& inStream, HyperGraph::EdgeArray<T>& array)
00753 {
00754     readFromStream<HyperGraph::EdgeList, HyperGraph::EdgeArray<T> >(inStream, array);
00755     return inStream;
00756 };
00757 
00758 template<typename T>
00759 static std::ostream& operator>>(std::istream& inStream, HyperGraph::AdjArray<T>& array)
00760 {
00761     for (HyperGraph::EdgeList::iterator it = HyperGraph::EdgeList::begin(array.graph());it.valid(); it++)
00762     {
00763         HyperGraph::edge e = *it;
00764         for (HyperGraph::EdgeAdjList::iterator adj_it = HyperGraph::EdgeAdjList::begin(e); adj_it.valid(); adj_it++)
00765         {
00766             inStream >> array[(*adj_it)];
00767         };
00768     };
00769     return inStream;
00770 };
00771 
00772 static std::ostream& operator<<(std::ostream& outStream, HyperGraph& graph)
00773 {
00774     outStream << graph.numberOfNodes() << std::endl;
00775     outStream << graph.numberOfEdges() << std::endl;
00776 
00777     HyperGraph::NodeArray<int> packed_index(&graph);
00778 
00779     int i=0;
00780     for (HyperGraph::NodeList::iterator it = HyperGraph::NodeList::begin(&graph);it.valid(); it++)
00781     {
00782         packed_index[*it] = i++;
00783     };
00784 
00785     for (HyperGraph::EdgeList::iterator it = HyperGraph::EdgeList::begin(&graph);it.valid(); it++)
00786     {
00787         HyperGraph::edge e = *it;
00788         outStream << e->cardinality() << std::endl;
00789         for (HyperGraph::EdgeAdjList::iterator adj_it = HyperGraph::EdgeAdjList::begin(e); adj_it.valid(); adj_it++)
00790         {
00791             outStream << packed_index[(*adj_it)->theNode()] << std::endl;
00792         };
00793     };
00794     return outStream;
00795 };
00796 
00797 static std::istream& operator>>(std::istream& inStream, HyperGraph& graph)
00798 {
00799     int numNodes;
00800     int numEdges;
00801     int numAdjElements;
00802     inStream >> numNodes;
00803     inStream >> numEdges;
00804 
00805     HyperGraph::node* pNodes = new HyperGraph::node[numNodes];
00806     for (int i=0; i<numNodes;i++)
00807         pNodes[i] = graph.newNode();
00808 
00809     for (int i=0; i<numEdges;i++)
00810     {
00811         HyperGraph::edge e = graph.newEdge();
00812         int numAdj;
00813         inStream >> numAdj;
00814         for (int j=0; j<numAdj; j++)
00815         {
00816             int packedNodeIndex;
00817             inStream >> packedNodeIndex;
00818             graph.addNode(pNodes[packedNodeIndex], e);
00819         };
00820     };
00821     return inStream;
00822 };
00823 
00824 } // end of namespace ogdf
00825 
00826 #endif /* HYPERGRAPH_H_ */