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