![]() |
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 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