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