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