Tulip  4.1.0
Better Visualization Through Research
 All Classes Files Functions Variables Enumerations Enumerator Properties Groups Pages
GraphStorage.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 1 and Inria Bordeaux - Sud Ouest
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 
22 #ifndef GRAPHSTORAGE_H
23 #define GRAPHSTORAGE_H
24 #include <cassert>
25 #include <vector>
26 
27 #include <tulip/Node.h>
28 #include <tulip/Edge.h>
29 #include <tulip/IdManager.h>
30 #include <tulip/SimpleVector.h>
31 #include <tulip/MutableContainer.h>
32 
33 namespace tlp {
34 
35 //===========================================
36 /**
37  * @class GraphStorageIdsMemento
38  * @brief that class provides a simple interface
39  * to save the state of the ids manage by the GraphStorage class
40  */
41 class GraphStorageIdsMemento {
42 public:
43  virtual ~GraphStorageIdsMemento() {}
44 };
45 //===========================================
46 /**
47  * @class GraphStorage
48  * @brief That class provide a simple implementation
49  * for the storage of graph elts (nodes edges)
50  */
51 class GraphStorage {
52 public:
53  //=======================================================
54  void clear();
55  //=======================================================
56  GraphStorage();
57  //=======================================================
58  ~GraphStorage();
59  //=======================================================
60  /**
61  * @brief Return true if n belongs to the graph
62  */
63  bool isElement(const node n) const;
64  //=======================================================
65  /**
66  * @brief Return true if e belongs to the graph
67  */
68  bool isElement(const edge e) const;
69  //=======================================================
70  /**
71  * @brief Enables to reserve memory for nbNodes
72  * Reserving memory before to addNode enable to reduce the number of vector resizing and then
73  * to speed up significantly construction of graphs.
74  */
75  void reserveNodes(size_t nb);
76  //=======================================================
77  /**
78  * @brief Enables to reserve memory for nbEdges
79  * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
80  * to speed up significantly construction of graphs.
81  */
82  void reserveEdges(size_t nb);
83  //=======================================================
84  /**
85  * @brief Enables to reserve memory for adjacency nodes
86  * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
87  * to speed up significantly construction of graphs.
88  */
89  void reserveAdj(node n, size_t nb);
90  //=======================================================
91  /**
92  * @brief Enables to reserve memory for adjacency nodes
93  * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
94  * to speed up significantly construction of graphs.
95  */
96  void reserveAdj(size_t nb);
97  //=======================================================
98  /**
99  * @brief restore adjacency edges of a given node
100  */
101  void restoreAdj(node n, const std::vector<edge>& edges);
102  //=======================================================
103  /**
104  * @brief Return the first node of graph
105  */
106  node getOneNode() const;
107  //=======================================================
108  /**
109  * @brief Return a Tulip Iterator on nodes of the graph
110  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
111  * @complexity: o(1)
112  */
113  Iterator<node>* getNodes() const;
114  //=======================================================
115  /**
116  * @brief Return the current state of the ids management
117  * must be deleted by the caller
118  * this can be used for push/pop
119  */
120  const GraphStorageIdsMemento* getIdsMemento();
121  //=======================================================
122  /**
123  * @brief restore a state of the ids management
124  */
125  void restoreIdsMemento(const GraphStorageIdsMemento*);
126  //=======================================================
127  /**
128  * @brief Return a Tulip Iterator on edges of the graph
129  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
130  */
131  Iterator<edge>* getEdges() const;
132  //=======================================================
133  /**
134  * @brief Return a Tulip Iterator on adjacent edges of the node n
135  * @warning: be careful that loops appear twice
136  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
137  */
138  Iterator<edge>* getInOutEdges(node n) const;
139  //=======================================================
140  /**
141  * @brief get adjacency edges of a given node
142  */
143  void getInOutEdges(node n, std::vector<edge>& edges,
144  bool loopsOnlyOnce = false) const;
145  //=======================================================
146  /**
147  * @brief Return a Tulip Iterator on out edges of the node n
148  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
149  */
150  Iterator<edge>* getOutEdges(node n) const;
151  //=======================================================
152  /**
153  * @brief Return a Tulip Iterator on in edges of the node n
154  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
155  */
156  Iterator<edge>* getInEdges(node n) const;
157  //=======================================================
158  /**
159  * @brief Return a Tulip Iterator on adjacent nodes of the node n
160  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
161  */
162  Iterator<node>* getInOutNodes(node n) const;
163  //=======================================================
164  /**
165  * @brief Return a Tulip Iterator on in nodes of the node n
166  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
167  */
168  Iterator<node>* getInNodes(node n) const;
169  //=======================================================
170  /**
171  * @brief Return a Tulip Iterator on out nodes of the node n
172  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
173  */
174  Iterator<node>* getOutNodes(node n) const;
175  //=======================================================
176  /**
177  * @brief Return the degree of a node
178  */
179  unsigned int deg(node n) const;
180  //=======================================================
181  /**
182  * @brief Return the out degree of a node
183  */
184  unsigned int outdeg(node n) const;
185  //=======================================================
186  /**
187  * @brief Return the in degree of a node
188  */
189  unsigned int indeg(node n) const;
190  //=======================================================
191  /**
192  * @brief Return the number of edges in the graph
193  */
194  unsigned int numberOfEdges() const;
195  //=======================================================
196  /**
197  * @brief Return the number of nodes in the graph
198  */
199  unsigned int numberOfNodes() const;
200  //=======================================================
201  /**
202  * @brief Return the extremities of an edge (src, target)
203  */
204  const std::pair<node, node>& ends(const edge e) const;
205  //=======================================================
206  /**
207  * @brief return the first extremity (considered as source if the graph is directed) of an edge
208  */
209  node source(edge e) const;
210  //=======================================================
211  /**
212  * @brief return the second extremity (considered as target if the graph is directed) of an edge
213  */
214  node target(edge e) const;
215  //=======================================================
216  /**
217  * @brief return the opposite node of n through edge e
218  */
219  node opposite(edge e, node n) const;
220  //=======================================================
221  /**
222  * @brief Reconnect the edge e to have the new given ends
223  * @warning That operation modify the array of neighboors of extrmities of edges, thus
224  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
225  */
226  void setEnds(const edge e, const node newSrc, const node newTgt);
227  //=======================================================
228  /**
229  * @brief change the source of an edge
230  * @warning That operation modify the array of neighboors of extrmities of edges, thus
231  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
232  * \see setEnds
233  */
234  void setSource(const edge e, const node n);
235  //=======================================================
236  /**
237  * @brief change the target of an edge
238  * @warning That operation modify the array of neighboors of extrmities of edges, thus
239  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
240  * \see setEnds
241  */
242  void setTarget(const edge e, const node n);
243  //=======================================================
244  /**
245  * @brief Reverse an edge e, source become target and target become soure
246  */
247  void reverse(const edge e);
248  //=======================================================
249  /**
250  * \brief Set the ordering of edges around n according to their order in v.
251  */
252  void setEdgeOrder(const node n, const std::vector<edge> &v );
253  //=======================================================
254  /**
255  * \brief swap to edge in the ordered adjacency vector
256  * \warning the two edges must be element of star(v)
257  */
258  void swapEdgeOrder(const node n, const edge e1, const edge e2);
259  //=======================================================
260  /**
261  * @brief Add the given node in the structure and return it
262  * @warning: That operation modify the array of nodes
263  * and thus devalidate all iterators on it.
264  * @complexity: o(1)
265  */
266  node addNode(node n);
267  //=======================================================
268  /**
269  * @brief Add a new node in the structure and return it
270  * @warning: That operation modify the array of nodes
271  * and thus devalidate all iterators on it.
272  * @complexity: o(1)
273  */
274  node addNode();
275  //=======================================================
276  /**
277  * @brief Add nb new nodes in the structure and returns them
278  * in the addedNodes vector
279  * @warning: That operation modify the array of nodes
280  * and thus devalidate all iterators on it. The addedNodes vector
281  * is cleared before adding nodes
282  * @complexity: o(1)
283  */
284  void addNodes(unsigned int nb, std::vector<node>& addedNodes);
285  //=======================================================
286  /**
287  * @brief Add the given nodes in the structure
288  * @warning: That operation modify the array of nodes
289  * and thus devalidate all iterators on it.
290  * @complexity: o(1)
291  */
292  void restoreNodes(const std::vector<node>& addedNodes);
293  //=======================================================
294  /**
295  * @brief remove a node from the nodes structure only
296  * @warning That operation modify the array of nodes
297  * and thus devalidate all iterators on it.
298  * @complexity: o(1)
299  */
300  void removeFromNodes(const node n);
301  //=======================================================
302  /**
303  * @brief Delete a node and all its adjacent edges in the graph
304  * @warning That operation modify the array of nodes and the array of edges
305  * and thus devalidate all iterators on it.
306  * @warning That operation modify the array of neighboors of extrmities of edges, thus
307  * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edges.
308  * @warning Orders of edges in the extremities of the deleted edges are affected
309  * @complexity: o(1)
310  */
311  void delNode(node n);
312  //=======================================================
313  /**
314  * @brief Add the given edge between src and tgt and return it
315  * the last argument indicates if the edge has to be added
316  * in the adjacency edges of its two ends
317  * @warning That operation modify the array of edges and
318  * the adjacency edges of its ends thus any iterators existing for
319  * these structures will be devalidated.
320  */
321  edge addEdge(const node src, const node tgt,
322  const edge e, bool updateEndsEdges);
323  //=======================================================
324  /**
325  * @brief Add a new edge between src and tgt and return it
326  * @warning That operation modify the array of edges and
327  * the adjacency edges of its ends thus any iterators existing for
328  * these structures will be devalidated.
329  */
330  edge addEdge(node src, node tgt);
331  //=======================================================
332  /**
333  * @brief Add edges in the structure and returns them
334  * in the addedEdges vector
335  * @warning: That operation modify the array of edges and
336  * the adjacency edges of its ends thus any iterators existing for
337  * these structures will be devalidated.
338  */
339  void addEdges(const std::vector<std::pair<node, node> >& edges,
340  std::vector<edge>& addedEdges);
341  //=======================================================
342  /**
343  * @brief restore edges in the structure and returns them
344  * in the addedEdges vector
345  * @warning: That operation modify the array of edges
346  * thus any iterators existing for
347  * these structures will be devalidated.
348  */
349  void restoreEdges(const std::vector<edge>& edgesToRestore,
350  const std::vector<std::pair<node, node> >& ends);
351 //=======================================================
352  /**
353  * @brief Delete an edge in the graph
354  * @warning: That operation modify the array of edges
355  * and thus devalidate all iterators on it.
356  * @warning That operation modify the array of neighboors of extremities of the edge e, thus
357  * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edge.
358  * @warning Orders of edges in the extremities of the deleted edge are affected
359  */
360  void delEdge(edge e);
361  //=======================================================
362  /**
363  * @brief Delete all edges in the graph
364  * @warning: That operation modify the array of edges and all arrays of nodes
365  * and thus devalidate all iterators, only graph nodes iterators are not affected.
366  */
367  void delAllEdges();
368  //=======================================================
369  /**
370  * @brief Delete all nodes in the graph
371  * @warning: That operation modify the array of edges and all arrays of nodes
372  * and thus devalidate all iterators.
373  */
374  void delAllNodes();
375  //=======================================================
376 private :
377  // specific types
378  typedef SimpleVector<edge> EdgeVector;
379 
380  struct EdgeContainer {
381  EdgeVector edges;
382  unsigned int outDegree;
383 
384  EdgeContainer():outDegree(0) {}
385  };
386  typedef std::vector<EdgeContainer> Nodes;
387  typedef std::vector<std::pair< node , node > > Edges;
388 
389  // data members
390  mutable Edges edges;
391  mutable Nodes nodes;
392  IdManager nodeIds;
393  IdManager edgeIds;
394  unsigned int nbNodes;
395  unsigned int nbEdges;
396 
397  // member functions below do not belong to the public API
398  // they are just needed by the current implementation
399  //=======================================================
400  /**
401  * @brief remove an edge from an EdgeContainer
402  * @warning That operation modify the EdgeContainer
403  * and thus devalidate all iterators on it.
404  */
405  static void removeFromEdgeContainer(EdgeContainer &c, const edge e);
406  //=======================================================
407  /**
408  * @brief remove an edge from the edges structure
409  * and from the EdgeContainer of its ends
410  * except for the end node in argument if it is valid
411  * @warning That operation modify the array of edges
412  * and thus devalidate all iterators on it.
413  */
414  void removeFromEdges(const edge e, node end = node());
415 };
416 }
417 #endif // GRAPHSTORAGE_H
418 ///@endcond