Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/GraphStorage.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 GRAPHSTORAGE_H
00023 #define GRAPHSTORAGE_H
00024 #include <cassert>
00025 #include <vector>
00026 
00027 #include <tulip/Node.h>
00028 #include <tulip/Edge.h>
00029 #include <tulip/IdManager.h>
00030 #include <tulip/SimpleVector.h>
00031 #include <tulip/MutableContainer.h>
00032 
00033 namespace tlp {
00034 
00035 //===========================================
00036 /**
00037   * @class GraphStorageIdsMemento
00038   * @brief that class provides a simple interface
00039   * to save the state of the ids manage by the GraphStorage class
00040   */
00041 class GraphStorageIdsMemento {
00042 public:
00043   virtual ~GraphStorageIdsMemento() {}
00044 };
00045 //===========================================
00046 /**
00047   * @class GraphStorage
00048   * @brief That class provide a simple implementation
00049   * for the storage of graph  elts (nodes edges)
00050   */
00051 class GraphStorage {
00052 public:
00053   //=======================================================
00054   void clear();
00055   //=======================================================
00056   GraphStorage();
00057   //=======================================================
00058   ~GraphStorage();
00059   //=======================================================
00060   /**
00061    * @brief Return true if n belongs to the graph
00062    */
00063   bool isElement(const node n) const;
00064   //=======================================================
00065   /**
00066    * @brief Return true if e belongs to the graph
00067    */
00068   bool isElement(const edge e) const;
00069   //=======================================================
00070   /**
00071    * @brief Enables to reserve memory for nbNodes
00072    * Reserving memory before to addNode enable to reduce the number of vector resizing and then
00073    * to speed up significantly construction of graphs.
00074    */
00075   void reserveNodes(size_t nb);
00076   //=======================================================
00077   /**
00078    * @brief Enables to reserve memory for nbEdges
00079    * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
00080    * to speed up significantly construction of graphs.
00081     */
00082   void reserveEdges(size_t nb);
00083   //=======================================================
00084   /**
00085    * @brief Enables to reserve memory for adjacency nodes
00086    * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
00087    * to speed up significantly construction of graphs.
00088    */
00089   void reserveAdj(node n, size_t nb);
00090   //=======================================================
00091   /**
00092    * @brief Enables to reserve memory for adjacency nodes
00093    * Reserving memory before to addEdge enable to reduce the number of vector resizing and then
00094    * to speed up significantly construction of graphs.
00095    */
00096   void reserveAdj(size_t nb);
00097   //=======================================================
00098   /**
00099    * @brief restore adjacency edges of a given node
00100    */
00101   void restoreAdj(node n, const std::vector<edge>& edges);
00102   //=======================================================
00103   /**
00104    * @brief Return the first node of graph
00105    */
00106   node getOneNode() const;
00107   //=======================================================
00108   /**
00109    * @brief Return a Tulip Iterator on nodes of the graph
00110    * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
00111    * @complexity: o(1)
00112    */
00113   Iterator<node>* getNodes() const;
00114   //=======================================================
00115   /**
00116    * @brief Return the current state of the ids management
00117    * must be deleted by the caller
00118    * this can be used for push/pop
00119    */
00120   const GraphStorageIdsMemento* getIdsMemento();
00121   //=======================================================
00122   /**
00123    * @brief  restore a state of the ids management
00124    */
00125   void restoreIdsMemento(const GraphStorageIdsMemento*);
00126   //=======================================================
00127   /**
00128    * @brief Return a Tulip Iterator on edges of the graph
00129    * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
00130    */
00131   Iterator<edge>* getEdges() const;
00132   //=======================================================
00133   /**
00134    * @brief Return a Tulip Iterator on adjacent edges of the node n
00135    * @warning: be careful that loops appear twice
00136    * @warning: The returned iterator should be deleted by the caller to prevent memory leaks
00137    */
00138   Iterator<edge>* getInOutEdges(node n) const;
00139   //=======================================================
00140   /**
00141    * @brief get adjacency edges of a given node
00142    */
00143   void getInOutEdges(node n, std::vector<edge>& edges,
00144                      bool loopsOnlyOnce = false) const;
00145   //=======================================================
00146   /**
00147    * @brief Return a Tulip Iterator on out edges of the node n
00148    * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
00149    */
00150   Iterator<edge>* getOutEdges(node n) const;
00151   //=======================================================
00152   /**
00153    * @brief Return a Tulip Iterator on in edges of the node n
00154    * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
00155    */
00156   Iterator<edge>* getInEdges(node n) const;
00157   //=======================================================
00158   /**
00159    * @brief Returns if edges exist between two nodes
00160    * @param source The source of the hypothetical edges.
00161    * @param target The target of the hypothetical edges.
00162    * @param directed When set to false edges from target to source are also considered
00163    * @param edges The vector of edges to fill up with the edges found
00164    * @param onlyFirst If true only the first edge found will be returned
00165    * @return true if an edge has been bound
00166    */
00167   bool getEdges(const node source, const node target, bool directed,
00168                 std::vector<edge>& edges, bool onlyFirst = false) const;
00169 
00170   //=======================================================
00171   /**
00172    * @brief Return a Tulip Iterator on adjacent nodes of the node n
00173    * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
00174    */
00175   Iterator<node>* getInOutNodes(node n) const;
00176   //=======================================================
00177   /**
00178    * @brief Return a Tulip Iterator on in nodes of the node n
00179    * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
00180    */
00181   Iterator<node>* getInNodes(node n) const;
00182   //=======================================================
00183   /**
00184    * @brief Return a Tulip Iterator on out nodes of the node n
00185    * @warning: The returned iterator must be deleted by the caller to prevent memory leaks
00186    */
00187   Iterator<node>* getOutNodes(node n) const;
00188   //=======================================================
00189   /**
00190    * @brief Return the degree of a node
00191    */
00192   unsigned int deg(node n) const;
00193   //=======================================================
00194   /**
00195    * @brief Return the out degree of a node
00196    */
00197   unsigned int outdeg(node n) const;
00198   //=======================================================
00199   /**
00200    * @brief Return the in degree of a node
00201    */
00202   unsigned int indeg(node n) const;
00203   //=======================================================
00204   /**
00205    * @brief Return the number of edges in the graph
00206    */
00207   unsigned int numberOfEdges() const;
00208   //=======================================================
00209   /**
00210    * @brief Return the number of nodes in the graph
00211    */
00212   unsigned int numberOfNodes() const;
00213   //=======================================================
00214   /**
00215    * @brief Return the extremities of an edge (src, target)
00216    */
00217   const std::pair<node, node>& ends(const edge e) const;
00218   //=======================================================
00219   /**
00220    * @brief return the first extremity (considered as source if the graph is directed) of an edge
00221    */
00222   node source(edge e) const;
00223   //=======================================================
00224   /**
00225    * @brief return the second extremity (considered as target if the graph is directed) of an edge
00226    */
00227   node target(edge e) const;
00228   //=======================================================
00229   /**
00230    * @brief return the opposite node of n through edge e
00231    */
00232   node opposite(edge e, node n) const;
00233   //=======================================================
00234   /**
00235    * @brief Reconnect the edge e to have the new given ends
00236    * @warning That operation modify the array of neighboors of extrmities of edges, thus
00237    * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
00238    */
00239   void setEnds(const edge e, const node newSrc, const node newTgt);
00240   //=======================================================
00241   /**
00242    * @brief change the source of an edge
00243    * @warning That operation modify the array of neighboors of extrmities of edges, thus
00244    * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
00245    * \see setEnds
00246    */
00247   void setSource(const edge e, const node n);
00248   //=======================================================
00249   /**
00250    * @brief change the target of an edge
00251    * @warning That operation modify the array of neighboors of extrmities of edges, thus
00252    * it devalidates iterators on adjacency for the nodes at the extremities of the modified edges and nodes.
00253    * \see setEnds
00254    */
00255   void setTarget(const edge e, const node n);
00256   //=======================================================
00257   /**
00258    * @brief Reverse an edge e, source become target and target become soure
00259    */
00260   void reverse(const edge e);
00261   //=======================================================
00262   /**
00263    * \brief Set the ordering of edges around n according to their order in v.
00264    */
00265   void setEdgeOrder(const node n, const std::vector<edge> &v );
00266   //=======================================================
00267   /**
00268    * \brief swap to edge in the ordered adjacency vector
00269    * \warning the two edges must be element of star(v)
00270    */
00271   void swapEdgeOrder(const node n, const edge e1, const edge e2);
00272   //=======================================================
00273   /**
00274    * @brief Add the given node in the structure and return it
00275    * @warning: That operation modify the array of nodes
00276    * and thus devalidate all iterators on it.
00277    * @complexity: o(1)
00278    */
00279   node addNode(node n);
00280   //=======================================================
00281   /**
00282    * @brief Add a new node in the structure and return it
00283    * @warning: That operation modify the array of nodes
00284    * and thus devalidate all iterators on it.
00285    * @complexity: o(1)
00286    */
00287   node addNode();
00288   //=======================================================
00289   /**
00290    * @brief Add nb new nodes in the structure and returns them
00291    * in the addedNodes vector
00292    * @warning: That operation modify the array of nodes
00293    * and thus devalidate all iterators on it. The addedNodes vector
00294    * is cleared before adding nodes
00295    * @complexity: o(1)
00296    */
00297   void addNodes(unsigned int nb, std::vector<node>& addedNodes);
00298   //=======================================================
00299   /**
00300    * @brief Add the given nodes in the structure
00301    * @warning: That operation modify the array of nodes
00302    * and thus devalidate all iterators on it.
00303    * @complexity: o(1)
00304    */
00305   void restoreNodes(const std::vector<node>& addedNodes);
00306   //=======================================================
00307   /**
00308    * @brief remove a node from the nodes structure only
00309    * @warning That operation modify the array of nodes
00310    * and thus devalidate all iterators on it.
00311    * @complexity: o(1)
00312    */
00313   void removeFromNodes(const node n);
00314   //=======================================================
00315   /**
00316    * @brief Delete a node and all its adjacent edges in the graph
00317    * @warning That operation modify the array of nodes and the array of edges
00318    * and thus devalidate all iterators on it.
00319    * @warning That operation modify the array of neighboors of extrmities of edges, thus
00320    * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edges.
00321    * @warning Orders of edges in the extremities of the deleted edges are affected
00322    * @complexity: o(1)
00323    */
00324   void delNode(node n);
00325   //=======================================================
00326   /**
00327    * @brief Add the given edge between src and tgt and return it
00328    * the last argument indicates if the edge has to be added
00329    * in the adjacency edges of its two ends
00330    * @warning That operation modify the array of edges and
00331    * the adjacency edges of its ends thus any iterators existing for
00332    * these structures will be devalidated.
00333    */
00334   edge addEdge(const node src, const node tgt,
00335                const edge e, bool updateEndsEdges);
00336   //=======================================================
00337   /**
00338    * @brief Add a new edge between src and tgt and return it
00339    * @warning That operation modify the array of edges and
00340    * the adjacency edges of its ends thus any iterators existing for
00341    * these structures will be devalidated.
00342    */
00343   edge addEdge(node src, node tgt);
00344   //=======================================================
00345   /**
00346    * @brief Add edges in the structure and returns them
00347    * in the addedEdges vector
00348    * @warning: That operation modify the array of edges and
00349    * the adjacency edges of its ends thus any iterators existing for
00350    * these structures will be devalidated.
00351    */
00352   void addEdges(const std::vector<std::pair<node, node> >& edges,
00353                 std::vector<edge>& addedEdges);
00354   //=======================================================
00355   /**
00356    * @brief restore edges in the structure and returns them
00357    * in the addedEdges vector
00358    * @warning: That operation modify the array of edges
00359    * thus any iterators existing for
00360    * these structures will be devalidated.
00361    */
00362   void restoreEdges(const std::vector<edge>& edgesToRestore,
00363                     const std::vector<std::pair<node, node> >& ends);
00364 //=======================================================
00365   /**
00366    * @brief Delete an edge in the graph
00367    * @warning: That operation modify the array of edges
00368    * and thus devalidate all iterators on it.
00369    * @warning That operation modify the array of neighboors of extremities of the edge e, thus
00370    * it devalidates iterators on adjacency for the nodes at the extremities od the deleted edge.
00371    * @warning Orders of edges in the extremities of the deleted edge are affected
00372    */
00373   void delEdge(edge e);
00374   //=======================================================
00375   /**
00376    * @brief Delete all edges in the graph
00377    * @warning: That operation modify the array of edges and all arrays of nodes
00378    * and thus devalidate all iterators, only graph nodes iterators are not affected.
00379    */
00380   void delAllEdges();
00381   //=======================================================
00382   /**
00383    * @brief Delete all nodes in the graph
00384    * @warning: That operation modify the array of edges and all arrays of nodes
00385    * and thus devalidate all iterators.
00386    */
00387   void delAllNodes();
00388   //=======================================================
00389 private :
00390   // specific types
00391   typedef SimpleVector<edge> EdgeVector;
00392 
00393   struct EdgeContainer {
00394     EdgeVector edges;
00395     unsigned int outDegree;
00396 
00397     EdgeContainer():outDegree(0) {}
00398   };
00399   typedef std::vector<EdgeContainer> Nodes;
00400   typedef std::vector<std::pair< node , node > > Edges;
00401 
00402   // data members
00403   mutable Edges edges;
00404   mutable Nodes nodes;
00405   IdManager nodeIds;
00406   IdManager edgeIds;
00407   unsigned int nbNodes;
00408   unsigned int nbEdges;
00409 
00410   // member functions below do not belong to the public API
00411   // they are just needed by the current implementation
00412   //=======================================================
00413   /**
00414    * @brief remove an edge from an EdgeContainer
00415    * @warning That operation modify the EdgeContainer
00416    * and thus devalidate all iterators on it.
00417    */
00418   static void removeFromEdgeContainer(EdgeContainer &c, const edge e);
00419   //=======================================================
00420   /**
00421    * @brief remove an edge from the edges structure
00422    * and from the EdgeContainer of its ends
00423    * except for the end node in argument if it is valid
00424    * @warning That operation modify the array of edges
00425    * and thus devalidate all iterators on it.
00426    */
00427   void removeFromEdges(const edge e, node end = node());
00428 };
00429 }
00430 #endif // GRAPHSTORAGE_H
00431 ///@endcond
 All Classes Files Functions Variables Enumerations Enumerator Properties