Tulip  5.0.0
Large graphs analysis and drawing
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
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 GRAPHSTORAGE_H
22 #define GRAPHSTORAGE_H
23 #include <cstring>
24 #include <cassert>
25 #include <vector>
26 
27 #include <tulip/Node.h>
28 #include <tulip/Edge.h>
29 #include <tulip/IdManager.h>
30 
31 namespace tlp {
32 
33 class Graph;
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  //=======================================================
55  void clear();
56  //=======================================================
57  /**
58  * @brief Return true if n belongs to the graph
59  */
60  inline bool isElement(const node n) const {
61  return nodeIds.isElement(n);
62  }
63  //=======================================================
64  /**
65  * @brief Return the number of nodes in the graph
66  */
67  inline unsigned int numberOfNodes() const {
68  return nodeIds.size();
69  }
70  //=======================================================
71  /**
72  * @brief Return true if e belongs to the graph
73  */
74  inline bool isElement(const edge e) const {
75  return edgeIds.isElement(e);
76  }
77  //=======================================================
78  /**
79  * @brief Return the number of edges in the graph
80  */
81  inline unsigned int numberOfEdges() const {
82  return edgeIds.size();
83  }
84  //=======================================================
85  /**
86  * @brief Enables to reserve memory for nbNodes
87  * Reserving memory before to addNode enable to reduce the number of vector resizing and then
88  * to speed up significantly construction of graphs.
89  */
90  void reserveNodes(const size_t nb);
91  //=======================================================
92  /**
93  * @brief Enables to reserve memory for nbEdges
94  * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
95  * to speed up significantly construction of graphs.
96  */
97  void reserveEdges(const size_t nb);
98  //=======================================================
99  /**
100  * @brief Enables to reserve memory for adjacency nodes
101  * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
102  * to speed up significantly construction of graphs.
103  */
104  void reserveAdj(const node n, const size_t nb);
105  //=======================================================
106  /**
107  * @brief Enables to reserve memory for adjacency nodes
108  * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
109  * to speed up significantly construction of graphs.
110  */
111  void reserveAdj(const size_t nb);
112  //=======================================================
113  /**
114  * @brief restore adjacency edges of a given node
115  */
116  void restoreAdj(const node n, const std::vector<edge>& edges);
117  //=======================================================
118  /**
119  * @brief return the adjacency edges of a given node
120  */
121  inline const std::vector<edge>& adj(const node n) const {
122  assert(isElement(n));
123  return nodeData[n.id].edges;
124  }
125  //=======================================================
126  /**
127  * @brief Return the first node of graph
128  */
129  inline node getOneNode() const {
130  return numberOfNodes() ? nodeIds[0] : node();
131  }
132  //=======================================================
133  /**
134  * @brief Return a Tulip Iterator on nodes of the graph
135  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
136  * @complexity: o(1)
137  */
138  inline Iterator<node>* getNodes() const {
139  return nodeIds.getElts();
140  }
141  //=======================================================
142  /**
143  * @brief Return the current state of the ids management
144  * must be deleted by the caller
145  * this can be used for push/pop
146  */
147  const GraphStorageIdsMemento* getIdsMemento() const;
148  //=======================================================
149  /**
150  * @brief restore a state of the ids management
151  */
152  void restoreIdsMemento(const GraphStorageIdsMemento*);
153  //=======================================================
154  /**
155  * @brief Return a Tulip Iterator on edges of the graph
156  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
157  */
158  inline Iterator<edge>* getEdges() const {
159  return edgeIds.getElts();
160  }
161  //=======================================================
162  /**
163  * @brief Return a Tulip Iterator on adjacent edges of the node n
164  * @warning: be careful that loops appear twice
165  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
166  */
167  Iterator<edge>* getInOutEdges(const node n) const;
168  //=======================================================
169  /**
170  * @brief Return a Tulip Iterator on out edges of the node n
171  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
172  */
173  Iterator<edge>* getOutEdges(const node n) const;
174  //=======================================================
175  /**
176  * @brief Return a Tulip Iterator on in edges of the node n
177  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
178  */
179  Iterator<edge>* getInEdges(const node n) const;
180  //=======================================================
181  /**
182  * @brief Return if edges exist between two nodes
183  * @param src The source of the hypothetical edges.
184  * @param tgt The target of the hypothetical edges.
185  * @param directed When set to false edges from target to source are also considered
186  * @param edges The vector of edges to fill up with the edges found
187  * @param the subgraph owning the edges
188  * @param onlyFirst If true only the first edge found will be returned
189  * @return true if an edge has been bound
190  */
191  bool getEdges(const node src, const node tgt, bool directed,
192  std::vector<edge>& edges, const Graph* sg = NULL,
193  bool onlyFirst = false) const;
194 
195  //=======================================================
196  /**
197  * @brief Return a Tulip Iterator on adjacent nodes of the node n
198  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
199  */
200  Iterator<node>* getInOutNodes(const node n) const;
201  //=======================================================
202  /**
203  * @brief Return a Tulip Iterator on in nodes of the node n
204  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
205  */
206  Iterator<node>* getInNodes(const node n) const;
207  //=======================================================
208  /**
209  * @brief Return a Tulip Iterator on out nodes of the node n
210  * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
211  */
212  Iterator<node>* getOutNodes(const node n) const;
213  //=======================================================
214  /**
215  * @brief Return the degree of a node
216  */
217  inline unsigned int deg(const node n) const {
218  assert(isElement(n));
219  return nodeData[n.id].edges.size();
220  }
221  //=======================================================
222  /**
223  * @brief Return the out degree of a node
224  */
225  inline unsigned int outdeg(const node n) const {
226  assert(isElement(n));
227  return nodeData[n.id].outDegree;
228  }
229  //=======================================================
230  /**
231  * @brief Return the in degree of a node
232  */
233  inline unsigned int indeg(const node n) const {
234  assert(isElement(n));
235  const NodeData& ctnr = nodeData[n.id];
236  return ctnr.edges.size() - ctnr.outDegree;
237  }
238  //=======================================================
239  /**
240  * @brief Return the edges of the graph
241  */
242  inline const std::vector<edge>& edges() const {
243  return edgeIds;
244  }
245  //=======================================================
246  /**
247  * @brief Return the position of an edge in the edges of the graph
248  */
249  inline unsigned int edgePos(const edge e) const {
250  return edgeIds.getPos(e);
251  }
252  //=======================================================
253  /**
254  * @brief Return the nodes of the graph
255  */
256  inline const std::vector<node>& nodes() const {
257  return nodeIds;
258  }
259  //=======================================================
260  /**
261  * @brief Return the position of a node in the nodes of the graph
262  */
263  inline unsigned int nodePos(const node n) const {
264  return nodeIds.getPos(n);
265  }
266  //=======================================================
267  /**
268  * @brief Return the extremities of an edge (src, target)
269  */
270  inline const std::pair<node, node>& ends(const edge e) const {
271  assert(isElement(e));
272  return edgeEnds[e.id];
273  }
274  //=======================================================
275  /**
276  * @brief return the first extremity (considered as source if the graph is directed) of an edge
277  */
278  inline node source(const edge e) const {
279  assert(isElement(e));
280  return edgeEnds[e.id].first;
281  }
282  //=======================================================
283  /**
284  * @brief return the second extremity (considered as target if the graph is directed) of an edge
285  */
286  inline node target(const edge e) const {
287  assert(isElement(e));
288  return edgeEnds[e.id].second;
289  }
290  //=======================================================
291  /**
292  * @brief return the opposite node of n through edge e
293  */
294  inline node opposite(const edge e, const node n) const {
295  assert(isElement(e));
296  const std::pair<node, node>& eEnds = edgeEnds[e.id];
297  assert((eEnds.first == n) || (eEnds.second == n));
298  return (eEnds.first == n) ? eEnds.second : eEnds.first;
299  }
300 
301  //=======================================================
302  /**
303  * @brief Reconnect the edge e to have the new given ends
304  * @warning That operation modify the array of neighboors of extrmities of edges, thus
305  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
306  */
307  void setEnds(const edge e, const node newSrc, const node newTgt);
308  //=======================================================
309  /**
310  * @brief change the source of an edge
311  * @warning That operation modify the array of neighboors of extrmities of edges, thus
312  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
313  * \see setEnds
314  */
315  inline void setSource(const edge e, const node n) {
316  setEnds(e, n, node());
317  }
318  //=======================================================
319  /**
320  * @brief change the target of an edge
321  * @warning That operation modify the array of neighboors of extrmities of edges, thus
322  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
323  * \see setEnds
324  */
325  inline void setTarget(const edge e, const node n) {
326  setEnds(e, node(), n);
327  }
328  //=======================================================
329  /**
330  * @brief Reverse an edge e, source become target and target become soure
331  */
332  void reverse(const edge e);
333  //=======================================================
334  /**
335  * \brief Set the ordering of edges around n according to their order in v.
336  */
337  void setEdgeOrder(const node n, const std::vector<edge> &v );
338  //=======================================================
339  /**
340  * \brief swap to edge in the ordered adjacency vector
341  * \warning the two edges must be element of star(v)
342  */
343  void swapEdgeOrder(const node n, const edge e1, const edge e2);
344  //=======================================================
345  /**
346  * @brief Add the given node in the structure and return it
347  * @warning: That operation modify the array of nodes
348  * and thus devalidate all iterators on it.
349  * @complexity: o(1)
350  */
351  void restoreNode(const node n);
352  //=======================================================
353  /**
354  * @brief Add a new node in the structure and return it
355  * @warning: That operation modify the array of nodes
356  * and thus devalidate all iterators on it.
357  * @complexity: o(1)
358  */
359  node addNode();
360  //=======================================================
361  /**
362  * @brief Add nb new nodes in the structure and returns them
363  * in the addedNodes vector
364  * @warning: That operation modify the array of nodes
365  * and thus devalidate all iterators on it. The addedNodes vector
366  * is cleared before adding nodes
367  * @complexity: o(1)
368  */
369  void addNodes(unsigned int nb, std::vector<node>* addedNodes = NULL);
370  //=======================================================
371  /**
372  * @brief remove a node from the nodes structure only
373  * @warning That operation modify the array of nodes
374  * and thus devalidate all iterators on it.
375  * @complexity: o(1)
376  */
377  void removeFromNodes(const node n);
378  //=======================================================
379  /**
380  * @brief Delete a node and all its adjacent edges in the graph
381  * @warning That operation modify the array of nodes and the array of edges
382  * and thus devalidate all iterators on it.
383  * @warning That operation modify the array of neighboors of extrmities of edges, thus
384  * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edges.
385  * @warning Orders of edges in the extremities of the deleted edges are affected
386  * @complexity: o(1)
387  */
388  void delNode(const node n);
389  //=======================================================
390  /**
391  * @brief restore the given edge between src and tgt and return it
392  * the last argument indicates if the edge has to be added
393  * in the adjacency edges of its two ends
394  * @warning That operation modify the array of edges and
395  * the adjacency edges of its ends thus any iterators existing for
396  * these structures will be devalidated.
397  */
398  void restoreEdge(const node src, const node tgt, const edge e);
399  //=======================================================
400  /**
401  * @brief Add a new edge between src and tgt and return it
402  * @warning That operation modify the array of edges and
403  * the adjacency edges of its ends thus any iterators existing for
404  * these structures will be devalidated.
405  */
406  edge addEdge(const node src, const node tgt);
407  //=======================================================
408  /**
409  * @brief Add edges in the structure and returns them
410  * in the addedEdges vector
411  * @warning: That operation modify the array of edges and
412  * the adjacency edges of its ends thus any iterators existing for
413  * these structures will be devalidated.
414  */
415  void addEdges(const std::vector<std::pair<node, node> >& edges,
416  std::vector<edge>* addedEdges = NULL);
417 //=======================================================
418  /**
419  * @brief Delete an edge in the graph
420  * @warning: That operation modify the array of edges
421  * and thus devalidate all iterators on it.
422  * @warning That operation modify the array of neighboors of extremities of the edge e, thus
423  * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edge.
424  * @warning Orders of edges in the extremities of the deleted edge are affected
425  */
426  void delEdge(const edge e);
427  //=======================================================
428  /**
429  * @brief Delete all edges in the graph
430  * @warning: That operation modify the array of edges and all arrays of nodes
431  * and thus devalidate all iterators, only graph nodes iterators are not affected.
432  */
433  void delAllEdges();
434  //=======================================================
435  /**
436  * @brief Delete all nodes in the graph
437  * @warning: That operation modify the array of edges and all arrays of nodes
438  * and thus devalidate all iterators.
439  */
440  void delAllNodes();
441  //=======================================================
442  /**
443  * @brief sort the graph elements in ascending order
444  * @warning: That operation modify the vector of nodes and the vector of edges
445  * and thus devalidate all iterators.
446  */
447  inline void sortElts() {
448  nodeIds.sort();
449  edgeIds.sort();
450  }
451  //=======================================================
452 private :
453  // specific types
454  struct NodeData {
455  std::vector<edge> edges;
456  unsigned int outDegree;
457  unsigned int pos;
458 
459  NodeData(unsigned int pos = UINT_MAX): outDegree(0), pos(pos) {}
460  };
461 
462  // data members
463  mutable std::vector<std::pair<node, node> > edgeEnds;
464  mutable std::vector<NodeData> nodeData;
465  IdContainer<node> nodeIds;
466  IdContainer<edge> edgeIds;
467 
468  // member functions below do not belong to the public API
469  // they are just needed by the current implementation
470  //=======================================================
471  /**
472  * @brief remove an edge from an NodeData
473  * @warning That operation modify the NodeData
474  * and thus devalidate all iterators on it.
475  */
476  static void removeFromNodeData(NodeData &c, const edge e);
477  //=======================================================
478  /**
479  * @brief remove an edge from the edges structure
480  * and from the NodeData of its ends
481  * except for the end node in argument if it is valid
482  * @warning That operation modify the array of edges
483  * and thus devalidate all iterators on it.
484  */
485  void removeFromEdges(const edge e, node end = node());
486 };
487 }
488 #endif // GRAPHSTORAGE_H
489 ///@endcond
Interface for Tulip iterators. Allows basic iteration operations only.
Definition: Iterator.h:39