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/List.h>
37
38namespace ogdf {
39
40class Graph;
41class ClusterGraph;
42class ConstCombinatorialEmbedding;
43class CombinatorialEmbedding;
44
45namespace internal {
46
47class OGDF_EXPORT GraphListBase;
48
50
56 friend class ogdf::Graph;
57 friend class GraphListBase;
58
59protected:
60 GraphElement* m_next = nullptr;
61 GraphElement* m_prev = nullptr;
62
64};
65
68protected:
69 int m_size;
72
73public:
76 m_head = m_tail = nullptr;
77 m_size = 0;
78 }
79
82
84 int size() const { return m_size; }
85
88 pX->m_next = nullptr;
89 pX->m_prev = m_tail;
90 if (m_head) {
91 m_tail = m_tail->m_next = pX;
92 } else {
93 m_tail = m_head = pX;
94 }
95 ++m_size;
96 }
97
100 pX->m_prev = pY;
102 pY->m_next = pX;
103 if (pYnext) {
104 pYnext->m_prev = pX;
105 } else {
106 m_tail = pX;
107 }
108 ++m_size;
109 }
110
113 pX->m_next = pY;
115 pY->m_prev = pX;
116 if (pYprev) {
117 pYprev->m_next = pX;
118 } else {
119 m_head = pX;
120 }
121 ++m_size;
122 }
123
127
128 if (pxPrev) {
130 } else {
131 m_head = pxNext;
132 }
133 if (pxNext) {
135 } else {
136 m_tail = pxPrev;
137 }
138 m_size--;
139 }
140
142 template<class LIST>
143 void sort(const LIST& newOrder) {
144 GraphElement* pPred = nullptr;
145 typename LIST::const_iterator it = newOrder.begin();
146 if (!it.valid()) {
147 return;
148 }
149
150 m_head = *it;
151 for (; it.valid(); ++it) {
152 GraphElement* p = *it;
153 if ((p->m_prev = pPred) != nullptr) {
154 pPred->m_next = p;
155 }
156 pPred = p;
157 }
158
159 (m_tail = pPred)->m_next = nullptr;
160 }
161
163 void reverse() {
164 GraphElement* pX = m_head;
165 m_head = m_tail;
166 m_tail = pX;
167 while (pX) {
169 pX->m_next = pX->m_prev;
170 pX = pX->m_prev = pY;
171 }
172 }
173
176 if (pX->m_next == pY) {
177 pX->m_next = pY->m_next;
178 pY->m_prev = pX->m_prev;
179 pY->m_next = pX;
180 pX->m_prev = pY;
181
182 } else if (pY->m_next == pX) {
183 pY->m_next = pX->m_next;
184 pX->m_prev = pY->m_prev;
185 pX->m_next = pY;
186 pY->m_prev = pX;
187
188 } else {
189 std::swap(pX->m_next, pY->m_next);
190 std::swap(pX->m_prev, pY->m_prev);
191 }
192
193 if (pX->m_prev) {
194 pX->m_prev->m_next = pX;
195 } else {
196 m_head = pX;
197 }
198 if (pX->m_next) {
199 pX->m_next->m_prev = pX;
200 } else {
201 m_tail = pX;
202 }
203
204 if (pY->m_prev) {
205 pY->m_prev->m_next = pY;
206 } else {
207 m_head = pY;
208 }
209 if (pY->m_next) {
210 pY->m_next->m_prev = pY;
211 } else {
212 m_tail = pY;
213 }
214
215#ifdef OGDF_DEBUG
217#endif
218 }
219
221 template<class RNG>
222 void permute(RNG& rng) {
223 Array<GraphElement*> A(m_size + 2);
224 A[0] = A[m_size + 1] = nullptr;
225
226 int i = 1;
228 for (pX = m_head; pX; pX = pX->m_next) {
229 A[i++] = pX;
230 }
231
232 A.permute(1, m_size, rng);
233
234 for (i = 1; i <= m_size; i++) {
235 pX = A[i];
236 pX->m_next = A[i + 1];
237 pX->m_prev = A[i - 1];
238 }
239
240 m_head = A[1];
241 m_tail = A[m_size];
242
243#ifdef OGDF_DEBUG
245#endif
246 }
247
249 void permute() {
250 std::minstd_rand rng(randomSeed());
251 permute(rng);
252 }
253
254#ifdef OGDF_DEBUG
256 void consistencyCheck() const {
257 OGDF_ASSERT((m_head == nullptr) == (m_tail == nullptr));
258
259 if (m_head != nullptr) {
260 OGDF_ASSERT(m_head->m_prev == nullptr);
261 OGDF_ASSERT(m_tail->m_next == nullptr);
262
263 for (GraphElement* pX = m_head; pX; pX = pX->m_next) {
264 if (pX->m_prev) {
265 OGDF_ASSERT(pX->m_prev->m_next == pX);
266 } else {
267 OGDF_ASSERT(pX == m_head);
268 }
269
270 if (pX->m_next) {
271 OGDF_ASSERT(pX->m_next->m_prev == pX);
272 } else {
273 OGDF_ASSERT(pX == m_tail);
274 }
275 }
276 }
277 }
278#endif
279
281};
282
284
287template<class T>
288class GraphList : protected GraphListBase {
289public:
292
295 if (m_head) {
296 OGDF_ALLOCATOR::deallocateList(sizeof(T), m_head, m_tail);
297 }
298 }
299
301 int size() const { return m_size; }
302
304 T* head() const { return static_cast<T*>(m_head); }
305
307 T* tail() const { return static_cast<T*>(m_tail); }
308
310 bool empty() const { return m_size == 0; }
311
314
317
320
322 void move(T* pX, GraphList<T>& L, T* pY, Direction dir) {
324 if (dir == Direction::after) {
325 L.insertAfter(pX, pY);
326 } else {
327 L.insertBefore(pX, pY);
328 }
329 }
330
332 void move(T* pX, GraphList<T>& L) {
334 L.pushBack(pX);
335 }
336
338 void moveAfter(T* pX, T* pY) {
340 insertAfter(pX, pY);
341 }
342
344 void moveBefore(T* pX, T* pY) {
347 }
348
350 void del(T* pX) {
352 delete pX;
353 }
354
357
359 void clear() {
360 if (m_head) {
361 OGDF_ALLOCATOR::deallocateList(sizeof(T), m_head, m_tail);
362 m_head = m_tail = nullptr;
363 m_size = 0;
364 }
365 }
366
368 template<class T_LIST>
369 void sort(const T_LIST& newOrder) {
370 GraphListBase::sort(newOrder);
371 }
372
375
377 void swap(T* pX, T* pY) { GraphListBase::swap(pX, pY); }
378
380#ifdef OGDF_DEBUG
381 using GraphListBase::consistencyCheck;
382#endif
383
385};
386
387template<class GraphObject>
424
425}
426}
Declaration and implementation of Array class and Array algorithms.
Declaration of doubly linked lists and iterators.
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
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:521
The base class for objects used by (hyper)graphs.
Definition GraphList.h:55
GraphElement * m_next
The successor in the list.
Definition GraphList.h:60
GraphElement * m_prev
The predecessor in the list.
Definition GraphList.h:61
Base class for GraphElement lists.
Definition GraphList.h:67
void pushBack(GraphElement *pX)
Adds element pX at the end of the list.
Definition GraphList.h:87
int m_size
The size of the list.
Definition GraphList.h:69
void insertAfter(GraphElement *pX, GraphElement *pY)
Inserts element pX after element pY.
Definition GraphList.h:99
GraphListBase()
Constructs an empty list.
Definition GraphList.h:75
void insertBefore(GraphElement *pX, GraphElement *pY)
Inserts element pX before element pY.
Definition GraphList.h:112
void sort(const LIST &newOrder)
Sorts the list according to newOrder.
Definition GraphList.h:143
GraphElement * m_head
Pointer to the first element in the list.
Definition GraphList.h:70
int size() const
Returns the size of the list.
Definition GraphList.h:84
void reverse()
Reverses the order of the list elements.
Definition GraphList.h:163
void del(GraphElement *pX)
Removes element pX from the list.
Definition GraphList.h:125
void permute()
Permutes all list elements.
Definition GraphList.h:249
GraphElement * m_tail
Pointer to the last element in the list.
Definition GraphList.h:71
void permute(RNG &rng)
Permutes all list elements.
Definition GraphList.h:222
void swap(GraphElement *pX, GraphElement *pY)
Exchanges the positions of pX and pY in the list.
Definition GraphList.h:175
Lists of graph objects (like nodes, edges, etc.).
Definition GraphList.h:288
T * head() const
Returns the first element in the list.
Definition GraphList.h:304
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:322
void sort(const T_LIST &newOrder)
Sorts all elements according to newOrder.
Definition GraphList.h:369
bool empty() const
Returns true iff the list is empty.
Definition GraphList.h:310
~GraphList()
Destruction: deletes all elements.
Definition GraphList.h:294
void delPure(T *pX)
Only removes element pX from the list; does not delete it.
Definition GraphList.h:356
T * tail() const
Returns the last element in the list.
Definition GraphList.h:307
void del(T *pX)
Removes element pX from the list and deletes it.
Definition GraphList.h:350
void clear()
Removes all elements from the list and deletes them.
Definition GraphList.h:359
void insertBefore(T *pX, T *pY)
Inserts element pX before element pY.
Definition GraphList.h:319
void move(T *pX, GraphList< T > &L)
Moves element pX to list L and inserts it at the end.
Definition GraphList.h:332
void pushBack(T *pX)
Adds element pX at the end of the list.
Definition GraphList.h:313
int size() const
Returns the size of the list.
Definition GraphList.h:301
void insertAfter(T *pX, T *pY)
Inserts element pX after element pY.
Definition GraphList.h:316
void moveBefore(T *pX, T *pY)
Moves element pX from its current position to a position before pY.
Definition GraphList.h:344
GraphList()
Constructs an empty list.
Definition GraphList.h:291
void moveAfter(T *pX, T *pY)
Moves element pX from its current position to a position after pY.
Definition GraphList.h:338
void swap(T *pX, T *pY)
Exchanges the positions of pX and pY in the list.
Definition GraphList.h:377
void permute()
Permutes all list elements.
Definition GraphList.h:249
void reverse()
Reverses the order of the list elements.
Definition GraphList.h:374
GraphIterator< GraphObject * > iterator
Provides a bidirectional iterator to an object in the container.
Definition GraphList.h:402
GraphReverseIterator< GraphObject * > reverse_iterator
Provides a bidirectional reverse iterator to an object in the container.
Definition GraphList.h:404
reverse_iterator rbegin() const
Returns a reverse iterator to the last element in the container.
Definition GraphList.h:413
GraphObject * value_type
The value type (a pointer to a specific graph object)
Definition GraphList.h:400
iterator end() const
Returns an iterator to the one-past-last element in the container.
Definition GraphList.h:410
iterator begin() const
Returns an iterator to the first element in the container.
Definition GraphList.h:407
reverse_iterator rend() const
Returns a reverse iterator to the one-before-first element in the container.
Definition GraphList.h:416
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
Decralation of graph iterators.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition memory.h:84
long unsigned int randomSeed()
Returns a random value suitable as initial seed for a random number engine.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Direction
Definition basic.h:134