![]() |
Tulip
4.6.0
Better Visualization Through Research
|
00001 /* 00002 * 00003 * This file is part of Tulip (www.tulip-software.org) 00004 * 00005 * Authors: David Auber and the Tulip development Team 00006 * from LaBRI, University of Bordeaux 00007 * 00008 * Tulip is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU Lesser General Public License 00010 * as published by the Free Software Foundation, either version 3 00011 * of the License, or (at your option) any later version. 00012 * 00013 * Tulip is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00016 * See the GNU General Public License for more details. 00017 * 00018 */ 00019 ///@cond DOXYGEN_HIDDEN 00020 00021 00022 #ifndef VECTORGRAPH_H 00023 #define VECTORGRAPH_H 00024 #include <vector> 00025 #include <algorithm> 00026 00027 #include <set> 00028 #include <cassert> 00029 00030 #include <tulip/tulipconf.h> 00031 #include <tulip/Node.h> 00032 #include <tulip/Edge.h> 00033 #include <tulip/vectorgraphproperty.h> 00034 00035 namespace tlp { 00036 00037 template<class itType > 00038 struct Iterator; 00039 //=========================================== 00040 /** 00041 * @class VectorGraph 00042 * 00043 * @brief That class provide a simple implementation of graph structure (without subgraphs, observer, metagraph) 00044 * it enables to obtain very efficient access/modification time. 00045 * 00046 * User can both use tulip iterators or direct vector to access to the graph structure for better performance. 00047 * To have maximum speedup, that Graph implementation use only vectors, almost all operations 00048 * are done in constant time (even modification), however since the class use vectors, modification 00049 * of adjacency can change the ordering of edges around nodes. If you use it only for standard 00050 * graph operations there is no problem. However if you want to manipulate maps, be aware that 00051 * a modification can change the graph embedding. EdgeOrdering function can be used to reorder 00052 * correctly elements when necessary. 00053 * 00054 * @warning the class is not thread safe 00055 * @warning modification of the graph structure devalidate iterations. 00056 * 00057 * @warning Use that class only if you need performance. 00058 * @todo split the file in .h .cpp 00059 */ 00060 class TLP_SCOPE VectorGraph { 00061 00062 public: 00063 //======================================================= 00064 VectorGraph(); 00065 //======================================================= 00066 ~VectorGraph(); 00067 //======================================================= 00068 /** 00069 * @brief delete all nodes/edges and Properties of the graph 00070 * @remark o(N + E + NbProp) 00071 */ 00072 void clear(); 00073 //======================================================= 00074 /** 00075 * @brief Test if an edge exist between two nodes, in directed mode the orientation 00076 * is taken into account. 00077 * @return the found edge, else an invalid edge. 00078 * @remark o(min(deg(src), deg(tgt)) 00079 * @todo test 00080 */ 00081 edge existEdge(const node src, const node tgt, const bool directed = true) const; 00082 //======================================================= 00083 /** 00084 * @brief Return true if n belongs to the graph 00085 * @remark o(1) 00086 */ 00087 bool isElement(const node n) const; 00088 //======================================================= 00089 /** 00090 * @brief Return true if e belongs to the graph 00091 * @remark o(1) 00092 */ 00093 bool isElement(const edge e) const; 00094 //======================================================= 00095 /** 00096 * \brief Set the ordering of edges around n according to their order in v. 00097 * \warning there is no test here, all edge in v must be element of star(e) 00098 * @remark o(v.size()) 00099 */ 00100 void setEdgeOrder(const node n, const std::vector<edge> &v ); 00101 //======================================================= 00102 /** 00103 * \brief swap to edge in the ordered adjacency vector 00104 * \warning the two edges must be element of star(v) 00105 * @remark o(1) 00106 */ 00107 void swapEdgeOrder(const node n, const edge e1, const edge e2); 00108 //======================================================= 00109 /** 00110 * @brief Enables to reserve memory for nbNodes 00111 * Reserving memory before to addNode enable to reduce the number of vector resizing and then 00112 * to speed up significantly construction of graphs. 00113 * @remark o(N + nbNodes) 00114 */ 00115 void reserveNodes(const size_t nbNodes); 00116 //======================================================= 00117 /** 00118 * @brief Enables to reserve memory for nbEdges 00119 * Reserving memory before to addEdge enable to reduce the number of vector resizing and then 00120 * to speed up significantly construction of graphs. 00121 * @remark o(N + nbNodes) 00122 */ 00123 void reserveEdges(const size_t nbEdges); 00124 //======================================================= 00125 /** 00126 * @brief Enables to reserve memory for adjacency nodes 00127 * Reserving memory before to addEdge enable to reduce the number of vector resizing and then 00128 * to speed up significantly construction of graphs. 00129 * @remark o(E + nbEdges) 00130 */ 00131 void reserveAdj(const size_t nbEdges); 00132 //======================================================= 00133 /** 00134 * @brief Enables to reserve memory for adjacency nodes 00135 * Reserving memory before to addEdge enable to reduce the number of vector resizing and then 00136 * to speed up significantly construction of graphs. 00137 * @remark o(E + nbEdges) 00138 */ 00139 void reserveAdj(const node n, const size_t nbEdges); 00140 //======================================================= 00141 /** 00142 * @brief Return the node at position id in the array of nodes 00143 * @remark o(1) 00144 */ 00145 node operator[](const unsigned int id) const; 00146 //======================================================= 00147 /** 00148 * @brief Return the edge at position id in the array of nodes 00149 * @remark o(1) 00150 */ 00151 edge operator()(const unsigned int id) const; 00152 //======================================================= 00153 /** 00154 * @brief Return the first node of graph (ie first node in the array of nodes) 00155 * @remark o(1) 00156 */ 00157 node getOneNode() const; 00158 //======================================================= 00159 /** 00160 * @brief Return a Tulip Iterator on nodes of the graph 00161 * @warning: The returned iterator should be deleted by the caller to prevent memory leaks 00162 * @remark: o(1) 00163 */ 00164 Iterator<node> * getNodes() const; 00165 //======================================================= 00166 /** 00167 * @brief Return a Tulip Iterator on edges of the graph 00168 * @warning: The returned iterator should be deleted by the caller to prevent memory leaks 00169 * @remark: o(1) 00170 */ 00171 Iterator<edge> * getEdges() const; 00172 //======================================================= 00173 /** 00174 * @brief Return a Tulip Iterator on adjacent edges of the node n 00175 * @warning: The returned iterator should be deleted by the caller to prevent memory leaks 00176 * @remark: o(1) 00177 */ 00178 Iterator<edge> * getInOutEdges(const node n) const; 00179 //======================================================= 00180 /** 00181 * @brief Return a Tulip Iterator on out edges of the node n 00182 * @warning: The returned iterator should be deleted by the caller to prevent memory leaks 00183 * @remark: o(1) 00184 */ 00185 Iterator<edge> * getOutEdges(const node n) const; 00186 //======================================================= 00187 /** 00188 * @brief Return a Tulip Iterator on in edges of the node n 00189 * @warning: The returned iterator should be deleted by the caller to prevent memory leaks 00190 * @remark: o(1) 00191 */ 00192 Iterator<edge> * getInEdges(const node n) const; 00193 //======================================================= 00194 /** 00195 * @brief Return a Tulip Iterator on adjacent nodes of the node n 00196 * @warning: The returned iterator should be deleted by the caller to prevent memory leaks 00197 * @remark: o(1) 00198 */ 00199 Iterator<node> * getInOutNodes(const node n) const; 00200 //======================================================= 00201 /** 00202 * @brief Return a Tulip Iterator on in nodes of the node n 00203 * @warning: The returned iterator should be deleted by the caller to prevent memory leaks 00204 * @remark o(1) 00205 */ 00206 //======================================================= 00207 Iterator<node> * getInNodes(const node n) const; 00208 /** 00209 * @brief Return a Tulip Iterator on out nodes of the node n 00210 * @warning: The returned iterator should be deleted by the caller to prevent memory leaks 00211 * @remark o(1) 00212 */ 00213 //======================================================= 00214 Iterator<node> * getOutNodes(const node n) const; 00215 //======================================================= 00216 /** 00217 * @brief Return the degree of a node 00218 * @remark o(1) 00219 */ 00220 unsigned int deg(const node n) const; 00221 //======================================================= 00222 /** 00223 * @brief Return the out degree of a node 00224 * @remark o(1) 00225 */ 00226 unsigned int outdeg(const node n) const; 00227 //======================================================= 00228 /** 00229 * @brief Return the in degree of a node 00230 * @remark o(1) 00231 */ 00232 unsigned int indeg(const node n) const; 00233 //======================================================= 00234 /** 00235 * @brief Return the number of edges in the graph 00236 * @remark: o(1) 00237 */ 00238 unsigned int numberOfEdges() const; 00239 //======================================================= 00240 /** 00241 * @brief Return the number of nodes in the graph 00242 * @remark: o(1) 00243 */ 00244 unsigned int numberOfNodes() const; 00245 //======================================================= 00246 /** 00247 * @brief Add a new node in the graph and return it 00248 * @warning: That operation modify the array of nodes 00249 * and thus devalidate all iterators on it. 00250 * @remark: o(1) 00251 */ 00252 node addNode(); 00253 //======================================================= 00254 /** 00255 * @brief Delete a node and all its adjacent edges in the graph 00256 * @warning That operation modify the array of nodes and the array of edges 00257 * and thus devalidate all iterators on it. 00258 * @warning That operation modify the array of neighboors of extrmities of edges, thus 00259 * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edges. 00260 * @warning Orders of edges in the extremities of the deleted edges are affected 00261 * @remark: o(1) 00262 */ 00263 void delNode(const node n); 00264 //======================================================= 00265 /** 00266 * @brief Add a new edge between src and tgt and return it 00267 * @warning That operation modify the array of neighboors of extrmities of edges, thus 00268 * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edges. 00269 * @remark o(1) 00270 */ 00271 edge addEdge(const node src, const node tgt); 00272 //======================================================= 00273 /** 00274 * @brief Delete an edge in the graph 00275 * @warning: That operation modify the array of edges 00276 * and thus devalidate all iterators on it. 00277 * @warning That operation modify the array of neighboors of extremities of the edge e, thus 00278 * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edge. 00279 * @warning Orders of edges in the extremities of the deleted edge are affected 00280 * @remark o(1) 00281 */ 00282 void delEdge(const edge e); 00283 //======================================================= 00284 /** 00285 * @brief Delete all adjacent edges (in/out) of a node 00286 * @warning: That operation modify the array of edges 00287 * and thus devalidate all iterators on it. 00288 * @warning That operation modify the array of neighboors of extremities of the edge e, thus 00289 * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edge. 00290 * @warning Orders of edges in the extremities of the deleted edge are affected 00291 * @remark o(deg(V)) 00292 * @todo test 00293 */ 00294 void delEdges(const node n); 00295 //======================================================= 00296 /** 00297 * @brief Delete all edges in the graph 00298 * @warning: That operation modify the array of edges and all arrays of nodes 00299 * and thus devalidate all iterators, only graph nodes iterators are not affected. 00300 * @remark o(E + V) 00301 */ 00302 void delAllEdges(); 00303 //======================================================= 00304 /** 00305 * @brief Delete all nodes in the graph 00306 * @warning: That operation modify the array of edges and all arrays of nodes 00307 * and thus devalidate all iterators. 00308 * @remark o(E + V) 00309 */ 00310 void delAllNodes(); 00311 //======================================================= 00312 /** 00313 * @brief return the first extremity (considered as source if the graph is directed) of an edge 00314 * @remark o(1) 00315 */ 00316 node source(const edge e) const; 00317 //======================================================= 00318 /** 00319 * @brief return the second extremity (considered as target if the graph is directed) of an edge 00320 * @remark o(1) 00321 */ 00322 node target(const edge e) const; 00323 //======================================================= 00324 /** 00325 * @brief return the opposite node of n through edge e 00326 * @remark o(1) 00327 */ 00328 node opposite(const edge e, const node n) const; 00329 //======================================================= 00330 /** 00331 * @brief Reverse an edge e, source become target and target become soure 00332 * @remark o(1) 00333 */ 00334 void reverse(const edge e); 00335 //======================================================= 00336 /** 00337 * @brief change the source of an edge 00338 * @warning That operation modify the array of neighboors of extrmities of edges, thus 00339 * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes. 00340 * @remark o(1) 00341 * \see setEnds 00342 */ 00343 void setSource(const edge e, const node n); 00344 //======================================================= 00345 /** 00346 * @brief change the target of an edge 00347 * @warning That operation modify the array of neighboors of extrmities of edges, thus 00348 * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes. 00349 * @remark o(1) 00350 * \see setEnds 00351 */ 00352 void setTarget(const edge e, const node n); 00353 //======================================================= 00354 /** 00355 * @brief Return the extremities of an edge (src, target) 00356 * @remark o(1) 00357 */ 00358 std::pair<node, node> ends(const edge e) const; 00359 //======================================================= 00360 /** 00361 * @brief Reconnect the edeg e to have the new given extremities 00362 * @warning That operation modify the array of neighboors of extrmities of edges, thus 00363 * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes. 00364 * @remark o(1) 00365 */ 00366 void setEnds(const edge e, const node src, const node tgt); 00367 //======================================================= 00368 /** 00369 * @brief Shuffle the array of graph nodes 00370 * @remark dependant of stl::random_shuffle algorithm (should be o(N)) 00371 */ 00372 void shuffleNodes(); 00373 //======================================================= 00374 /** 00375 * @brief Shuffle the array of graph edges 00376 * @remark dependant of stl::random_shuffle algorithm (should be o(E)) 00377 */ 00378 void shuffleEdges(); 00379 //======================================================= 00380 /** 00381 * @brief Sort all edges according to comparison functor given in parameter 00382 * if stable is true a stable sort algorithm is applied 00383 * Comparison should be an instance of a class wihch implements operator(): 00384 * @remark dependant of stl::sort and stl::stable_sort algorithm (should be o(E log (E))) 00385 * @code 00386 * class Compare { 00387 * //return true if a < b 00388 * bool operator()(const edge a, const edge b); 00389 * }; 00390 * @endcode 00391 * \warning that function is not compatible with the Tulip Graph API 00392 */ 00393 template<typename Compare> 00394 void sortEdges(Compare cmp, bool stable = false) { 00395 if (stable) 00396 stable_sort(_edges.begin(), _edges.end(), cmp); 00397 else 00398 sort(_edges.begin(), _edges.end(), cmp); 00399 00400 //recompute indices of edges 00401 for (unsigned int i = 0; i < _edges.size(); ++i) { 00402 _eData[_edges[i]]._edgesId = i; 00403 } 00404 } 00405 //======================================================= 00406 /** 00407 * @brief Sort all nodes according to comparison functor given in parameter 00408 * if stable is true a stable sort algorithm is applied 00409 * Comparison should be an instance of a class wihch implements operator(): 00410 * @code 00411 * class Compare { 00412 * //return true if a < b 00413 * bool operator()(const node a, const node b); 00414 * }; 00415 * @endcode 00416 * @remark dependant of stl::sort and stl::stable_sort algorithm (should be o(N log (N))) 00417 * \warning that function is not compatible with the Tulip Graph API 00418 */ 00419 template<typename Compare > 00420 void sortNodes(Compare cmp, bool stable = false) { 00421 if (stable) 00422 stable_sort(_nodes.begin(), _nodes.end(), cmp); 00423 else 00424 sort(_nodes.begin(), _nodes.end(), cmp); 00425 00426 //recompute indices of edges 00427 for (unsigned int i = 0; i < _nodes.size(); ++i) { 00428 _nData[_nodes[i]]._nodesId = i; 00429 } 00430 } 00431 //======================================================= 00432 /** 00433 * @brief return the position of an edge in the array of edges. 00434 * \warning that function is not compatible with the Tulip Graph API 00435 * @remark o(1) 00436 */ 00437 unsigned int edgePos(const edge e) const; 00438 //======================================================= 00439 /** 00440 * @brief return the position of a node in the array of nodes. 00441 * \warning that function is not compatible with the Tulip Graph API 00442 * @remark o(1) 00443 */ 00444 unsigned int nodePos(const node n) const; 00445 //======================================================= 00446 /** 00447 * @brief Swap two nodes in the array of graph nodes 00448 * @remark o(1) 00449 * \warning that function is not compatible with the Tulip Graph API 00450 */ 00451 void swap(const node a, const node b); 00452 //======================================================= 00453 /** 00454 * @brief Swap two edges in the array of graph edge 00455 * @remark o(1) 00456 * \warning that function is not compatible with the Tulip Graph API 00457 */ 00458 void swap(const edge a, const edge b); 00459 //======================================================= 00460 /** 00461 * @brief Create a new node array of type TYPE 00462 * NodesAttr can be copied in constant time it is just a pointer 00463 * NodesAttr is not a smart pointer it must be deleted with freeNodesAttribute 00464 * @remark o(log(number of arrays) + new of a vector<TYPE> of size N) 00465 * \warning that function is not compatible with the Tulip Graph API 00466 */ 00467 template<typename TYPE> 00468 void alloc(NodeProperty<TYPE> &prop) { 00469 ValArray<TYPE> *array = new ValArray<TYPE>(_nodes.size() + _freeNodes.size(), _nodes.capacity()); 00470 _nodeArrays.insert(array); 00471 prop = NodeProperty<TYPE>(array, this); 00472 } 00473 //======================================================= 00474 /** 00475 * @brief Delete an Array from the set of node arrays 00476 * @warning all copy of the ValArray are no more valid (serious bug if they are used after) 00477 * @remark o(log(number of arrays) + free of a vector<TYPE> of size N) 00478 * \warning that function is not compatible with the Tulip Graph API 00479 */ 00480 template<typename TYPE> 00481 void free(NodeProperty<TYPE> array) { 00482 assert(_nodeArrays.find(array._array) != _nodeArrays.end()); 00483 delete array._array; 00484 _nodeArrays.erase(array._array); 00485 } 00486 //======================================================= 00487 /** 00488 * @brief Create a new edge array of type TYPE 00489 * EdgesAttr can be copied in constant time it is just a pointer 00490 * EdgesAttr is not a smart pointer it must be deleted with freeEdgesAttribute 00491 * @remark o(log(number of node arrays) + new of a vector<TYPE> of size E) 00492 * \warning that function is not compatible with the Tulip Graph API 00493 */ 00494 template<typename TYPE> 00495 void alloc(EdgeProperty<TYPE> &prop) { 00496 ValArray<TYPE> *array = new ValArray<TYPE>(_edges.size() + _freeEdges.size(), _edges.capacity()); 00497 _edgeArrays.insert(array); 00498 prop = EdgeProperty<TYPE>(array, this); 00499 } 00500 //======================================================= 00501 /** 00502 * @brief Delete an Array from the set of edge arrays 00503 * @warning all copy of the ValArray are no more valid (serious bug if they are used after) 00504 * @remark o(log(number of edge arrays) + free of a vector<TYPE> of size E) 00505 * \warning that function is not compatible with the Tulip Graph API 00506 */ 00507 template<typename TYPE> 00508 void free(EdgeProperty<TYPE> array) { 00509 assert(_edgeArrays.find(array._array) != _edgeArrays.end()); 00510 delete array._array; 00511 _edgeArrays.erase(array._array); 00512 } 00513 //======================================================= 00514 /** 00515 * @brief Return a const reference on the vector of adjacent nodes of n 00516 * 00517 * It is the fastest way to access to node adjacency, Iterators are 25% slower. 00518 * \warning code that use that function won't be compatible with Tulip Graph API 00519 * 00520 * @remark o(1) 00521 * \see getInOutNodes 00522 * \see getInNodes 00523 * \see getOutNodes 00524 */ 00525 const std::vector<node>& adj(const node n) const; 00526 //======================================================= 00527 /** 00528 * @brief Return a const reference on the vector of adjacent edges of n 00529 * 00530 * It is the fastest way to access to edge adjacency, Iterators are 25% slower. 00531 * \warning code that use that function won't be compatible with Tulip Graph API 00532 * 00533 * @remark o(1) 00534 * \see getInOutEdges 00535 * \see getInEdges 00536 * \see getOutEdges 00537 */ 00538 const std::vector<edge>& star(const node n) const; 00539 //======================================================= 00540 /** 00541 * @brief Return a const reference on the vector of nodes of the graph 00542 * It is the fastest way to access to edge adjacency, Iterators are 25% slower. 00543 * \warning code that use that function won't be compatible with Tulip Graph API 00544 * @remark o(1) 00545 */ 00546 const std::vector<node>& nodes() const; 00547 //======================================================= 00548 /** 00549 * @brief Return a const reference on the vector of edges of the graph 00550 * It is the fastest way to access to edge adjacency, Iterators are 25% slower. 00551 * \warning code that use that function won't be compatible with Tulip Graph API 00552 * @remark o(1) 00553 */ 00554 const std::vector<edge>& edges() const; 00555 //======================================================= 00556 #ifndef NDEBUG 00557 /** 00558 * these two function are used internally to insure that property has been allocated in debug mode 00559 * @warning never used these function directly even in debug mode !!! 00560 */ 00561 template<typename TYPE> 00562 bool isNodeAttr(ValArray<TYPE> *array) { 00563 return (_nodeArrays.find(array) != _nodeArrays.end()); 00564 } 00565 template<typename TYPE> 00566 bool isEdgeAttr(ValArray<TYPE> *array) { 00567 return (_edgeArrays.find(array) != _edgeArrays.end()); 00568 } 00569 #endif 00570 //============================================================= 00571 /** 00572 * output the graph in a very simple way for debugging 00573 */ 00574 void dump() const; 00575 //============================================================= 00576 /** 00577 * internal function to test the integrity of the graph 00578 */ 00579 void integrityTest(); 00580 00581 private: 00582 00583 struct _iNodes { 00584 _iNodes(unsigned int id = UINT_MAX): _nodesId(id), _outdeg(0) { 00585 } 00586 00587 void clear() { 00588 _outdeg = 0; 00589 _adjt.resize(0); 00590 _adjn.resize(0); 00591 _adje.resize(0); 00592 } 00593 00594 void addEdge(bool t, node n, edge e) { 00595 _adjt.push_back(t); 00596 _adjn.push_back(n); 00597 _adje.push_back(e); 00598 } 00599 00600 unsigned int _nodesId; /** index of a node in the _nodes vector*/ 00601 unsigned int _outdeg; /** out degree of nodes */ 00602 std::vector<bool> _adjt; /** orientation of the edge, used to separate in and out edges/nodes */ 00603 std::vector<node> _adjn; /** inout nodes*/ 00604 std::vector<edge> _adje; /** inout edges*/ 00605 }; 00606 00607 struct _iEdges { 00608 unsigned int _edgesId; /** index of a node in the _edges vector*/ 00609 std::pair<node, node> _edgeExtremities; /** source and target of an edge */ 00610 std::pair<unsigned int, unsigned int> _edgeExtremitiesPos; /** source and target of an edge */ 00611 }; 00612 00613 std::vector<_iNodes> _nData; /** internal storage of nodes */ 00614 std::vector<_iEdges> _eData; /** internal storage of edges */ 00615 00616 std::vector< node > _nodes; /** vector of nodes element of the graph */ 00617 std::vector< edge > _edges; /** vector of edges element of the graph */ 00618 00619 std::vector<node> _freeNodes; /** vector of nodes that has been deleted and that can be reused */ 00620 std::vector<edge> _freeEdges; /** vector of edges that has been deleted and that can be reused */ 00621 00622 std::set<ValArrayInterface *> _nodeArrays; /** set of all node properties allocated on that graph */ 00623 std::set<ValArrayInterface *> _edgeArrays; /** set of all edge properties allocated on that graph */ 00624 00625 //======================================================= 00626 /** 00627 * internal function to break the program and output debug information during 00628 * integrity test. 00629 * @TODO hide that function in the .cpp file 00630 */ 00631 void testCond(std::string str, bool b); 00632 //======================================================= 00633 /** 00634 * internal function to adjust size of node properties when graph is modified 00635 */ 00636 void addNodeToArray(node n); 00637 //======================================================= 00638 /** 00639 * internal function to adjust size of edge properties when graph is modified 00640 */ 00641 void addEdgeToArray(edge e); 00642 //======================================================= 00643 /** 00644 * internal function to remove an edge 00645 */ 00646 void removeEdge(edge e); 00647 //======================================================= 00648 /** 00649 * Internal function to remove the edge e in the adjacency list of n 00650 */ 00651 void moveEdge(node n, unsigned int a, unsigned int b); 00652 /** 00653 * Internal function tp remove the edge e in the adjacency list of n 00654 */ 00655 void partialDelEdge(node n, edge e); 00656 //======================================================= 00657 }; 00658 00659 00660 #ifndef NDEBUG //these two function are used to insure that property has been allocated in debug mode 00661 template <typename TYPE> 00662 bool NodeProperty<TYPE>::isValid() const { 00663 if (this->_graph == 0) return false; 00664 00665 if (this->_array == 0) return false; 00666 00667 return this->_graph->isNodeAttr(this->_array); 00668 } 00669 00670 template <typename TYPE> 00671 bool EdgeProperty<TYPE>::isValid() const { 00672 if (this->_graph == 0) return false; 00673 00674 if (this->_array == 0) return false; 00675 00676 return this->_graph->isEdgeAttr(this->_array); 00677 } 00678 #endif 00679 } 00680 #endif // VECTORGRAPH_H 00681 ///@endcond