Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
GraphStorage.h
1/*
2 *
3 * This file is part of Tulip (https://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
31namespace tlp {
32
33class 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 */
41class GraphStorageIdsMemento {
42public:
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 */
51class GraphStorage {
52public:
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 modifies the array of neighbors of extremities of edges, thus
303 * it invalidates 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 modifies the array of neighbors of extremities of edges, thus
311 * it invalidates 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 modifies the array of neighbors of extremities of edges, thus
322 * it invalidates 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 becomes target and target becomes source
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 two edges 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 modifies the array of nodes
349 * and thus invalidates 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 modifies the array of nodes
357 * and thus invalidates 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 modifies the array of nodes
366 * and thus invalidates 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 modifies the array of nodes
375 * and thus invalidates 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 modifies the array of nodes and the array of edges
383 * and thus invalidates all iterators on it.
384 * @warning That operation modifies the array of neighbors of extremities of edges, thus
385 * it invalidates 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 modifies the array of edges and
396 * the adjacency edges of its ends thus any iterators existing for
397 * these structures will be invalidated.
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 modifies the array of edges and
404 * the adjacency edges of its ends thus any iterators existing for
405 * these structures will be invalidated.
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 modifies the array of edges and
413 * the adjacency edges of its ends thus any iterators existing for
414 * these structures will be invalidated.
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 modifies the array of edges
422 * and thus invalidates all iterators on it.
423 * @warning That operation modifies the array of neighbors of extremities of the edge e, thus
424 * it invalidates 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 modifies the array of edges and all arrays of nodes
432 * and thus invalidates 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 modifies the array of edges and all arrays of nodes
439 * and thus invalidates all iterators.
440 */
441 void delAllNodes();
442 //=======================================================
443 /**
444 * @brief sort the graph elements in ascending order
445 * @warning: That operation modifies the vector of nodes and the vector of edges
446 * and thus invalidates all iterators.
447 */
448 inline void sortElts() {
449 nodeIds.sort();
450 edgeIds.sort();
451 }
452 //=======================================================
453private:
454 // specific types
455 struct NodeData {
456 std::vector<edge> edges;
457 unsigned int outDegree;
458
459 NodeData() : outDegree(0) {}
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 modifies the NodeData
474 * and thus invalidates 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 modifies the array of edges
483 * and thus invalidates all iterators on it.
484 */
485 void removeFromEdges(const edge e, node end = node());
486};
487} // namespace tlp
488#endif // GRAPHSTORAGE_H
489///@endcond