Tulip  5.0.0
Large graphs analysis and drawing
GraphIterator.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
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 
44 class TLP_SCOPE EdgeIterator :public Iterator<edge> {
45 };
46 
47 #if !defined(NDEBUG) && !defined(_OPENMP)
48 class TLP_SCOPE NodeIteratorObserver :public NodeIterator, public Observable {
49 private:
50  // Observable interface
51  void treatEvent(const Event&);
52 };
53 
54 class TLP_SCOPE EdgeIteratorObserver :public EdgeIterator, public Observable {
55 private:
56  // Observable interface
57  void treatEvent(const Event&);
58 };
59 #endif
60 //===========================================================
61 ///Factorization of code for iterators
62 class TLP_SCOPE FactorNodeIterator
63 #if defined(NDEBUG) || defined(_OPENMP)
64  :public NodeIterator
65 #else
66  :public NodeIteratorObserver
67 #endif
68 {
69 protected:
70  Graph *_parentGraph;
71 public:
72  FactorNodeIterator(const Graph *sG):
73  _parentGraph(sG->getSuperGraph()) {
74  }
75 };
76 
77 class TLP_SCOPE FactorEdgeIterator
78 #if defined(NDEBUG) || defined(_OPENMP)
79  :public EdgeIterator
80 #else
81  :public EdgeIteratorObserver
82 #endif
83 {
84 protected:
85  Graph *_parentGraph;
86 public:
87  FactorEdgeIterator(const Graph *sG):
88  _parentGraph(sG->getSuperGraph()) {
89  }
90 };
91 //============================================================
92 ///Node iterator for GraphView
93 template<typename VALUE_TYPE>
94 class SGraphNodeIterator:public FactorNodeIterator, public MemoryPool<SGraphNodeIterator<VALUE_TYPE> > {
95 private:
96  const Graph* sg;
97  Iterator<node> *it;
98  node curNode;
99  VALUE_TYPE value;
100  const MutableContainer<VALUE_TYPE>& _filter;
101 
102 protected:
103  void prepareNext() {
104  while(it->hasNext()) {
105  curNode = it->next();
106 
107  if (_filter.get(curNode) == value)
108  return;
109  }
110 
111  // set curNode as invalid
112  curNode = node();
113  }
114 
115 public:
116  SGraphNodeIterator(const Graph *sG,
117  const MutableContainer<VALUE_TYPE>& filter,
118  typename tlp::StoredType<VALUE_TYPE>::ReturnedConstValue val) :FactorNodeIterator(sG), sg(sG), value(val), _filter(filter) {
119  it=sg->getNodes();
120 #if !defined(NDEBUG) && !defined(_OPENMP)
121  sg->addListener(this);
122 #endif
123  // anticipate first iteration
124  prepareNext();
125  }
126  ~SGraphNodeIterator() {
127 #if !defined(NDEBUG) && !defined(_OPENMP)
128  sg->removeListener(this);
129 #endif
130  delete it;
131  }
132  node next() {
133  assert(curNode.isValid());
134  // we are already pointing to the next
135  node tmp = curNode;
136  // anticipate next iteration
137  prepareNext();
138  return tmp;
139  }
140 
141  bool hasNext() {
142  return (curNode.isValid());
143  }
144 };
145 
146 //============================================================
147 ///Out node iterator for GraphView
148 class TLP_SCOPE OutNodesIterator:public FactorNodeIterator, public MemoryPool<OutNodesIterator> {
149 private:
150  Iterator<edge> *it;
151 #if !defined(NDEBUG) && !defined(_OPENMP)
152  const GraphView *sg;
153 #endif
154 public:
155  OutNodesIterator(const GraphView *sG, node n);
156  ~OutNodesIterator();
157  node next();
158  bool hasNext();
159 };
160 //============================================================
161 ///In node iterator for GraphView
162 class InNodesIterator:public FactorNodeIterator, public MemoryPool<InNodesIterator> {
163 private:
164  Iterator<edge> *it;
165 #if !defined(NDEBUG) && !defined(_OPENMP)
166  const GraphView *sg;
167 #endif
168 public:
169  InNodesIterator(const GraphView *sG, node n);
170  ~InNodesIterator();
171  node next();
172  bool hasNext();
173 };
174 //============================================================
175 ///In Out node iterator for GraphView
176 class TLP_SCOPE InOutNodesIterator:public FactorNodeIterator, public MemoryPool<InOutNodesIterator> {
177 private:
178  Iterator<edge> *it;
179  node n;
180 #if !defined(NDEBUG) && !defined(_OPENMP)
181  const GraphView *sg;
182 #endif
183 public:
184  InOutNodesIterator(const GraphView *sG, node n);
185  ~InOutNodesIterator();
186  node next();
187  bool hasNext();
188 };
189 //=============================================================
190 ///Edge iterator for GraphView
191 template<typename VALUE_TYPE>
192 class SGraphEdgeIterator:public FactorEdgeIterator, public MemoryPool<SGraphEdgeIterator<VALUE_TYPE> > {
193 private:
194  const Graph* sg;
195  Iterator<edge> *it;
196  edge curEdge;
197  VALUE_TYPE value;
198  const MutableContainer<VALUE_TYPE>& _filter;
199 
200 protected:
201  void prepareNext() {
202  while(it->hasNext()) {
203  curEdge=it->next();
204 
205  if (_filter.get(curEdge.id) == value)
206  return;
207  }
208 
209  // set curEdge as invalid
210  curEdge = edge();
211  }
212 
213 public:
214  SGraphEdgeIterator(const Graph *sG,
215  const MutableContainer<VALUE_TYPE>& filter,
216  typename tlp::StoredType<VALUE_TYPE>::ReturnedConstValue val)
217  : FactorEdgeIterator(sG), sg(sG), value(val), _filter(filter) {
218  it=sg->getEdges();
219 #if !defined(NDEBUG) && !defined(_OPENMP)
220  sg->addListener(this);
221 #endif
222  // anticipate first iteration
223  prepareNext();
224  }
225 
226  ~SGraphEdgeIterator() {
227 #if !defined(NDEBUG) && !defined(_OPENMP)
228  sg->removeListener(this);
229 #endif
230  delete it;
231  }
232 
233  edge next() {
234  assert(curEdge.isValid());
235  // we are already pointing to the next
236  edge tmp=curEdge;
237  // anticipating the next iteration
238  prepareNext();
239  return tmp;
240  }
241 
242  bool hasNext() {
243  return (curEdge.isValid());
244  }
245 };
246 //============================================================
247 ///Out edge iterator for GraphView
248 class TLP_SCOPE OutEdgesIterator:public FactorEdgeIterator, public MemoryPool<OutEdgesIterator> {
249 private:
250  Iterator<edge> *it;
251  edge curEdge;
252  const GraphView* sg;
253 
254 public:
255  OutEdgesIterator(const GraphView *sG, node n);
256  ~OutEdgesIterator();
257  edge next();
258  bool hasNext();
259 protected:
260  void prepareNext();
261 };
262 //============================================================
263 ///In edge iterator for GraphView
264 class TLP_SCOPE InEdgesIterator:public FactorEdgeIterator, public MemoryPool<InEdgesIterator> {
265 private:
266  Iterator<edge> *it;
267  edge curEdge;
268  const GraphView* sg;
269 
270 public:
271  InEdgesIterator(const GraphView *sG, node n);
272  ~InEdgesIterator();
273  edge next();
274  bool hasNext();
275 protected:
276  void prepareNext();
277 };
278 //============================================================
279 ///In Out edge iterator for GraphView
280 class TLP_SCOPE InOutEdgesIterator:public FactorEdgeIterator, public MemoryPool<InOutEdgesIterator> {
281 private:
282  Iterator<edge> *it;
283  edge curEdge;
284  const GraphView* sg;
285 
286 public:
287  InOutEdgesIterator(const GraphView *sG, node n);
288  ~InOutEdgesIterator();
289  edge next();
290  bool hasNext();
291 protected:
292  void prepareNext();
293 };
294 
295 //============================================================
296 //Iterator for the Graph
297 //============================================================
298 class TLP_SCOPE GraphNodeIterator
299 #if defined(NDEBUG) || defined(_OPENMP)
300  :public NodeIterator, public MemoryPool<GraphNodeIterator>
301 #else
302  :public NodeIteratorObserver
303 #endif
304 {
305 private:
306 #if !defined(NDEBUG) && !defined(_OPENMP)
307  const Graph *graph;
308 #endif
309  Iterator<node> *itId;
310 public:
311  GraphNodeIterator(const Graph *g, Iterator<node>* it);
312  ~GraphNodeIterator();
313  node next();
314  bool hasNext();
315 };
316 //=============================================================
317 ///Edge iterator for data sg
318 class TLP_SCOPE GraphEdgeIterator
319 #if defined(NDEBUG) || defined(_OPENMP)
320  :public EdgeIterator, public MemoryPool<GraphEdgeIterator>
321 #else
322  :public EdgeIteratorObserver
323 #endif
324 {
325 private:
326 #if !defined(NDEBUG) && !defined(_OPENMP)
327  const Graph *graph;
328 #endif
329  Iterator<edge> *itId;
330 public:
331  GraphEdgeIterator(const Graph *g, Iterator<edge>* it);
332  ~GraphEdgeIterator();
333  edge next();
334  bool hasNext();
335 };
336 //============================================================
337 
338 }
339 #endif
340 
341 ///@endcond
virtual itType next()=0
Moves the Iterator on the next element.
Interface for Tulip iterators. Allows basic iteration operations only.
Definition: Iterator.h:39
virtual bool hasNext()=0
Tells if the sequence is at its end.