Tulip  4.4.0
Better Visualization Through Research
 All Classes Namespaces 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 Returns if edges exist between two nodes
160  * @param source The source of the hypothetical edges.
161  * @param target The target of the hypothetical edges.
162  * @param directed When set to false edges from target to source are also considered
163  * @param edges The vector of edges to fill up with the edges found
164  * @param onlyFirst If true only the first edge found will be returned
165  * @return true if an edge has been bound
166  */
167  bool getEdges(const node source, const node target, bool directed,
168  std::vector<edge>& edges, bool onlyFirst = false) const;
169 
170  //=======================================================
171  /**
172  * @brief Return a Tulip Iterator on adjacent nodes of the node n
173  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
174  */
175  Iterator<node>* getInOutNodes(node n) const;
176  //=======================================================
177  /**
178  * @brief Return a Tulip Iterator on in nodes of the node n
179  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
180  */
181  Iterator<node>* getInNodes(node n) const;
182  //=======================================================
183  /**
184  * @brief Return a Tulip Iterator on out nodes of the node n
185  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
186  */
187  Iterator<node>* getOutNodes(node n) const;
188  //=======================================================
189  /**
190  * @brief Return the degree of a node
191  */
192  unsigned int deg(node n) const;
193  //=======================================================
194  /**
195  * @brief Return the out degree of a node
196  */
197  unsigned int outdeg(node n) const;
198  //=======================================================
199  /**
200  * @brief Return the in degree of a node
201  */
202  unsigned int indeg(node n) const;
203  //=======================================================
204  /**
205  * @brief Return the number of edges in the graph
206  */
207  unsigned int numberOfEdges() const;
208  //=======================================================
209  /**
210  * @brief Return the number of nodes in the graph
211  */
212  unsigned int numberOfNodes() const;
213  //=======================================================
214  /**
215  * @brief Return the extremities of an edge (src, target)
216  */
217  const std::pair<node, node>& ends(const edge e) const;
218  //=======================================================
219  /**
220  * @brief return the first extremity (considered as source if the graph is directed) of an edge
221  */
222  node source(edge e) const;
223  //=======================================================
224  /**
225  * @brief return the second extremity (considered as target if the graph is directed) of an edge
226  */
227  node target(edge e) const;
228  //=======================================================
229  /**
230  * @brief return the opposite node of n through edge e
231  */
232  node opposite(edge e, node n) const;
233  //=======================================================
234  /**
235  * @brief Reconnect the edge e to have the new given ends
236  * @warning That operation modify the array of neighboors of extrmities of edges, thus
237  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
238  */
239  void setEnds(const edge e, const node newSrc, const node newTgt);
240  //=======================================================
241  /**
242  * @brief change the source of an edge
243  * @warning That operation modify the array of neighboors of extrmities of edges, thus
244  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
245  * \see setEnds
246  */
247  void setSource(const edge e, const node n);
248  //=======================================================
249  /**
250  * @brief change the target of an edge
251  * @warning That operation modify the array of neighboors of extrmities of edges, thus
252  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
253  * \see setEnds
254  */
255  void setTarget(const edge e, const node n);
256  //=======================================================
257  /**
258  * @brief Reverse an edge e, source become target and target become soure
259  */
260  void reverse(const edge e);
261  //=======================================================
262  /**
263  * \brief Set the ordering of edges around n according to their order in v.
264  */
265  void setEdgeOrder(const node n, const std::vector<edge> &v );
266  //=======================================================
267  /**
268  * \brief swap to edge in the ordered adjacency vector
269  * \warning the two edges must be element of star(v)
270  */
271  void swapEdgeOrder(const node n, const edge e1, const edge e2);
272  //=======================================================
273  /**
274  * @brief Add the given node in the structure and return it
275  * @warning: That operation modify the array of nodes
276  * and thus devalidate all iterators on it.
277  * @complexity: o(1)
278  */
279  node addNode(node n);
280  //=======================================================
281  /**
282  * @brief Add a new node in the structure and return it
283  * @warning: That operation modify the array of nodes
284  * and thus devalidate all iterators on it.
285  * @complexity: o(1)
286  */
287  node addNode();
288  //=======================================================
289  /**
290  * @brief Add nb new nodes in the structure and returns them
291  * in the addedNodes vector
292  * @warning: That operation modify the array of nodes
293  * and thus devalidate all iterators on it. The addedNodes vector
294  * is cleared before adding nodes
295  * @complexity: o(1)
296  */
297  void addNodes(unsigned int nb, std::vector<node>& addedNodes);
298  //=======================================================
299  /**
300  * @brief Add the given nodes in the structure
301  * @warning: That operation modify the array of nodes
302  * and thus devalidate all iterators on it.
303  * @complexity: o(1)
304  */
305  void restoreNodes(const std::vector<node>& addedNodes);
306  //=======================================================
307  /**
308  * @brief remove a node from the nodes structure only
309  * @warning That operation modify the array of nodes
310  * and thus devalidate all iterators on it.
311  * @complexity: o(1)
312  */
313  void removeFromNodes(const node n);
314  //=======================================================
315  /**
316  * @brief Delete a node and all its adjacent edges in the graph
317  * @warning That operation modify the array of nodes and the array of edges
318  * and thus devalidate all iterators on it.
319  * @warning That operation modify the array of neighboors of extrmities of edges, thus
320  * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edges.
321  * @warning Orders of edges in the extremities of the deleted edges are affected
322  * @complexity: o(1)
323  */
324  void delNode(node n);
325  //=======================================================
326  /**
327  * @brief Add the given edge between src and tgt and return it
328  * the last argument indicates if the edge has to be added
329  * in the adjacency edges of its two ends
330  * @warning That operation modify the array of edges and
331  * the adjacency edges of its ends thus any iterators existing for
332  * these structures will be devalidated.
333  */
334  edge addEdge(const node src, const node tgt,
335  const edge e, bool updateEndsEdges);
336  //=======================================================
337  /**
338  * @brief Add a new edge between src and tgt and return it
339  * @warning That operation modify the array of edges and
340  * the adjacency edges of its ends thus any iterators existing for
341  * these structures will be devalidated.
342  */
343  edge addEdge(node src, node tgt);
344  //=======================================================
345  /**
346  * @brief Add edges in the structure and returns them
347  * in the addedEdges vector
348  * @warning: That operation modify the array of edges and
349  * the adjacency edges of its ends thus any iterators existing for
350  * these structures will be devalidated.
351  */
352  void addEdges(const std::vector<std::pair<node, node> >& edges,
353  std::vector<edge>& addedEdges);
354  //=======================================================
355  /**
356  * @brief restore edges in the structure and returns them
357  * in the addedEdges vector
358  * @warning: That operation modify the array of edges
359  * thus any iterators existing for
360  * these structures will be devalidated.
361  */
362  void restoreEdges(const std::vector<edge>& edgesToRestore,
363  const std::vector<std::pair<node, node> >& ends);
364 //=======================================================
365  /**
366  * @brief Delete an edge in the graph
367  * @warning: That operation modify the array of edges
368  * and thus devalidate all iterators on it.
369  * @warning That operation modify the array of neighboors of extremities of the edge e, thus
370  * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edge.
371  * @warning Orders of edges in the extremities of the deleted edge are affected
372  */
373  void delEdge(edge e);
374  //=======================================================
375  /**
376  * @brief Delete all edges in the graph
377  * @warning: That operation modify the array of edges and all arrays of nodes
378  * and thus devalidate all iterators, only graph nodes iterators are not affected.
379  */
380  void delAllEdges();
381  //=======================================================
382  /**
383  * @brief Delete all nodes in the graph
384  * @warning: That operation modify the array of edges and all arrays of nodes
385  * and thus devalidate all iterators.
386  */
387  void delAllNodes();
388  //=======================================================
389 private :
390  // specific types
391  typedef SimpleVector<edge> EdgeVector;
392 
393  struct EdgeContainer {
394  EdgeVector edges;
395  unsigned int outDegree;
396 
397  EdgeContainer():outDegree(0) {}
398  };
399  typedef std::vector<EdgeContainer> Nodes;
400  typedef std::vector<std::pair< node , node > > Edges;
401 
402  // data members
403  mutable Edges edges;
404  mutable Nodes nodes;
405  IdManager nodeIds;
406  IdManager edgeIds;
407  unsigned int nbNodes;
408  unsigned int nbEdges;
409 
410  // member functions below do not belong to the public API
411  // they are just needed by the current implementation
412  //=======================================================
413  /**
414  * @brief remove an edge from an EdgeContainer
415  * @warning That operation modify the EdgeContainer
416  * and thus devalidate all iterators on it.
417  */
418  static void removeFromEdgeContainer(EdgeContainer &c, const edge e);
419  //=======================================================
420  /**
421  * @brief remove an edge from the edges structure
422  * and from the EdgeContainer of its ends
423  * except for the end node in argument if it is valid
424  * @warning That operation modify the array of edges
425  * and thus devalidate all iterators on it.
426  */
427  void removeFromEdges(const edge e, node end = node());
428 };
429 }
430 #endif // GRAPHSTORAGE_H
431 ///@endcond