Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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
35namespace tlp {
36
37template <class itType>
38struct 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 modifications of the graph structure invalidate iterations.
58 *
59 * @warning Use that class only if you need performance.
60 * @todo split the file in .h .cpp
61 */
62class TLP_SCOPE VectorGraph {
63
64public:
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 modifies the array of nodes
286 * and thus invalidates 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 modifies the array of nodes
295 * and thus invalidates 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 modifies the array of nodes and the array of edges
304 * and thus invalidates all iterators on it.
305 * @warning That operation modifies the array of neighbors of extremities of edges, thus
306 * it invalidates 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 modifies the array of neighbors of extremities of edges, thus
316 * it invalidates 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 modifies the array of edges and
326 * the adjacency edges of its ends thus any iterators existing for
327 * these structures will be invalidated.
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 modifies the array of edges
335 * and thus invalidates all iterators on it.
336 * @warning That operation modifies the array of neighbors of extremities of the edge e, thus
337 * it invalidates 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 modifies the array of edges
347 * and thus invalidates all iterators on it.
348 * @warning That operation modifies the array of neighbors of extremities of the edge e, thus
349 * it invalidates 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 modifies the array of edges and all arrays of nodes
360 * and thus invalidates 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 modifies the array of edges and all arrays of nodes
368 * and thus invalidates 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 becomes target and target becomes source
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 modifies the array of neighbors of extremities of edges, thus
407 * it invalidates 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 modifies the array of neighbors of extremities of edges, thus
421 * it invalidates 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 edge e to have the new given extremities
443 * @warning That operation modifies the array of neighbors of extremities of edges, thus
444 * it invalidates 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 dependent of stl::shuffle algorithm (should be o(N))
453 */
454 void shuffleNodes();
455 //=======================================================
456 /**
457 * @brief Shuffle the array of graph edges
458 * @remark dependent of stl::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 which implements operator():
466 * @remark dependent 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 which 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 dependent 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
679private:
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 adjust size of node properties when graph is modified
721 */
722 void addNodeToValues(node n);
723 //=======================================================
724 /**
725 * internal function to adjust size of edge properties when graph is modified
726 */
727 void addEdgeToValues(edge e);
728 //=======================================================
729 /**
730 * internal function to configure a new edge and its ends
731 */
732 void addEdgeInternal(edge e, node src, node tgt);
733 //=======================================================
734 /**
735 * internal function to remove an edge
736 */
737 void removeEdge(edge e);
738 //=======================================================
739 /**
740 * Internal function to remove the edge e in the adjacency list of n
741 */
742 void moveEdge(node n, unsigned int a, unsigned int b);
743 /**
744 * Internal function tp remove the edge e in the adjacency list of n
745 */
746 void partialDelEdge(node n, edge e);
747 //=======================================================
748};
749
750#ifndef NDEBUG // these two functions are used to insure that property has been allocated in debug
751 // mode
752template <typename TYPE>
753bool NodeProperty<TYPE>::isValid() const {
754 if (this->_graph == 0)
755 return false;
756
757 if (this->_values == 0)
758 return false;
759
760 return this->_graph->isNodeAttr(this->_values);
761}
762
763template <typename TYPE>
764bool EdgeProperty<TYPE>::isValid() const {
765 if (this->_graph == 0)
766 return false;
767
768 if (this->_values == 0)
769 return false;
770
771 return this->_graph->isEdgeAttr(this->_values);
772}
773#endif
774} // namespace tlp
775#endif // VECTORGRAPH_H
776///@endcond