Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
GraphList.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/Array.h>
35#include <ogdf/basic/basic.h>
36#include <ogdf/basic/internal/config_autogen.h>
38#include <ogdf/basic/memory.h>
39
40#include <iterator>
41#include <random>
42#include <utility>
43
44namespace ogdf {
45
46class ClusterGraph;
47class CombinatorialEmbedding;
48class ConstCombinatorialEmbedding;
49class Graph;
50
51namespace internal {
52
53
55
61 friend class ogdf::Graph;
62 friend class GraphListBase;
63
64protected:
65 GraphElement* m_next = nullptr;
66 GraphElement* m_prev = nullptr;
67
69};
70
73protected:
74 int m_size;
77
78public:
81 m_head = m_tail = nullptr;
82 m_size = 0;
83 }
84
87
89 int size() const { return m_size; }
90
92 bool empty() const { return m_size == 0; }
93
96 pX->m_next = nullptr;
97 pX->m_prev = m_tail;
98 if (m_head) {
99 m_tail = m_tail->m_next = pX;
100 } else {
101 m_tail = m_head = pX;
102 }
103 ++m_size;
104 }
105
108 pX->m_prev = pY;
109 GraphElement* pYnext = pX->m_next = pY->m_next;
110 pY->m_next = pX;
111 if (pYnext) {
112 pYnext->m_prev = pX;
113 } else {
114 m_tail = pX;
115 }
116 ++m_size;
117 }
118
121 pX->m_next = pY;
122 GraphElement* pYprev = pX->m_prev = pY->m_prev;
123 pY->m_prev = pX;
124 if (pYprev) {
125 pYprev->m_next = pX;
126 } else {
127 m_head = pX;
128 }
129 ++m_size;
130 }
131
133 void del(GraphElement* pX) {
134 GraphElement *pxPrev = pX->m_prev, *pxNext = pX->m_next;
135
136 if (pxPrev) {
137 pxPrev->m_next = pxNext;
138 } else {
139 m_head = pxNext;
140 }
141 if (pxNext) {
142 pxNext->m_prev = pxPrev;
143 } else {
144 m_tail = pxPrev;
145 }
146 m_size--;
147 }
148
150 template<class LIST>
151 void sort(const LIST& newOrder) {
152 using std::begin;
153 using std::end;
154 sort(begin(newOrder), end(newOrder));
155 }
156
158 template<class IT>
159 void sort(IT begin, IT end) {
160 if (begin == end) {
161 return;
162 }
163 m_head = *begin;
164 GraphElement* pPred = nullptr;
165 for (auto it = begin; it != end; ++it) {
166 GraphElement* p = *it;
167 if ((p->m_prev = pPred) != nullptr) {
168 pPred->m_next = p;
169 }
170 pPred = p;
171 }
172 (m_tail = pPred)->m_next = nullptr;
173 }
174
176 void reverse() {
177 GraphElement* pX = m_head;
178 m_head = m_tail;
179 m_tail = pX;
180 while (pX) {
181 GraphElement* pY = pX->m_next;
182 pX->m_next = pX->m_prev;
183 pX = pX->m_prev = pY;
184 }
185 }
186
189 if (pX->m_next == pY) {
190 pX->m_next = pY->m_next;
191 pY->m_prev = pX->m_prev;
192 pY->m_next = pX;
193 pX->m_prev = pY;
194
195 } else if (pY->m_next == pX) {
196 pY->m_next = pX->m_next;
197 pX->m_prev = pY->m_prev;
198 pX->m_next = pY;
199 pY->m_prev = pX;
200
201 } else {
202 std::swap(pX->m_next, pY->m_next);
203 std::swap(pX->m_prev, pY->m_prev);
204 }
205
206 if (pX->m_prev) {
207 pX->m_prev->m_next = pX;
208 } else {
209 m_head = pX;
210 }
211 if (pX->m_next) {
212 pX->m_next->m_prev = pX;
213 } else {
214 m_tail = pX;
215 }
216
217 if (pY->m_prev) {
218 pY->m_prev->m_next = pY;
219 } else {
220 m_head = pY;
221 }
222 if (pY->m_next) {
223 pY->m_next->m_prev = pY;
224 } else {
225 m_tail = pY;
226 }
227
228#ifdef OGDF_DEBUG
229 consistencyCheck();
230#endif
231 }
232
234 template<class RNG>
235 void permute(RNG& rng) {
236 Array<GraphElement*> A(m_size + 2);
237 A[0] = A[m_size + 1] = nullptr;
238
239 int i = 1;
240 GraphElement* pX;
241 for (pX = m_head; pX; pX = pX->m_next) {
242 A[i++] = pX;
243 }
244
245 A.permute(1, m_size, rng);
246
247 for (i = 1; i <= m_size; i++) {
248 pX = A[i];
249 pX->m_next = A[i + 1];
250 pX->m_prev = A[i - 1];
251 }
252
253 m_head = A[1];
254 m_tail = A[m_size];
255
256#ifdef OGDF_DEBUG
257 consistencyCheck();
258#endif
259 }
260
262 void permute() {
263 std::minstd_rand rng(randomSeed());
264 permute(rng);
265 }
266
267#ifdef OGDF_DEBUG
269 void consistencyCheck() const {
270 OGDF_ASSERT((m_head == nullptr) == (m_tail == nullptr));
271
272 if (m_head != nullptr) {
273 OGDF_ASSERT(m_head->m_prev == nullptr);
274 OGDF_ASSERT(m_tail->m_next == nullptr);
275
276 for (GraphElement* pX = m_head; pX; pX = pX->m_next) {
277 if (pX->m_prev) {
278 OGDF_ASSERT(pX->m_prev->m_next == pX);
279 } else {
280 OGDF_ASSERT(pX == m_head);
281 }
282
283 if (pX->m_next) {
284 OGDF_ASSERT(pX->m_next->m_prev == pX);
285 } else {
286 OGDF_ASSERT(pX == m_tail);
287 }
288 }
289 }
290 }
291#endif
292
294};
295
297
300template<class T>
301class GraphList : protected GraphListBase {
302public:
304 using value_type = T*;
309
312
315 if (m_head) {
316 OGDF_ALLOCATOR::deallocateList(sizeof(T), m_head, m_tail);
317 }
318 }
319
322
324 T* head() const { return static_cast<T*>(m_head); }
325
327 T* tail() const { return static_cast<T*>(m_tail); }
328
331
333 void insertAfter(T* pX, T* pY) { GraphListBase::insertAfter(pX, pY); }
334
336 void insertBefore(T* pX, T* pY) { GraphListBase::insertBefore(pX, pY); }
337
339 void move(T* pX, GraphList<T>& L, T* pY, Direction dir) {
341 if (dir == Direction::after) {
342 L.insertAfter(pX, pY);
343 } else {
344 L.insertBefore(pX, pY);
345 }
346 }
347
349 void move(T* pX, GraphList<T>& L) {
351 L.pushBack(pX);
352 }
353
355 void moveAfter(T* pX, T* pY) {
357 insertAfter(pX, pY);
358 }
359
361 void moveBefore(T* pX, T* pY) {
363 insertBefore(pX, pY);
364 }
365
367 void del(T* pX) {
369 delete pX;
370 }
371
373 void delPure(T* pX) { GraphListBase::del(pX); }
374
376 void clear() {
377 if (m_head) {
378 OGDF_ALLOCATOR::deallocateList(sizeof(T), m_head, m_tail);
379 m_head = m_tail = nullptr;
380 m_size = 0;
381 }
382 }
383
385 iterator begin() const { return GraphList<T>::head(); }
386
388 iterator end() const { return iterator(); }
389
392
395
399
401 void swap(T* pX, T* pY) { GraphListBase::swap(pX, pY); }
402
403#ifdef OGDF_DEBUG
405#endif
406};
407
409template<class GraphObject>
410class GraphObjectContainer : private GraphList<GraphObject> {
411 friend class ogdf::Graph;
412 friend class ogdf::ClusterGraph;
415
416public:
420
421 using GraphList<GraphObject>::begin;
422 using GraphList<GraphObject>::rbegin;
423 using GraphList<GraphObject>::end;
424 using GraphList<GraphObject>::rend;
425
426 using GraphList<GraphObject>::size;
427 using GraphList<GraphObject>::empty;
428 using GraphList<GraphObject>::head;
429 using GraphList<GraphObject>::tail;
430};
431
432}
433}
Declaration and implementation of Array class and Array algorithms.
Basic declarations, included by all source files.
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:219
Representation of clustered graphs.
Combinatorial embeddings of planar graphs with modification functionality.
Combinatorial embeddings of planar graphs.
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:866
The base class for objects used by (hyper)graphs.
Definition GraphList.h:60
GraphElement * m_next
The successor in the list.
Definition GraphList.h:65
GraphElement * m_prev
The predecessor in the list.
Definition GraphList.h:66
Base class for GraphElement lists.
Definition GraphList.h:72
void sort(IT begin, IT end)
Sorts the list according to the range defined by two iterators.
Definition GraphList.h:159
void pushBack(GraphElement *pX)
Adds element pX at the end of the list.
Definition GraphList.h:95
int m_size
The size of the list.
Definition GraphList.h:74
bool empty() const
Returns true iff the list is empty.
Definition GraphList.h:92
void insertAfter(GraphElement *pX, GraphElement *pY)
Inserts element pX after element pY.
Definition GraphList.h:107
GraphListBase()
Constructs an empty list.
Definition GraphList.h:80
void insertBefore(GraphElement *pX, GraphElement *pY)
Inserts element pX before element pY.
Definition GraphList.h:120
void sort(const LIST &newOrder)
Sorts the list according to newOrder.
Definition GraphList.h:151
void consistencyCheck() const
Asserts consistency of this list.
Definition GraphList.h:269
GraphElement * m_head
Pointer to the first element in the list.
Definition GraphList.h:75
int size() const
Returns the size of the list.
Definition GraphList.h:89
void reverse()
Reverses the order of the list elements.
Definition GraphList.h:176
void del(GraphElement *pX)
Removes element pX from the list.
Definition GraphList.h:133
void permute()
Permutes all list elements.
Definition GraphList.h:262
GraphElement * m_tail
Pointer to the last element in the list.
Definition GraphList.h:76
void permute(RNG &rng)
Permutes all list elements.
Definition GraphList.h:235
void swap(GraphElement *pX, GraphElement *pY)
Exchanges the positions of pX and pY in the list.
Definition GraphList.h:188
Lists of graph objects (like nodes, edges, etc.).
Definition GraphList.h:301
T * head() const
Returns the first element in the list.
Definition GraphList.h:324
void move(T *pX, GraphList< T > &L, T *pY, Direction dir)
Moves element pX to list L and inserts it before or after pY.
Definition GraphList.h:339
~GraphList()
Destruction: deletes all elements.
Definition GraphList.h:314
void delPure(T *pX)
Only removes element pX from the list; does not delete it.
Definition GraphList.h:373
T * tail() const
Returns the last element in the list.
Definition GraphList.h:327
reverse_iterator rend() const
Returns a reverse iterator to the one-before-first element in the container.
Definition GraphList.h:394
void del(T *pX)
Removes element pX from the list and deletes it.
Definition GraphList.h:367
bool empty() const
Returns true iff the list is empty.
Definition GraphList.h:92
void clear()
Removes all elements from the list and deletes them.
Definition GraphList.h:376
iterator begin() const
Returns an iterator to the first element in the container.
Definition GraphList.h:385
void insertBefore(T *pX, T *pY)
Inserts element pX before element pY.
Definition GraphList.h:336
void move(T *pX, GraphList< T > &L)
Moves element pX to list L and inserts it at the end.
Definition GraphList.h:349
reverse_iterator rbegin() const
Returns a reverse iterator to the last element in the container.
Definition GraphList.h:391
void pushBack(T *pX)
Adds element pX at the end of the list.
Definition GraphList.h:330
void insertAfter(T *pX, T *pY)
Inserts element pX after element pY.
Definition GraphList.h:333
void moveBefore(T *pX, T *pY)
Moves element pX from its current position to a position before pY.
Definition GraphList.h:361
GraphReverseIterator< T * > reverse_iterator
Provides a bidirectional reverse iterator to an object in the container.
Definition GraphList.h:308
GraphList()
Constructs an empty list.
Definition GraphList.h:311
T * value_type
The value type (a pointer to a specific graph object)
Definition GraphList.h:304
iterator end() const
Returns an iterator to the one-past-last element in the container.
Definition GraphList.h:388
int size() const
Returns the size of the list.
Definition GraphList.h:89
void moveAfter(T *pX, T *pY)
Moves element pX from its current position to a position after pY.
Definition GraphList.h:355
void swap(T *pX, T *pY)
Exchanges the positions of pX and pY in the list.
Definition GraphList.h:401
GraphIterator< T * > iterator
Provides a bidirectional iterator to an object in the container.
Definition GraphList.h:306
Public read-only interface for lists of graph objects.
Definition GraphList.h:410
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF dynamic library (shared object / DLL),...
Definition config.h:117
Decralation of graph iterators.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:52
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition memory.h:85
long unsigned int randomSeed()
Returns a random value suitable as initial seed for a random number engine.
Declaration of memory manager for allocating small pieces of memory.
The namespace for all OGDF objects.
HypergraphRegistry< HypernodeElement >::iterator begin(const HypergraphRegistry< HypernodeElement > &self)
Direction
Definition basic.h:150
HypergraphRegistry< HypernodeElement >::iterator end(const HypergraphRegistry< HypernodeElement > &self)