Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

Hypergraph.h
Go to the documentation of this file.
1 
34 #pragma once
35 
36 #include <ogdf/basic/List.h>
37 #include <ogdf/basic/GraphList.h>
38 
40 #define forall_adj_elements(adj,ge) for((adj)=(v)->firstAdj();(adj);(adj)=(adj)->succ())
41 
43 #define forall_hypernodes(v,H) for((v)=(H).firstHypernode(); (v); (v)=(v)->succ())
44 
46 #define forall_rev_hypernodes(v,H) for((v)=(H).lastHypernode(); (v); (v)=(v)->pred())
47 
49 #define forall_hyperedges(e,H) for((e)=(H).firstHyperedge(); (e); (e)=(e)->succ())
50 
52 #define forall_rev_hyperedges(e,H) for((e)=(H).lastHyperedge(); (e); (e)=(e)->pred())
53 
54 namespace ogdf {
55 
56 class OGDF_EXPORT Hypergraph;
57 class OGDF_EXPORT HypernodeElement;
58 class OGDF_EXPORT HyperedgeElement;
59 class OGDF_EXPORT AdjHypergraphElement;
60 
63 
66 
69 
71 
76 {
77  friend class Hypergraph;
78  friend class GraphListBase;
80 
81 private:
82 
84  GraphElement *m_element;
85 
87 
94 
96  int m_index;
97 
99  explicit AdjHypergraphElement(GraphElement *pElement)
100  : m_element(pElement), m_twin(nullptr), m_index(0)
101  { }
102 
104  AdjHypergraphElement(GraphElement *pElement, int pIndex)
105  : m_element(pElement), m_twin(nullptr), m_index(pIndex)
106  { }
107 
108 public:
109 
111  int index() const
112  {
113  return m_index;
114  }
115 
117 
122  GraphElement * element() const
123  {
124  return m_element;
125  }
126 
129  {
130  return m_twin;
131  }
132 
135  {
136  return static_cast<adjHypergraphEntry>(m_next);
137  }
138 
141  {
142  return static_cast<adjHypergraphEntry>(m_prev);
143  }
144 
146  adjHypergraphEntry cyclicSucc() const;
147 
149  adjHypergraphEntry cyclicPred() const;
150 
152 };
153 
156 {
157  friend class Hypergraph;
158  friend class GraphListBase;
160 
161 private:
162 
165 
167  int m_index;
168 
171 
174 
176 
179  explicit HyperedgeElement(int pIndex)
180  : m_index(pIndex), m_cardinality(0), m_hypergraph(nullptr) { }
181 
182 public:
183 
185  int index() const
186  {
187  return m_index;
188  }
189 
191  int cardinality() const
192  {
193  return m_cardinality;
194  }
195 
198  {
199  return m_hypergraph;
200  }
201 
204  {
205  return m_adjHypernodes.head();
206  }
207 
210  {
211  return m_adjHypernodes.tail();
212  }
213 
216  {
217  return m_adjHypernodes;
218  }
219 
221  template<class NODELIST> void allHypernodes(NODELIST &hypernodes) const
222  {
223  hypernodes.clear();
224  for (adjHypergraphEntry adj = firstAdj(); adj; adj = adj->succ())
225  hypernodes.pushBack(reinterpret_cast<hypernode>(adj->element()));
226  }
227 
229  bool incident(hypernode v) const
230  {
231  for (adjHypergraphEntry adj = firstAdj(); adj; adj = adj->succ()) {
232  if (reinterpret_cast<hypernode>(adj->element()) == v) {
233  return true;
234  }
235  }
236  return false;
237  }
238 
240  hyperedge succ() const
241  {
242  return static_cast<hyperedge>(m_next);
243  }
244 
246  hyperedge pred() const
247  {
248  return static_cast<hyperedge>(m_prev);
249  }
250 
252  bool operator==(const hyperedge e) const
253  {
254  return e->index() == m_index && e->hypergraph() == m_hypergraph;
255  }
256 
257  friend std::ostream & operator<<(std::ostream &os, ogdf::hyperedge e);
258 
260 };
261 
264 {
265  friend class Hypergraph;
266  friend class GraphListBase;
268 
269 public:
270 
272  enum class Type {
273  normal = 0x0000001,
274  dummy = 0x0000002,
275  OR = 0x0000003,
276  BUF = 0x0000004,
277  AND = 0x0000005,
278  NOR = 0x0000006,
279  NOT = 0x0000007,
280  XOR = 0x0000008,
281  DFF = 0x0000009,
282  NAND = 0x0000010,
283  INPUT = 0x0000011,
284  OUTPUT = 0x0000012
285  };
286 
287 private:
288 
291 
293  int m_index;
294 
296  int m_degree;
297 
300 
303 
305  explicit HypernodeElement(int pIndex)
306  : m_index(pIndex), m_degree(0), m_type(Type::normal), m_hypergraph(nullptr)
307  {
308  }
309 
311  HypernodeElement(int pIndex, Type pType)
312  : m_index(pIndex), m_degree(0), m_type(pType), m_hypergraph(nullptr)
313  {
314  }
315 
316 public:
317 
319  int index() const
320  {
321  return m_index;
322  }
323 
325  int degree() const
326  {
327  return m_degree;
328  }
329 
332  {
333  return m_hypergraph;
334  }
335 
337  Type type() const
338  {
339  return m_type;
340  }
341 
343  void type(Type pType)
344  {
345  m_type = pType;
346  }
347 
350  {
351  return m_adjHyperedges.head();
352  }
353 
356  {
357  return m_adjHyperedges.tail();
358  }
359 
361  template<class NODELIST> void allHyperedges(NODELIST &hyperedges) const
362  {
363  hyperedges.clear();
364  for (adjHypergraphEntry adj = firstAdj(); adj; adj = adj->succ())
365  hyperedges.pushBack(reinterpret_cast<hyperedge>(adj->element()));
366  }
367 
369  bool adjacent(hypernode v) const
370  {
371  for (adjHypergraphEntry adj = firstAdj(); adj; adj = adj->succ()) {
372  if (reinterpret_cast<hyperedge>(adj->element())->incident(v)) {
373  return true;
374  }
375  }
376  return false;
377  }
378 
380  hypernode succ() const
381  {
382  return static_cast<hypernode>(m_next);
383  }
384 
386  hypernode pred() const
387  {
388  return static_cast<hypernode>(m_prev);
389  }
390 
392  bool operator==(const hypernode v) const
393  {
394  return v->index() == m_index && v->hypergraph() == m_hypergraph;
395  }
396 
398 };
399 
400 class HypergraphArrayBase;
401 template<class T> class HypernodeArray;
402 template<class T> class HyperedgeArray;
404 
406 {
409 
412 
415 
418 
421 
424 
427 
430 
435 
436 public:
437 
439  Hypergraph();
440 
442  Hypergraph(const Hypergraph &H);
443 
445  ~Hypergraph();
446 
448  bool empty() const
449  {
450  return m_nHypernodes == 0;
451  }
452 
455  {
456  return m_hypernodes;
457  }
458 
461  {
462  return m_hyperedges;
463  }
464 
466  int numberOfHypernodes() const
467  {
468  return m_nHypernodes;
469  }
470 
472  int numberOfHyperedges() const
473  {
474  return m_nHyperedges;
475  }
476 
478  int maxHypernodeIndex() const
479  {
480  return m_hypernodeIdCount - 1;
481  }
482 
484  int maxHyperedgeIndex() const
485  {
486  return m_hyperedgeIdCount - 1;
487  }
488 
491  {
492  return m_hypernodes.head();
493  }
494 
497  {
498  return m_hypernodes.tail();
499  }
500 
503  {
504  return m_hyperedges.head();
505  }
506 
509  {
510  return m_hyperedges.tail();
511  }
512 
515  {
516  return m_hypernodeArrayTableSize;
517  }
518 
521  {
522  return m_hyperedgeArrayTableSize;
523  }
524 
526  hypernode newHypernode();
527 
529  hypernode newHypernode(int pIndex);
530 
532  hypernode newHypernode(HypernodeElement::Type pType);
533 
535  hypernode newHypernode(int pIndex, HypernodeElement::Type pType);
536 
538 
542  hyperedge newHyperedge(List<hypernode> &hypernodes);
543 
545 
550  hyperedge newHyperedge(int pIndex, List<hypernode> &hypernodes);
551 
553 
556  void delHypernode(hypernode v);
557 
559 
562  void delHyperedge(hyperedge e);
563 
565  void clear();
566 
568  hypernode randomHypernode() const;
569 
571  hyperedge randomHyperedge() const;
572 
574  template<class LIST> void allHypernodes(LIST &hypernodeList) const
575  {
576  hypernodeList.clear();
577  for (hypernode v = m_hypernodes.head(); v; v = v->succ())
578  hypernodeList.pushBack(v);
579  }
580 
582  template<class LIST> void allHyperedges(LIST &hyperedgeList) const
583  {
584  hyperedgeList.clear();
585  for (hyperedge e = m_hyperedges.head(); e; e = e->succ())
586  hyperedgeList.pushBack(e);
587  }
588 
590  void readBenchHypergraph(std::istream &is);
591 
593  void readBenchHypergraph(const char *filename);
594 
596  void readPlaHypergraph(std::istream &is);
597 
599  void loadPlaHypergraph(const char *fileName);
600 
602  bool consistency() const;
603 
606  registerHypernodeArray(HypergraphArrayBase *pHypernodeArray) const;
607 
609  registerHyperedgeArray(HypergraphArrayBase *pHyperedgeArray) const;
610 
613  registerObserver(HypergraphObserver *pObserver) const;
614 
616  void unregisterHypernodeArray(ListIterator<HypergraphArrayBase *> it) const;
617 
619  void unregisterHyperedgeArray(ListIterator<HypergraphArrayBase *> it) const;
620 
622  void unregisterObserver(ListIterator<HypergraphObserver *> it) const;
623 
624  Hypergraph &operator=(const Hypergraph &H);
625 
626  friend std::ostream & operator<<(std::ostream &os, ogdf::Hypergraph &H);
627 
628  friend std::istream & operator>>(std::istream &is, ogdf::Hypergraph &H);
629 
631 
632 private:
633 
634  void initArrays();
635 
636  void initObservers();
637 
638  int nextEntry(char *buffer, int from, string stop);
639 
640  HypernodeElement::Type gateType(string gate);
641 };
642 
643 }
ogdf::Hypergraph::numberOfHyperedges
int numberOfHyperedges() const
Returns the number of hyperedges in the hypergraph.
Definition: Hypergraph.h:472
ogdf::Hypergraph::maxHyperedgeIndex
int maxHyperedgeIndex() const
Returns the largest used hyperedge index.
Definition: Hypergraph.h:484
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::HyperedgeArray
Dynamic arrays indexed with nodes.
Definition: Hypergraph.h:402
ogdf::Hypergraph::m_hypernodeArrays
ListPure< HypergraphArrayBase * > m_hypernodeArrays
The registered hypergraph arrays & observers.
Definition: Hypergraph.h:432
ogdf::AdjHypergraphElement::element
GraphElement * element() const
Returns the element associated with this adjacency entry.
Definition: Hypergraph.h:122
ogdf::internal::GraphList::tail
T * tail() const
Returns the last element in the list.
Definition: GraphList.h:297
ogdf::Hypergraph::allHyperedges
void allHyperedges(LIST &hyperedgeList) const
Returns a list with all hyperedges of the hypergraph.
Definition: Hypergraph.h:582
ogdf::Hypergraph::OGDF_MALLOC_NEW_DELETE
OGDF_MALLOC_NEW_DELETE
Definition: Hypergraph.h:630
ogdf::Hypergraph::allHypernodes
void allHypernodes(LIST &hypernodeList) const
Returns a list with all hypernodes of the hypergraph.
Definition: Hypergraph.h:574
ogdf::HyperedgeElement::cardinality
int cardinality() const
Returns the number of incident hypernodes.
Definition: Hypergraph.h:191
ogdf::AdjHypergraphElement::pred
adjHypergraphEntry pred() const
Returns the predecessor in the adjacency list.
Definition: Hypergraph.h:140
ogdf::HypernodeArray
Dynamic arrays indexed with hypernodes.
Definition: Hypergraph.h:401
ogdf::internal::GraphElement
The base class for objects used by (hyper)graphs.
Definition: GraphList.h:55
ogdf::Hypergraph::m_nHyperedges
int m_nHyperedges
The number of hyperedges in the hypergraph.
Definition: Hypergraph.h:417
ogdf::HypernodeElement::HypernodeElement
HypernodeElement(int pIndex, Type pType)
Constructor.
Definition: Hypergraph.h:311
ogdf::Hypergraph::hypernodes
internal::GraphList< HypernodeElement > hypernodes() const
Returns the list of all hypernodes.
Definition: Hypergraph.h:454
ogdf::HyperedgeElement::OGDF_NEW_DELETE
OGDF_NEW_DELETE
Definition: Hypergraph.h:259
ogdf::HyperedgeElement::incident
bool incident(hypernode v) const
Returns true iff v is incident to the hyperedge.
Definition: Hypergraph.h:229
ogdf::Hypergraph::m_hyperedges
internal::GraphList< HyperedgeElement > m_hyperedges
The list of all hyperedges.
Definition: Hypergraph.h:411
ogdf::AdjHypergraphElement::m_index
int m_index
The (unique) index of the adjacency entry.
Definition: Hypergraph.h:96
ogdf::HyperedgeElement::HyperedgeElement
HyperedgeElement(int pIndex)
Constructs an hyperedge element between hypernodes.
Definition: Hypergraph.h:179
ogdf::Hypergraph::m_hyperedgeArrayTableSize
int m_hyperedgeArrayTableSize
The current table size of hyperedge arrays within the hypergraph.
Definition: Hypergraph.h:429
ogdf::AdjHypergraphElement::m_element
GraphElement * m_element
The associated hyperedge or hypernode.
Definition: Hypergraph.h:84
ogdf::HyperedgeElement
Class for the representation of hyperedges.
Definition: Hypergraph.h:155
ogdf::HypernodeElement::firstAdj
adjHypergraphEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition: Hypergraph.h:349
ogdf::HypernodeElement::m_degree
int m_degree
The number of incident hyperedges.
Definition: Hypergraph.h:296
ogdf::AdjHypergraphElement::succ
adjHypergraphEntry succ() const
Returns the successor in the adjacency list.
Definition: Hypergraph.h:134
ogdf::HypernodeElement::pred
hypernode pred() const
Returns the predecessor in the list of all hypernodes.
Definition: Hypergraph.h:386
ogdf::Hypergraph::hyperedgeArrayTableSize
int hyperedgeArrayTableSize() const
Returns the table size of hyperedge arrays within the hypergraph.
Definition: Hypergraph.h:520
ogdf::Hypergraph::m_hyperedgeArrays
ListPure< HypergraphArrayBase * > m_hyperedgeArrays
Definition: Hypergraph.h:433
ogdf::HypergraphArrayBase
Abstract base class for hypergraph arrays.
Definition: HypergraphArray.h:41
ogdf::HyperedgeElement::incidentHypernodes
internal::GraphList< AdjHypergraphElement > incidentHypernodes() const
Returns the incident hypernodes of the hyperedge.
Definition: Hypergraph.h:215
ogdf::Hypergraph::lastHyperEdge
hyperedge lastHyperEdge() const
Returns the last hyperedge in the list of all hyperedges.
Definition: Hypergraph.h:508
ogdf::HypernodeElement::type
void type(Type pType)
Sets the type of hypernode.
Definition: Hypergraph.h:343
ogdf::HyperedgeElement::index
int index() const
Returns the index of a hyperedge.
Definition: Hypergraph.h:185
ogdf::Hypergraph::maxHypernodeIndex
int maxHypernodeIndex() const
Returns the largest used hypernode index.
Definition: Hypergraph.h:478
ogdf::Hypergraph::m_nHypernodes
int m_nHypernodes
The number of hypernodes in the hypergraph.
Definition: Hypergraph.h:414
ogdf::HypernodeElement::OGDF_NEW_DELETE
OGDF_NEW_DELETE
Definition: Hypergraph.h:397
ogdf::AdjHypergraphElement
Class for adjacency list elements.
Definition: Hypergraph.h:75
ogdf::HypernodeElement::Type
Type
The type of hypernodes.
Definition: Hypergraph.h:272
ogdf::HyperedgeElement::m_cardinality
int m_cardinality
The number of incidend hypernodes.
Definition: Hypergraph.h:170
ogdf::HypernodeElement::m_hypergraph
Hypergraph * m_hypergraph
The hypergraph containing the hypernode (if any).
Definition: Hypergraph.h:302
GraphList.h
Decralation of GraphElement and GraphList classes.
ogdf::Hypergraph::firstHyperedge
hyperedge firstHyperedge() const
Returns the first hyperedge in the list of all hyperedges.
Definition: Hypergraph.h:502
ogdf::Hypergraph::m_hyperedgeIdCount
int m_hyperedgeIdCount
The Index that will be assigned to the next created hyperedge.
Definition: Hypergraph.h:423
ogdf::HypernodeElement::hypergraph
Hypergraph * hypergraph() const
Returns the hypergraph containing the hypernode.
Definition: Hypergraph.h:331
ogdf::AdjHypergraphElement::twin
adjHypergraphEntry twin() const
Returns the pointer to a twin adjacency list.
Definition: Hypergraph.h:128
ogdf::AdjHypergraphElement::AdjHypergraphElement
AdjHypergraphElement(GraphElement *pElement, int pIndex)
Constructs an adjacency entry for a given hyper{node,edge} and index.
Definition: Hypergraph.h:104
ogdf::HypernodeElement::m_adjHyperedges
internal::GraphList< AdjHypergraphElement > m_adjHyperedges
The adjacency list of the hypernode.
Definition: Hypergraph.h:290
ogdf::Hypergraph::m_hypernodes
internal::GraphList< HypernodeElement > m_hypernodes
The list of all hypernodes.
Definition: Hypergraph.h:408
ogdf::Hypergraph::m_observers
ListPure< HypergraphObserver * > m_observers
Definition: Hypergraph.h:434
ogdf::HyperedgeElement::hypergraph
Hypergraph * hypergraph() const
Returns the hypergraph containing the hyperedge.
Definition: Hypergraph.h:197
ogdf::HyperedgeElement::pred
hyperedge pred() const
Returns the predecessor in the list of all hyperedges.
Definition: Hypergraph.h:246
ogdf::operator<<
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition: Array.h:949
ogdf::Hypergraph::empty
bool empty() const
Returns true iff the hypergraph is empty (ie. contains no hypernodes).
Definition: Hypergraph.h:448
ogdf::Hypergraph::numberOfHypernodes
int numberOfHypernodes() const
Returns the number of hypernodes in the hypergraph.
Definition: Hypergraph.h:466
ogdf::HypernodeElement::m_index
int m_index
The (unique) index of the hypernode.
Definition: Hypergraph.h:293
ogdf::Hypergraph::m_hypernodeArrayTableSize
int m_hypernodeArrayTableSize
The current table size of hypernode arrays within the hypergraph.
Definition: Hypergraph.h:426
ogdf::HypernodeElement::index
int index() const
Returns the (unique) hypernode index.
Definition: Hypergraph.h:319
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: List.h:40
ogdf::internal::GraphList
Lists of graph objects (like nodes, edges, etc.).
Definition: GraphList.h:277
ogdf::HyperedgeElement::m_hypergraph
Hypergraph * m_hypergraph
The hypergraph containing the hyperedge (if any).
Definition: Hypergraph.h:173
ogdf::HyperedgeElement::firstAdj
adjHypergraphEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition: Hypergraph.h:203
ogdf::AdjHypergraphElement::m_twin
adjHypergraphEntry m_twin
The corresponding adjacency entry.
Definition: Hypergraph.h:93
ogdf::HypernodeElement::adjacent
bool adjacent(hypernode v) const
Returns true iff v is adjacent to the hypernode.
Definition: Hypergraph.h:369
ogdf::HyperedgeElement::succ
hyperedge succ() const
Returns the successor in the list of all hyperedges.
Definition: Hypergraph.h:240
ogdf::HypernodeElement::allHyperedges
void allHyperedges(NODELIST &hyperedges) const
Returns a list with all incident hyperedges of the hypernode.
Definition: Hypergraph.h:361
ogdf::AdjHypergraphElement::index
int index() const
Returns the index of this adjacency element.
Definition: Hypergraph.h:111
ogdf::HyperedgeElement::operator==
bool operator==(const hyperedge e) const
Equality operator.
Definition: Hypergraph.h:252
ogdf::ListPure
Doubly linked lists.
Definition: List.h:41
ogdf::Hypergraph::firstHypernode
hypernode firstHypernode() const
Returns the first hypernode in the list of all hypernodes.
Definition: Hypergraph.h:490
ogdf::AdjHypergraphElement::OGDF_NEW_DELETE
OGDF_NEW_DELETE
Definition: Hypergraph.h:151
ogdf::Hypergraph::lastHypernode
hypernode lastHypernode() const
Returns the last hypernode in the list of all hypernodes.
Definition: Hypergraph.h:496
ogdf::HyperedgeElement::m_adjHypernodes
internal::GraphList< AdjHypergraphElement > m_adjHypernodes
The adjacency list of the hyperedge.
Definition: Hypergraph.h:164
ogdf::internal::GraphList::head
T * head() const
Returns the first element in the list.
Definition: GraphList.h:294
ogdf::HypernodeElement::operator==
bool operator==(const hypernode v) const
Equality operator.
Definition: Hypergraph.h:392
ogdf::HypernodeElement::degree
int degree() const
Returns the hypernode degree.
Definition: Hypergraph.h:325
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::Hypergraph::hyperedges
internal::GraphList< HyperedgeElement > hyperedges() const
Returns the list of all hyperedges.
Definition: Hypergraph.h:460
ogdf::Hypergraph::hypernodeArrayTableSize
int hypernodeArrayTableSize() const
Returns the table size of hypernode arrays with the hypergraph.
Definition: Hypergraph.h:514
ogdf::HypernodeElement::succ
hypernode succ() const
Returns the successor in the list of all hypernodes.
Definition: Hypergraph.h:380
ogdf::HyperedgeElement::allHypernodes
void allHypernodes(NODELIST &hypernodes) const
Returns a list with all incident hypernodes of the hyperedge.
Definition: Hypergraph.h:221
ogdf::HypernodeElement::lastAdj
adjHypergraphEntry lastAdj() const
Returns the last entry in the adjacency list.
Definition: Hypergraph.h:355
List.h
Declaration of doubly linked lists and iterators.
ogdf::HypernodeElement::HypernodeElement
HypernodeElement(int pIndex)
Constructor.
Definition: Hypergraph.h:305
ogdf::operator>>
std::istream & operator>>(std::istream &is, TokenIgnorer token)
ogdf::HypernodeElement::type
Type type() const
Returns the type of hypernode.
Definition: Hypergraph.h:337
ogdf::ListIteratorBase
Encapsulates a pointer to a list element.
Definition: List.h:42
ogdf::HyperedgeElement::lastAdj
adjHypergraphEntry lastAdj() const
Returns the last entry in the adjacency list.
Definition: Hypergraph.h:209
ogdf::HypernodeElement::m_type
Type m_type
The type of the hypernode.
Definition: Hypergraph.h:299
ogdf::HypergraphObserver
Definition: HypergraphObserver.h:48
ogdf::Hypergraph
Definition: Hypergraph.h:405
ogdf::AdjHypergraphElement::AdjHypergraphElement
AdjHypergraphElement(GraphElement *pElement)
Constructs an adjacency element for a given hyper{node,edge}.
Definition: Hypergraph.h:99
ogdf::HyperedgeElement::m_index
int m_index
The (unique) index of the hyperedge.
Definition: Hypergraph.h:167
ogdf::HypernodeElement
Class for the representation of hypernodes.
Definition: Hypergraph.h:263
ogdf::Hypergraph::m_hypernodeIdCount
int m_hypernodeIdCount
The Index that will be assigned to the next created hypernode.
Definition: Hypergraph.h:420