Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/vectorgraph.h
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
 All Classes Files Functions Variables Enumerations Enumerator Properties