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