Tulip  4.3.0
Better Visualization Through Research
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Groups Pages
vectorgraph.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 VECTORGRAPH_H
23 #define VECTORGRAPH_H
24 #include <vector>
25 #include <algorithm>
26 
27 #include <set>
28 #include <cassert>
29 
30 #include <tulip/tulipconf.h>
31 #include <tulip/Node.h>
32 #include <tulip/Edge.h>
33 #include <tulip/vectorgraphproperty.h>
34 
35 namespace tlp {
36 
37 template<class itType >
38 struct Iterator;
39 //===========================================
40 /**
41  * @class VectorGraph
42  *
43  * @brief That class provide a simple implementation of graph structure (without subgraphs, observer, metagraph)
44  * it enables to obtain very efficient access/modification time.
45  *
46  * User can both use tulip iterators or direct vector to access to the graph structure for better performance.
47  * To have maximum speedup, that Graph implementation use only vectors, almost all operations
48  * are done in constant time (even modification), however since the class use vectors, modification
49  * of adjacency can change the ordering of edges around nodes. If you use it only for standard
50  * graph operations there is no problem. However if you want to manipulate maps, be aware that
51  * a modification can change the graph embedding. EdgeOrdering function can be used to reorder
52  * correctly elements when necessary.
53  *
54  * @warning the class is not thread safe
55  * @warning modification of the graph structure devalidate iterations.
56  *
57  * @warning Use that class only if you need performance.
58  * @todo split the file in .h .cpp
59  */
60 class TLP_SCOPE VectorGraph {
61 
62 public:
63  //=======================================================
64  VectorGraph();
65  //=======================================================
66  ~VectorGraph();
67  //=======================================================
68  /**
69  * @brief delete all nodes/edges and Properties of the graph
70  * @remark o(N + E + NbProp)
71  */
72  void clear();
73  //=======================================================
74  /**
75  * @brief Test if an edge exist between two nodes, in directed mode the orientation
76  * is taken into account.
77  * @return the found edge, else an invalid edge.
78  * @remark o(min(deg(src), deg(tgt))
79  * @todo test
80  */
81  edge existEdge(const node src, const node tgt, const bool directed = true) const;
82  //=======================================================
83  /**
84  * @brief Return true if n belongs to the graph
85  * @remark o(1)
86  */
87  bool isElement(const node n) const;
88  //=======================================================
89  /**
90  * @brief Return true if e belongs to the graph
91  * @remark o(1)
92  */
93  bool isElement(const edge e) const;
94  //=======================================================
95  /**
96  * \brief Set the ordering of edges around n according to their order in v.
97  * \warning there is no test here, all edge in v must be element of star(e)
98  * @remark o(v.size())
99  */
100  void setEdgeOrder(const node n, const std::vector<edge> &v );
101  //=======================================================
102  /**
103  * \brief swap to edge in the ordered adjacency vector
104  * \warning the two edges must be element of star(v)
105  * @remark o(1)
106  */
107  void swapEdgeOrder(const node n, const edge e1, const edge e2);
108  //=======================================================
109  /**
110  * @brief Enables to reserve memory for nbNodes
111  * Reserving memory before to addNode enable to reduce the number of vector resizing and then
112  * to speed up significantly construction of graphs.
113  * @remark o(N + nbNodes)
114  */
115  void reserveNodes(const size_t nbNodes);
116  //=======================================================
117  /**
118  * @brief Enables to reserve memory for nbEdges
119  * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
120  * to speed up significantly construction of graphs.
121  * @remark o(N + nbNodes)
122  */
123  void reserveEdges(const size_t nbEdges);
124  //=======================================================
125  /**
126  * @brief Enables to reserve memory for adjacency nodes
127  * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
128  * to speed up significantly construction of graphs.
129  * @remark o(E + nbEdges)
130  */
131  void reserveAdj(const size_t nbEdges);
132  //=======================================================
133  /**
134  * @brief Enables to reserve memory for adjacency nodes
135  * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
136  * to speed up significantly construction of graphs.
137  * @remark o(E + nbEdges)
138  */
139  void reserveAdj(const node n, const size_t nbEdges);
140  //=======================================================
141  /**
142  * @brief Return the node at position id in the array of nodes
143  * @remark o(1)
144  */
145  node operator[](const unsigned int id) const;
146  //=======================================================
147  /**
148  * @brief Return the edge at position id in the array of nodes
149  * @remark o(1)
150  */
151  edge operator()(const unsigned int id) const;
152  //=======================================================
153  /**
154  * @brief Return the first node of graph (ie first node in the array of nodes)
155  * @remark o(1)
156  */
157  node getOneNode() const;
158  //=======================================================
159  /**
160  * @brief Return a Tulip Iterator on nodes of the graph
161  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
162  * @remark: o(1)
163  */
164  Iterator<node> * getNodes() const;
165  //=======================================================
166  /**
167  * @brief Return a Tulip Iterator on edges of the graph
168  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
169  * @remark: o(1)
170  */
171  Iterator<edge> * getEdges() const;
172  //=======================================================
173  /**
174  * @brief Return a Tulip Iterator on adjacent edges of the node n
175  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
176  * @remark: o(1)
177  */
178  Iterator<edge> * getInOutEdges(const node n) const;
179  //=======================================================
180  /**
181  * @brief Return a Tulip Iterator on out edges of the node n
182  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
183  * @remark: o(1)
184  */
185  Iterator<edge> * getOutEdges(const node n) const;
186  //=======================================================
187  /**
188  * @brief Return a Tulip Iterator on in edges of the node n
189  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
190  * @remark: o(1)
191  */
192  Iterator<edge> * getInEdges(const node n) const;
193  //=======================================================
194  /**
195  * @brief Return a Tulip Iterator on adjacent nodes of the node n
196  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
197  * @remark: o(1)
198  */
199  Iterator<node> * getInOutNodes(const node n) const;
200  //=======================================================
201  /**
202  * @brief Return a Tulip Iterator on in nodes of the node n
203  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
204  * @remark o(1)
205  */
206  //=======================================================
207  Iterator<node> * getInNodes(const node n) const;
208  /**
209  * @brief Return a Tulip Iterator on out nodes of the node n
210  * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
211  * @remark o(1)
212  */
213  //=======================================================
214  Iterator<node> * getOutNodes(const node n) const;
215  //=======================================================
216  /**
217  * @brief Return the degree of a node
218  * @remark o(1)
219  */
220  unsigned int deg(const node n) const;
221  //=======================================================
222  /**
223  * @brief Return the out degree of a node
224  * @remark o(1)
225  */
226  unsigned int outdeg(const node n) const;
227  //=======================================================
228  /**
229  * @brief Return the in degree of a node
230  * @remark o(1)
231  */
232  unsigned int indeg(const node n) const;
233  //=======================================================
234  /**
235  * @brief Return the number of edges in the graph
236  * @remark: o(1)
237  */
238  unsigned int numberOfEdges() const;
239  //=======================================================
240  /**
241  * @brief Return the number of nodes in the graph
242  * @remark: o(1)
243  */
244  unsigned int numberOfNodes() const;
245  //=======================================================
246  /**
247  * @brief Add a new node in the graph and return it
248  * @warning: That operation modify the array of nodes
249  * and thus devalidate all iterators on it.
250  * @remark: o(1)
251  */
252  node addNode();
253  //=======================================================
254  /**
255  * @brief Delete a node and all its adjacent edges in the graph
256  * @warning That operation modify the array of nodes and the array of edges
257  * and thus devalidate all iterators on it.
258  * @warning That operation modify the array of neighboors of extrmities of edges, thus
259  * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edges.
260  * @warning Orders of edges in the extremities of the deleted edges are affected
261  * @remark: o(1)
262  */
263  void delNode(const node n);
264  //=======================================================
265  /**
266  * @brief Add a new edge between src and tgt and return it
267  * @warning That operation modify the array of neighboors of extrmities of edges, thus
268  * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edges.
269  * @remark o(1)
270  */
271  edge addEdge(const node src, const node tgt);
272  //=======================================================
273  /**
274  * @brief Delete an edge in the graph
275  * @warning: That operation modify the array of edges
276  * and thus devalidate all iterators on it.
277  * @warning That operation modify the array of neighboors of extremities of the edge e, thus
278  * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edge.
279  * @warning Orders of edges in the extremities of the deleted edge are affected
280  * @remark o(1)
281  */
282  void delEdge(const edge e);
283  //=======================================================
284  /**
285  * @brief Delete all adjacent edges (in/out) of a node
286  * @warning: That operation modify the array of edges
287  * and thus devalidate all iterators on it.
288  * @warning That operation modify the array of neighboors of extremities of the edge e, thus
289  * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edge.
290  * @warning Orders of edges in the extremities of the deleted edge are affected
291  * @remark o(deg(V))
292  * @todo test
293  */
294  void delEdges(const node n);
295  //=======================================================
296  /**
297  * @brief Delete all edges in the graph
298  * @warning: That operation modify the array of edges and all arrays of nodes
299  * and thus devalidate all iterators, only graph nodes iterators are not affected.
300  * @remark o(E + V)
301  */
302  void delAllEdges();
303  //=======================================================
304  /**
305  * @brief Delete all nodes in the graph
306  * @warning: That operation modify the array of edges and all arrays of nodes
307  * and thus devalidate all iterators.
308  * @remark o(E + V)
309  */
310  void delAllNodes();
311  //=======================================================
312  /**
313  * @brief return the first extremity (considered as source if the graph is directed) of an edge
314  * @remark o(1)
315  */
316  node source(const edge e) const;
317  //=======================================================
318  /**
319  * @brief return the second extremity (considered as target if the graph is directed) of an edge
320  * @remark o(1)
321  */
322  node target(const edge e) const;
323  //=======================================================
324  /**
325  * @brief return the opposite node of n through edge e
326  * @remark o(1)
327  */
328  node opposite(const edge e, const node n) const;
329  //=======================================================
330  /**
331  * @brief Reverse an edge e, source become target and target become soure
332  * @remark o(1)
333  */
334  void reverse(const edge e);
335  //=======================================================
336  /**
337  * @brief change the source of an edge
338  * @warning That operation modify the array of neighboors of extrmities of edges, thus
339  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
340  * @remark o(1)
341  * \see setEnds
342  */
343  void setSource(const edge e, const node n);
344  //=======================================================
345  /**
346  * @brief change the target of an edge
347  * @warning That operation modify the array of neighboors of extrmities of edges, thus
348  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
349  * @remark o(1)
350  * \see setEnds
351  */
352  void setTarget(const edge e, const node n);
353  //=======================================================
354  /**
355  * @brief Return the extremities of an edge (src, target)
356  * @remark o(1)
357  */
358  std::pair<node, node> ends(const edge e) const;
359  //=======================================================
360  /**
361  * @brief Reconnect the edeg e to have the new given extremities
362  * @warning That operation modify the array of neighboors of extrmities of edges, thus
363  * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
364  * @remark o(1)
365  */
366  void setEnds(const edge e, const node src, const node tgt);
367  //=======================================================
368  /**
369  * @brief Shuffle the array of graph nodes
370  * @remark dependant of stl::random_shuffle algorithm (should be o(N))
371  */
372  void shuffleNodes();
373  //=======================================================
374  /**
375  * @brief Shuffle the array of graph edges
376  * @remark dependant of stl::random_shuffle algorithm (should be o(E))
377  */
378  void shuffleEdges();
379  //=======================================================
380  /**
381  * @brief Sort all edges according to comparison functor given in parameter
382  * if stable is true a stable sort algorithm is applied
383  * Comparison should be an instance of a class wihch implements operator():
384  * @remark dependant of stl::sort and stl::stable_sort algorithm (should be o(E log (E)))
385  * @code
386  * class Compare {
387  * //return true if a < b
388  * bool operator()(const edge a, const edge b);
389  * };
390  * @endcode
391  * \warning that function is not compatible with the Tulip Graph API
392  */
393  template<typename Compare>
394  void sortEdges(Compare cmp, bool stable = false) {
395  if (stable)
396  stable_sort(_edges.begin(), _edges.end(), cmp);
397  else
398  sort(_edges.begin(), _edges.end(), cmp);
399 
400  //recompute indices of edges
401  for (unsigned int i = 0; i < _edges.size(); ++i) {
402  _eData[_edges[i]]._edgesId = i;
403  }
404  }
405  //=======================================================
406  /**
407  * @brief Sort all nodes according to comparison functor given in parameter
408  * if stable is true a stable sort algorithm is applied
409  * Comparison should be an instance of a class wihch implements operator():
410  * @code
411  * class Compare {
412  * //return true if a < b
413  * bool operator()(const node a, const node b);
414  * };
415  * @endcode
416  * @remark dependant of stl::sort and stl::stable_sort algorithm (should be o(N log (N)))
417  * \warning that function is not compatible with the Tulip Graph API
418  */
419  template<typename Compare >
420  void sortNodes(Compare cmp, bool stable = false) {
421  if (stable)
422  stable_sort(_nodes.begin(), _nodes.end(), cmp);
423  else
424  sort(_nodes.begin(), _nodes.end(), cmp);
425 
426  //recompute indices of edges
427  for (unsigned int i = 0; i < _nodes.size(); ++i) {
428  _nData[_nodes[i]]._nodesId = i;
429  }
430  }
431  //=======================================================
432  /**
433  * @brief return the position of an edge in the array of edges.
434  * \warning that function is not compatible with the Tulip Graph API
435  * @remark o(1)
436  */
437  unsigned int edgePos(const edge e) const;
438  //=======================================================
439  /**
440  * @brief return the position of a node in the array of nodes.
441  * \warning that function is not compatible with the Tulip Graph API
442  * @remark o(1)
443  */
444  unsigned int nodePos(const node n) const;
445  //=======================================================
446  /**
447  * @brief Swap two nodes in the array of graph nodes
448  * @remark o(1)
449  * \warning that function is not compatible with the Tulip Graph API
450  */
451  void swap(const node a, const node b);
452  //=======================================================
453  /**
454  * @brief Swap two edges in the array of graph edge
455  * @remark o(1)
456  * \warning that function is not compatible with the Tulip Graph API
457  */
458  void swap(const edge a, const edge b);
459  //=======================================================
460  /**
461  * @brief Create a new node array of type TYPE
462  * NodesAttr can be copied in constant time it is just a pointer
463  * NodesAttr is not a smart pointer it must be deleted with freeNodesAttribute
464  * @remark o(log(number of arrays) + new of a vector<TYPE> of size N)
465  * \warning that function is not compatible with the Tulip Graph API
466  */
467  template<typename TYPE>
468  void alloc(NodeProperty<TYPE> &prop) {
469  ValArray<TYPE> *array = new ValArray<TYPE>(_nodes.size() + _freeNodes.size(), _nodes.capacity());
470  _nodeArrays.insert(array);
471  prop = NodeProperty<TYPE>(array, this);
472  }
473  //=======================================================
474  /**
475  * @brief Delete an Array from the set of node arrays
476  * @warning all copy of the ValArray are no more valid (serious bug if they are used after)
477  * @remark o(log(number of arrays) + free of a vector<TYPE> of size N)
478  * \warning that function is not compatible with the Tulip Graph API
479  */
480  template<typename TYPE>
481  void free(NodeProperty<TYPE> array) {
482  assert(_nodeArrays.find(array._array) != _nodeArrays.end());
483  delete array._array;
484  _nodeArrays.erase(array._array);
485  }
486  //=======================================================
487  /**
488  * @brief Create a new edge array of type TYPE
489  * EdgesAttr can be copied in constant time it is just a pointer
490  * EdgesAttr is not a smart pointer it must be deleted with freeEdgesAttribute
491  * @remark o(log(number of node arrays) + new of a vector<TYPE> of size E)
492  * \warning that function is not compatible with the Tulip Graph API
493  */
494  template<typename TYPE>
495  void alloc(EdgeProperty<TYPE> &prop) {
496  ValArray<TYPE> *array = new ValArray<TYPE>(_edges.size() + _freeEdges.size(), _edges.capacity());
497  _edgeArrays.insert(array);
498  prop = EdgeProperty<TYPE>(array, this);
499  }
500  //=======================================================
501  /**
502  * @brief Delete an Array from the set of edge arrays
503  * @warning all copy of the ValArray are no more valid (serious bug if they are used after)
504  * @remark o(log(number of edge arrays) + free of a vector<TYPE> of size E)
505  * \warning that function is not compatible with the Tulip Graph API
506  */
507  template<typename TYPE>
508  void free(EdgeProperty<TYPE> array) {
509  assert(_edgeArrays.find(array._array) != _edgeArrays.end());
510  delete array._array;
511  _edgeArrays.erase(array._array);
512  }
513  //=======================================================
514  /**
515  * @brief Return a const reference on the vector of adjacent nodes of n
516  *
517  * It is the fastest way to access to node adjacency, Iterators are 25% slower.
518  * \warning code that use that function won't be compatible with Tulip Graph API
519  *
520  * @remark o(1)
521  * \see getInOutNodes
522  * \see getInNodes
523  * \see getOutNodes
524  */
525  const std::vector<node>& adj(const node n) const;
526  //=======================================================
527  /**
528  * @brief Return a const reference on the vector of adjacent edges of n
529  *
530  * It is the fastest way to access to edge adjacency, Iterators are 25% slower.
531  * \warning code that use that function won't be compatible with Tulip Graph API
532  *
533  * @remark o(1)
534  * \see getInOutEdges
535  * \see getInEdges
536  * \see getOutEdges
537  */
538  const std::vector<edge>& star(const node n) const;
539  //=======================================================
540  /**
541  * @brief Return a const reference on the vector of nodes of the graph
542  * It is the fastest way to access to edge adjacency, Iterators are 25% slower.
543  * \warning code that use that function won't be compatible with Tulip Graph API
544  * @remark o(1)
545  */
546  const std::vector<node>& nodes() const;
547  //=======================================================
548  /**
549  * @brief Return a const reference on the vector of edges of the graph
550  * It is the fastest way to access to edge adjacency, Iterators are 25% slower.
551  * \warning code that use that function won't be compatible with Tulip Graph API
552  * @remark o(1)
553  */
554  const std::vector<edge>& edges() const;
555  //=======================================================
556 #ifndef NDEBUG
557  /**
558  * these two function are used internally to insure that property has been allocated in debug mode
559  * @warning never used these function directly even in debug mode !!!
560  */
561  template<typename TYPE>
562  bool isNodeAttr(ValArray<TYPE> *array) {
563  return (_nodeArrays.find(array) != _nodeArrays.end());
564  }
565  template<typename TYPE>
566  bool isEdgeAttr(ValArray<TYPE> *array) {
567  return (_edgeArrays.find(array) != _edgeArrays.end());
568  }
569 #endif
570  //=============================================================
571  /**
572  * output the graph in a very simple way for debugging
573  */
574  void dump() const;
575  //=============================================================
576  /**
577  * internal function to test the integrity of the graph
578  */
579  void integrityTest();
580 
581 private:
582 
583  struct _iNodes {
584  _iNodes(unsigned int id = UINT_MAX): _nodesId(id), _outdeg(0) {
585  }
586 
587  void clear() {
588  _outdeg = 0;
589  _adjt.resize(0);
590  _adjn.resize(0);
591  _adje.resize(0);
592  }
593 
594  void addEdge(bool t, node n, edge e) {
595  _adjt.push_back(t);
596  _adjn.push_back(n);
597  _adje.push_back(e);
598  }
599 
600  unsigned int _nodesId; /** index of a node in the _nodes vector*/
601  unsigned int _outdeg; /** out degree of nodes */
602  std::vector<bool> _adjt; /** orientation of the edge, used to separate in and out edges/nodes */
603  std::vector<node> _adjn; /** inout nodes*/
604  std::vector<edge> _adje; /** inout edges*/
605  };
606 
607  struct _iEdges {
608  unsigned int _edgesId; /** index of a node in the _edges vector*/
609  std::pair<node, node> _edgeExtremities; /** source and target of an edge */
610  std::pair<unsigned int, unsigned int> _edgeExtremitiesPos; /** source and target of an edge */
611  };
612 
613  std::vector<_iNodes> _nData; /** internal storage of nodes */
614  std::vector<_iEdges> _eData; /** internal storage of edges */
615 
616  std::vector< node > _nodes; /** vector of nodes element of the graph */
617  std::vector< edge > _edges; /** vector of edges element of the graph */
618 
619  std::vector<node> _freeNodes; /** vector of nodes that has been deleted and that can be reused */
620  std::vector<edge> _freeEdges; /** vector of edges that has been deleted and that can be reused */
621 
622  std::set<ValArrayInterface *> _nodeArrays; /** set of all node properties allocated on that graph */
623  std::set<ValArrayInterface *> _edgeArrays; /** set of all edge properties allocated on that graph */
624 
625  //=======================================================
626  /**
627  * internal function to break the program and output debug information during
628  * integrity test.
629  * @TODO hide that function in the .cpp file
630  */
631  void testCond(std::string str, bool b);
632  //=======================================================
633  /**
634  * internal function to adjust size of node properties when graph is modified
635  */
636  void addNodeToArray(node n);
637  //=======================================================
638  /**
639  * internal function to adjust size of edge properties when graph is modified
640  */
641  void addEdgeToArray(edge e);
642  //=======================================================
643  /**
644  * internal function to remove an edge
645  */
646  void removeEdge(edge e);
647  //=======================================================
648  /**
649  * Internal function to remove the edge e in the adjacency list of n
650  */
651  void moveEdge(node n, unsigned int a, unsigned int b);
652  /**
653  * Internal function tp remove the edge e in the adjacency list of n
654  */
655  void partialDelEdge(node n, edge e);
656  //=======================================================
657 };
658 
659 
660 #ifndef NDEBUG //these two function are used to insure that property has been allocated in debug mode
661 template <typename TYPE>
662 bool NodeProperty<TYPE>::isValid() const {
663  if (this->_graph == 0) return false;
664 
665  if (this->_array == 0) return false;
666 
667  return this->_graph->isNodeAttr(this->_array);
668 }
669 
670 template <typename TYPE>
671 bool EdgeProperty<TYPE>::isValid() const {
672  if (this->_graph == 0) return false;
673 
674  if (this->_array == 0) return false;
675 
676  return this->_graph->isEdgeAttr(this->_array);
677 }
678 #endif
679 }
680 #endif // VECTORGRAPH_H
681 ///@endcond