Tulip  5.2.0
Large graphs analysis and drawing
GraphIterator.h
1 /*
2  *
3  * This file is part of Tulip (http://tulip.labri.fr)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef TULIP_GGRAPHITERATOR_H
22 #define TULIP_GGRAPHITERATOR_H
23 #include <tulip/Iterator.h>
24 #include <tulip/memorypool.h>
25 #include <set>
26 
27 #include <tulip/MutableContainer.h>
28 #include <tulip/Observable.h>
29 #include <tulip/tulipconf.h>
30 #include <tulip/StoredType.h>
31 #include <iostream>
32 
33 namespace tlp {
34 
35 class Graph;
36 class GraphImpl;
37 class GraphView;
38 
39 struct node;
40 struct edge;
41 class TLP_SCOPE NodeIterator : public Iterator<node> {};
42 
43 class TLP_SCOPE EdgeIterator : public Iterator<edge> {};
44 
45 #if !defined(NDEBUG) && !defined(_OPENMP)
46 class TLP_SCOPE NodeIteratorObserver : public NodeIterator, public Observable {
47 private:
48  // Observable interface
49  void treatEvent(const Event &);
50 };
51 
52 class TLP_SCOPE EdgeIteratorObserver : public EdgeIterator, public Observable {
53 private:
54  // Observable interface
55  void treatEvent(const Event &);
56 };
57 #endif
58 //===========================================================
59 /// Factorization of code for iterators
60 class TLP_SCOPE FactorNodeIterator
61 #if defined(NDEBUG) || defined(_OPENMP)
62  : public NodeIterator
63 #else
64  : public NodeIteratorObserver
65 #endif
66 {
67 protected:
68  Graph *_parentGraph;
69 
70 public:
71  FactorNodeIterator(const Graph *sG) : _parentGraph(sG->getSuperGraph()) {}
72 };
73 
74 class TLP_SCOPE FactorEdgeIterator
75 #if defined(NDEBUG) || defined(_OPENMP)
76  : public EdgeIterator
77 #else
78  : public EdgeIteratorObserver
79 #endif
80 {
81 protected:
82  Graph *_parentGraph;
83 
84 public:
85  FactorEdgeIterator(const Graph *sG) : _parentGraph(sG->getSuperGraph()) {}
86 };
87 //============================================================
88 /// Node iterator for GraphView
89 template <typename VALUE_TYPE>
90 class SGraphNodeIterator : public FactorNodeIterator,
91  public MemoryPool<SGraphNodeIterator<VALUE_TYPE>> {
92 private:
93  const Graph *sg;
94  Iterator<node> *it;
95  node curNode;
96  VALUE_TYPE value;
97  const MutableContainer<VALUE_TYPE> &_filter;
98 
99 protected:
100  void prepareNext() {
101  while (it->hasNext()) {
102  curNode = it->next();
103 
104  if (_filter.get(curNode) == value)
105  return;
106  }
107 
108  // set curNode as invalid
109  curNode = node();
110  }
111 
112 public:
113  SGraphNodeIterator(const Graph *sG, const MutableContainer<VALUE_TYPE> &filter,
114  typename tlp::StoredType<VALUE_TYPE>::ReturnedConstValue val)
115  : FactorNodeIterator(sG), sg(sG), value(val), _filter(filter) {
116  it = sg->getNodes();
117 #if !defined(NDEBUG) && !defined(_OPENMP)
118  sg->addListener(this);
119 #endif
120  // anticipate first iteration
121  prepareNext();
122  }
123  ~SGraphNodeIterator() override {
124 #if !defined(NDEBUG) && !defined(_OPENMP)
125  sg->removeListener(this);
126 #endif
127  delete it;
128  }
129  node next() override {
130  assert(curNode.isValid());
131  // we are already pointing to the next
132  node tmp = curNode;
133  // anticipate next iteration
134  prepareNext();
135  return tmp;
136  }
137 
138  bool hasNext() override {
139  return (curNode.isValid());
140  }
141 };
142 
143 //============================================================
144 /// Out node iterator for GraphView
145 class TLP_SCOPE OutNodesIterator : public FactorNodeIterator, public MemoryPool<OutNodesIterator> {
146 private:
147  Iterator<edge> *it;
148 #if !defined(NDEBUG) && !defined(_OPENMP)
149  const GraphView *sg;
150 #endif
151 public:
152  OutNodesIterator(const GraphView *sG, node n);
153  ~OutNodesIterator() override;
154  node next() override;
155  bool hasNext() override;
156 };
157 //============================================================
158 /// In node iterator for GraphView
159 class InNodesIterator : public FactorNodeIterator, public MemoryPool<InNodesIterator> {
160 private:
161  Iterator<edge> *it;
162 #if !defined(NDEBUG) && !defined(_OPENMP)
163  const GraphView *sg;
164 #endif
165 public:
166  InNodesIterator(const GraphView *sG, node n);
167  ~InNodesIterator() override;
168  node next() override;
169  bool hasNext() override;
170 };
171 //============================================================
172 /// In Out node iterator for GraphView
173 class TLP_SCOPE InOutNodesIterator : public FactorNodeIterator,
174  public MemoryPool<InOutNodesIterator> {
175 private:
176  Iterator<edge> *it;
177  node n;
178 #if !defined(NDEBUG) && !defined(_OPENMP)
179  const GraphView *sg;
180 #endif
181 public:
182  InOutNodesIterator(const GraphView *sG, node n);
183  ~InOutNodesIterator() override;
184  node next() override;
185  bool hasNext() override;
186 };
187 //=============================================================
188 /// Edge iterator for GraphView
189 template <typename VALUE_TYPE>
190 class SGraphEdgeIterator : public FactorEdgeIterator,
191  public MemoryPool<SGraphEdgeIterator<VALUE_TYPE>> {
192 private:
193  const Graph *sg;
194  Iterator<edge> *it;
195  edge curEdge;
196  VALUE_TYPE value;
197  const MutableContainer<VALUE_TYPE> &_filter;
198 
199 protected:
200  void prepareNext() {
201  while (it->hasNext()) {
202  curEdge = it->next();
203 
204  if (_filter.get(curEdge.id) == value)
205  return;
206  }
207 
208  // set curEdge as invalid
209  curEdge = edge();
210  }
211 
212 public:
213  SGraphEdgeIterator(const Graph *sG, const MutableContainer<VALUE_TYPE> &filter,
214  typename tlp::StoredType<VALUE_TYPE>::ReturnedConstValue val)
215  : FactorEdgeIterator(sG), sg(sG), value(val), _filter(filter) {
216  it = sg->getEdges();
217 #if !defined(NDEBUG) && !defined(_OPENMP)
218  sg->addListener(this);
219 #endif
220  // anticipate first iteration
221  prepareNext();
222  }
223 
224  ~SGraphEdgeIterator() override {
225 #if !defined(NDEBUG) && !defined(_OPENMP)
226  sg->removeListener(this);
227 #endif
228  delete it;
229  }
230 
231  edge next() override {
232  assert(curEdge.isValid());
233  // we are already pointing to the next
234  edge tmp = curEdge;
235  // anticipating the next iteration
236  prepareNext();
237  return tmp;
238  }
239 
240  bool hasNext() override {
241  return (curEdge.isValid());
242  }
243 };
244 //============================================================
245 /// Out edge iterator for GraphView
246 class TLP_SCOPE OutEdgesIterator : public FactorEdgeIterator, public MemoryPool<OutEdgesIterator> {
247 private:
248  Iterator<edge> *it;
249  edge curEdge;
250  const GraphView *sg;
251 
252 public:
253  OutEdgesIterator(const GraphView *sG, node n);
254  ~OutEdgesIterator() override;
255  edge next() override;
256  bool hasNext() override;
257 
258 protected:
259  void prepareNext();
260 };
261 //============================================================
262 /// In edge iterator for GraphView
263 class TLP_SCOPE InEdgesIterator : public FactorEdgeIterator, public MemoryPool<InEdgesIterator> {
264 private:
265  Iterator<edge> *it;
266  edge curEdge;
267  const GraphView *sg;
268 
269 public:
270  InEdgesIterator(const GraphView *sG, node n);
271  ~InEdgesIterator() override;
272  edge next() override;
273  bool hasNext() override;
274 
275 protected:
276  void prepareNext();
277 };
278 //============================================================
279 /// In Out edge iterator for GraphView
280 class TLP_SCOPE InOutEdgesIterator : public FactorEdgeIterator,
281  public MemoryPool<InOutEdgesIterator> {
282 private:
283  Iterator<edge> *it;
284  edge curEdge;
285  const GraphView *sg;
286 
287 public:
288  InOutEdgesIterator(const GraphView *sG, node n);
289  ~InOutEdgesIterator() override;
290  edge next() override;
291  bool hasNext() override;
292 
293 protected:
294  void prepareNext();
295 };
296 
297 //============================================================
298 // Iterator for the Graph
299 //============================================================
300 class TLP_SCOPE GraphNodeIterator
301 #if defined(NDEBUG) || defined(_OPENMP)
302  : public NodeIterator,
303  public MemoryPool<GraphNodeIterator>
304 #else
305  : public NodeIteratorObserver
306 #endif
307 {
308 private:
309 #if !defined(NDEBUG) && !defined(_OPENMP)
310  const Graph *graph;
311 #endif
312  Iterator<node> *itId;
313 
314 public:
315  GraphNodeIterator(const Graph *g, Iterator<node> *it);
316  ~GraphNodeIterator() override;
317  node next() override;
318  bool hasNext() override;
319 };
320 //=============================================================
321 /// Edge iterator for data sg
322 class TLP_SCOPE GraphEdgeIterator
323 #if defined(NDEBUG) || defined(_OPENMP)
324  : public EdgeIterator,
325  public MemoryPool<GraphEdgeIterator>
326 #else
327  : public EdgeIteratorObserver
328 #endif
329 {
330 private:
331 #if !defined(NDEBUG) && !defined(_OPENMP)
332  const Graph *graph;
333 #endif
334  Iterator<edge> *itId;
335 
336 public:
337  GraphEdgeIterator(const Graph *g, Iterator<edge> *it);
338  ~GraphEdgeIterator() override;
339  edge next() override;
340  bool hasNext() override;
341 };
342 //============================================================
343 }
344 #endif
345 
346 ///@endcond