Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

EdgeArray.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/Graph_d.h>
35 
36 
37 namespace ogdf {
38 
39 
41 
51 
52 public:
53  const Graph *m_pGraph;
54 
56  EdgeArrayBase() : m_pGraph(nullptr) { }
57 
59  explicit EdgeArrayBase(const Graph *pG) : m_pGraph(pG) {
60  if(pG) m_it = pG->registerArray(this);
61  }
62 
66  base.m_pGraph = nullptr;
68  }
69 
70  // destructor, unregisters the array
71  virtual ~EdgeArrayBase() {
73  }
74 
75  // event interface used by Graph
77  virtual void enlargeTable(int newTableSize) = 0;
79  virtual void reinit(int initTableSize) = 0;
81  virtual void disconnect() = 0;
82 
84  void reregister(const Graph *pG) {
86  if ((m_pGraph = pG) != nullptr) m_it = pG->registerArray(this);
87  }
88 
92  m_pGraph = base.m_pGraph;
93  m_it = base.m_it;
94  base.m_pGraph = nullptr;
96  if (m_pGraph != nullptr)
98  }
99 };
100 
102 
112 template<class T> class EdgeArray : private Array<T>, protected EdgeArrayBase {
113  T m_x;
114 
115 public:
117  using key_type = edge;
119  using value_type = T;
120 
125 
126 
128  EdgeArray() : Array<T>(), EdgeArrayBase() { }
129 
131  explicit EdgeArray(const Graph &G) : Array<T>(G.edgeArrayTableSize()), EdgeArrayBase(&G) { }
132 
134 
138  EdgeArray(const Graph &G, const T &x) :
139  Array<T>(0,G.edgeArrayTableSize()-1,x), EdgeArrayBase(&G), m_x(x) { }
140 
142 
146 
148 
152 
153 
159 
161  bool valid() const { return Array<T>::low() <= Array<T>::high(); }
162 
164  const Graph *graphOf() const {
165  return m_pGraph;
166  }
167 
169  const T &operator[](edge e) const {
170  OGDF_ASSERT(e != nullptr);
171  OGDF_ASSERT(e->graphOf() == m_pGraph);
172  return Array<T>::operator [](e->index());
173  }
174 
176  T &operator[](edge e) {
177  OGDF_ASSERT(e != nullptr);
178  OGDF_ASSERT(e->graphOf() == m_pGraph);
179  return Array<T>::operator [](e->index());
180  }
181 
183  const T &operator()(edge e) const {
184  OGDF_ASSERT(e != nullptr);
185  OGDF_ASSERT(e->graphOf() == m_pGraph);
186  return Array<T>::operator [](e->index());
187  }
188 
190  T &operator()(edge e) {
191  OGDF_ASSERT(e != nullptr);
192  OGDF_ASSERT(e->graphOf() == m_pGraph);
193  return Array<T>::operator [](e->index());
194  }
195 
197  const T &operator[](adjEntry adj) const {
198  OGDF_ASSERT(adj != nullptr);
199  return Array<T>::operator [](adj->index() >> 1);
200  }
201 
204  OGDF_ASSERT(adj != nullptr);
205  return Array<T>::operator [](adj->index() >> 1);
206  }
207 
209  const T &operator()(adjEntry adj) const {
210  OGDF_ASSERT(adj != nullptr);
211  return Array<T>::operator [](adj->index() >> 1);
212  }
213 
216  OGDF_ASSERT(adj != nullptr);
217  return Array<T>::operator [](adj->index() >> 1);
218  }
219 
222  OGDF_DEPRECATED("Edge arrays should be indexed by an edge, not an integer index.")
223  const T &operator[](int index) const
224  { return Array<T>::operator [](index); }
225 
228  OGDF_DEPRECATED("Edge arrays should be indexed by an edge, not an integer index.")
229  T &operator[](int index)
230  { return Array<T>::operator [](index); }
231 
233 
238 
240 
243  iterator begin() { return iterator(m_pGraph->firstEdge(), this); }
244 
246 
249  const_iterator begin() const { return const_iterator(m_pGraph->firstEdge(), this); }
250 
252 
255  const_iterator cbegin() const { return const_iterator(m_pGraph->firstEdge(), this); }
256 
258 
261  iterator end() { return iterator(nullptr, this); }
262 
264 
267  const_iterator end() const { return const_iterator(nullptr, this); }
268 
270 
273  const_iterator cend() const { return const_iterator(nullptr, this); }
274 
276 
281 
283  void init() {
284  Array<T>::init(); reregister(nullptr);
285  }
286 
288  void init(const Graph &G) {
289  Array<T>::init(G.edgeArrayTableSize()); reregister(&G);
290  }
291 
293 
297  void init(const Graph &G, const T &x) {
298  Array<T>::init(0,G.edgeArrayTableSize()-1, m_x = x); reregister(&G);
299  }
300 
302  void fill(const T &x) {
303  int high = m_pGraph->maxEdgeIndex();
304  if(high >= 0)
305  Array<T>::fill(0,high,x);
306  }
307 
311  m_x = a.m_x;
312  reregister(a.m_pGraph);
313  return *this;
314  }
315 
317 
322  m_x = a.m_x;
323  moveRegister(a);
324  return *this;
325  }
326 
327 
329 
334 
335  static key_type findSuccKey(key_type key) { return key->succ(); }
336  static key_type findPredKey(key_type key) { return key->pred(); }
337 
339 
340 private:
341  virtual void enlargeTable(int newTableSize) {
342  Array<T>::resize(newTableSize,m_x);
343  }
344 
345  virtual void reinit(int initTableSize) {
346  Array<T>::init(0,initTableSize-1,m_x);
347  }
348 
349  virtual void disconnect() {
350  Array<T>::init();
351  m_pGraph = nullptr;
352  }
353 
355 };
356 
358 
363 {
365 
366 public:
368 
372  explicit BucketEdgeArray(const EdgeArray<int> &edgeArray) : m_pEdgeArray(&edgeArray) { }
373 
375  int getBucket(const edge &e) override { return (*m_pEdgeArray)[e]; }
376 };
377 
378 }
ogdf::EdgeArray::operator[]
T & operator[](adjEntry adj)
Returns a reference to the element with index edge of adj.
Definition: EdgeArray.h:203
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::EdgeArrayBase::~EdgeArrayBase
virtual ~EdgeArrayBase()
Definition: EdgeArray.h:71
ogdf::embedder::MDMFLengthAttribute
Auxiliary length attribute.
Definition: MDMFLengthAttribute.h:45
ogdf::EdgeArray::EdgeArray
EdgeArray(EdgeArray< T > &&A)
Constructs an edge array containing the elements of A (move semantics).
Definition: EdgeArray.h:151
ogdf::EdgeArray::init
void init()
Reinitializes the array. Associates the array with no graph.
Definition: EdgeArray.h:283
ogdf::EdgeArray::operator()
const T & operator()(adjEntry adj) const
Returns a reference to the element with index edge of adj.
Definition: EdgeArray.h:209
ogdf::EdgeArray::EdgeArray
EdgeArray(const Graph &G)
Constructs an edge array associated with G.
Definition: EdgeArray.h:131
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::EdgeArray::EdgeArray
EdgeArray(const Graph &G, const T &x)
Constructs an edge array associated with G.
Definition: EdgeArray.h:138
ogdf::EdgeArrayBase::reinit
virtual void reinit(int initTableSize)=0
Virtual function called when table has to be reinitialized.
ogdf::EdgeArray::enlargeTable
virtual void enlargeTable(int newTableSize)
Virtual function called when table size has to be enlarged.
Definition: EdgeArray.h:341
ogdf::Graph::maxEdgeIndex
int maxEdgeIndex() const
Returns the largest used edge index.
Definition: Graph_d.h:609
OGDF_DEPRECATED
#define OGDF_DEPRECATED(reason)
Mark a class / member / function as deprecated.
Definition: config.h:118
ogdf::EdgeArray::operator=
EdgeArray< T > & operator=(EdgeArray< T > &&a)
Assignment operator (move semantics).
Definition: EdgeArray.h:320
ogdf::Graph::unregisterArray
void unregisterArray(ListIterator< NodeArrayBase * > it) const
Unregisters a node array.
ogdf::whaType::A
@ A
ogdf::Array::high
INDEX high() const
Returns the maximal array index.
Definition: Array.h:283
ogdf::EdgeArray::iterator
internal::GraphArrayIterator< EdgeArray< T > > iterator
The type for edge array iterators.
Definition: EdgeArray.h:122
ogdf::EdgeElement::index
int index() const
Returns the index of the edge.
Definition: Graph_d.h:324
ogdf::BucketEdgeArray::BucketEdgeArray
BucketEdgeArray(const EdgeArray< int > &edgeArray)
Constructs a bucket function.
Definition: EdgeArray.h:372
ogdf::EdgeArray::cend
const_iterator cend() const
Returns a const iterator to one-past-last entry in the edge array.
Definition: EdgeArray.h:273
ogdf::EdgeArray::cbegin
const_iterator cbegin() const
Returns a const iterator to the first entry in the edge array.
Definition: EdgeArray.h:255
ogdf::BucketFunc
Abstract base class for bucket functions.
Definition: basic.h:241
ogdf::Array< ogdf::embedder::MDMFLengthAttribute >::iterator
ArrayIterator< ogdf::embedder::MDMFLengthAttribute > iterator
Provides a random-access iterator that can read or modify any element in an array.
Definition: Array.h:219
ogdf::Array::init
void init()
Reinitializes the array to an array with empty index set.
Definition: Array.h:358
ogdf::EdgeArrayBase::EdgeArrayBase
EdgeArrayBase(EdgeArrayBase &base)
Moves edge array base to this edge array.
Definition: EdgeArray.h:64
ogdf::Graph::registerArray
ListIterator< NodeArrayBase * > registerArray(NodeArrayBase *pNodeArray) const
Registers a node array.
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::internal::GraphArrayIteratorBase
Definition: graph_iterators.h:102
ogdf::EdgeArray
Dynamic arrays indexed with edges.
Definition: EdgeArray.h:112
ogdf::EdgeArrayBase
Abstract base class for edge arrays.
Definition: EdgeArray.h:45
ogdf::EdgeArray::valid
bool valid() const
Returns true iff the array is associated with a graph.
Definition: EdgeArray.h:161
ogdf::EdgeArrayBase::enlargeTable
virtual void enlargeTable(int newTableSize)=0
Virtual function called when table size has to be enlarged.
ogdf::EdgeArrayBase::moveRegister
void moveRegister(EdgeArrayBase &base)
Moves array registration from base to this array.
Definition: EdgeArray.h:90
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::EdgeArrayBase::reregister
void reregister(const Graph *pG)
Associates the array with a new graph.
Definition: EdgeArray.h:84
ogdf::EdgeArray::init
void init(const Graph &G)
Reinitializes the array. Associates the array with G.
Definition: EdgeArray.h:288
ogdf::EdgeArray::operator=
EdgeArray< T > & operator=(const EdgeArray< T > &a)
Assignment operator.
Definition: EdgeArray.h:309
ogdf::edge
EdgeElement * edge
The type of edges.
Definition: Graph_d.h:67
ogdf::EdgeArray::findPredKey
static key_type findPredKey(key_type key)
Definition: EdgeArray.h:336
ogdf::EdgeArray::begin
const_iterator begin() const
Returns a const iterator to the first entry in the edge array.
Definition: EdgeArray.h:249
ogdf::BucketEdgeArray::getBucket
int getBucket(const edge &e) override
Returns bucket of edge e.
Definition: EdgeArray.h:375
backward::details::move
const T & move(const T &v)
Definition: backward.hpp:243
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
ogdf::Array::operator[]
const_reference operator[](INDEX i) const
Returns a reference to the element at position i.
Definition: Array.h:292
ogdf::Array::fill
void fill(const E &x)
Sets all elements to x.
Definition: Array.h:387
ogdf::EdgeArray::operator()
T & operator()(edge e)
Returns a reference to the element with index e.
Definition: EdgeArray.h:190
ogdf::EdgeElement::pred
edge pred() const
Returns the predecessor in the list of all edges.
Definition: Graph_d.h:358
ogdf::EdgeArray::operator[]
T & operator[](edge e)
Returns a reference to the element with index e.
Definition: EdgeArray.h:176
ogdf::EdgeArrayBase::EdgeArrayBase
EdgeArrayBase()
Initializes an edge array not associated with a graph.
Definition: EdgeArray.h:56
ogdf::EdgeArray::reinit
virtual void reinit(int initTableSize)
Virtual function called when table has to be reinitialized.
Definition: EdgeArray.h:345
ogdf::EdgeArrayBase::disconnect
virtual void disconnect()=0
Virtual function called when array is disconnected from the graph.
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::EdgeArray::fill
void fill(const T &x)
Sets all array elements to x.
Definition: EdgeArray.h:302
ogdf::EdgeArray::init
void init(const Graph &G, const T &x)
Reinitializes the array. Associates the array with G.
Definition: EdgeArray.h:297
ogdf::Array::resize
void resize(INDEX newSize, const E &x)
Resizes (enlarges or shrinks) the array to hold newSize elements and sets new elements to x.
Definition: Array.h:426
ogdf::EdgeArrayBase::EdgeArrayBase
EdgeArrayBase(const Graph *pG)
Initializes an edge array associated with pG.
Definition: EdgeArray.h:59
ogdf::Graph::firstEdge
edge firstEdge() const
Returns the first edge in the list of all edges.
Definition: Graph_d.h:626
ogdf::Array< ogdf::embedder::MDMFLengthAttribute >::const_iterator
ArrayConstIterator< ogdf::embedder::MDMFLengthAttribute > const_iterator
Provides a random-access iterator that can read a const element in an array.
Definition: Array.h:217
ogdf::BucketEdgeArray::m_pEdgeArray
const EdgeArray< int > * m_pEdgeArray
Pointer to edge array.
Definition: EdgeArray.h:364
ogdf::EdgeArray::begin
iterator begin()
Returns an iterator to the first entry in the edge array.
Definition: EdgeArray.h:243
std
Definition: GML.h:110
ogdf::EdgeArrayBase::m_pGraph
const Graph * m_pGraph
The associated graph.
Definition: EdgeArray.h:53
ogdf::Array::operator=
Array< E, INDEX > & operator=(const Array< E, INDEX > &A)
Assignment operator.
Definition: Array.h:436
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::EdgeArray::disconnect
virtual void disconnect()
Virtual function called when array is disconnected from the graph.
Definition: EdgeArray.h:349
ogdf::EdgeArray::operator[]
const T & operator[](edge e) const
Returns a reference to the element with index e.
Definition: EdgeArray.h:169
ogdf::BucketEdgeArray
Bucket function for edges.
Definition: EdgeArray.h:362
ogdf::EdgeArray::const_iterator
internal::GraphArrayConstIterator< EdgeArray< T > > const_iterator
The type for edge array const iterators.
Definition: EdgeArray.h:124
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::EdgeElement::succ
edge succ() const
Returns the successor in the list of all edges.
Definition: Graph_d.h:356
ogdf::EdgeArray::operator[]
const T & operator[](adjEntry adj) const
Returns a reference to the element with index edge of adj.
Definition: EdgeArray.h:197
ogdf::Array::low
INDEX low() const
Returns the minimal array index.
Definition: Array.h:280
ogdf::EdgeArray::EdgeArray
EdgeArray()
Constructs an empty edge array associated with no graph.
Definition: EdgeArray.h:128
ogdf::EdgeArray::EdgeArray
EdgeArray(const EdgeArray< T > &A)
Constructs an edge array that is a copy of A.
Definition: EdgeArray.h:145
ogdf::Graph::moveRegisterArray
void moveRegisterArray(ListIterator< ArrayBase * > it, ArrayBase *pArray) const
Move the registration it of an graph element array to pArray (used with move semantics for graph elem...
Definition: Graph_d.h:1261
ogdf::EdgeArray::findSuccKey
static key_type findSuccKey(key_type key)
Definition: EdgeArray.h:335
ogdf::ListIteratorBase
Encapsulates a pointer to a list element.
Definition: List.h:42
Graph_d.h
Pure declaration header, find template implementation in Graph.h.
ogdf::AdjElement::index
int index() const
Returns the index of this adjacency element.
Definition: Graph_d.h:111
ogdf::EdgeArray::end
const_iterator end() const
Returns a const iterator to one-past-last entry in the edge array.
Definition: EdgeArray.h:267
ogdf::EdgeArray::operator()
T & operator()(adjEntry adj)
Returns a reference to the element with index edge of adj.
Definition: EdgeArray.h:215
ogdf::EdgeArray::operator()
const T & operator()(edge e) const
Returns a reference to the element with index e.
Definition: EdgeArray.h:183
ogdf::EdgeArray::m_x
T m_x
The default value for array elements.
Definition: EdgeArray.h:113
ogdf::EdgeArrayBase::m_it
ListIterator< EdgeArrayBase * > m_it
Pointer to list element in the list of all registered edge arrays which references this array.
Definition: EdgeArray.h:50
ogdf::EdgeArray::end
iterator end()
Returns an iterator to one-past-last entry in the edge array.
Definition: EdgeArray.h:261
ogdf::EdgeArray::graphOf
const Graph * graphOf() const
Returns a pointer to the associated graph.
Definition: EdgeArray.h:164