![]() |
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 DOXYGEN_NOTFOR_DEVEL 00023 #ifndef Tulip_PlanarConMap_H 00024 #define Tulip_PlanarConMap_H 00025 #include <vector> 00026 #include <tulip/tuliphash.h> 00027 #include <tulip/Face.h> 00028 #include <tulip/GraphDecorator.h> 00029 00030 namespace tlp { 00031 00032 struct Face; 00033 class IdManager; 00034 00035 /** 00036 * \brief interface for a topological graph 00037 */ 00038 /** 00039 * The class PlanarConMap is an interface for map in the Tulip Library. This only 00040 * considers connected planar map, moreover the graph must be simple. 00041 * After, its initialization, if modifications, such as additions or deletions of 00042 * edges or/and nodes, are made on the supergraph, the map will not be 00043 * valid any more. In this case, one can calls update() function to update the map 00044 * but it completely compute the map. 00045 */ 00046 00047 00048 class TLP_SCOPE PlanarConMap : public GraphDecorator { 00049 00050 /* for test classes */ 00051 friend class FaceIteratorTest; 00052 friend class PlanarConMapTest; 00053 00054 00055 friend class FaceIterator; 00056 friend class FaceAdjIterator; 00057 friend class NodeFaceIterator; 00058 friend class EdgeFaceIterator; 00059 00060 friend TLP_SCOPE PlanarConMap* computePlanarConMap(Graph* graph); 00061 00062 protected: 00063 /** Constructor 00064 * Warning, the graph must be planar, connected and simple. 00065 */ 00066 PlanarConMap(Graph* s); 00067 00068 00069 public: 00070 00071 //Destructor. 00072 virtual ~PlanarConMap(); 00073 00074 /** 00075 * Remove all nodes, edges, faces and subgraphs of the map 00076 */ 00077 void clear(); 00078 00079 /** Update the map : this recompute completely the map. 00080 * To do when an operation on one of the super-graphs of the map has been done. 00081 */ 00082 void update(); 00083 00084 //============================================================================== 00085 // Modification of the graph structure 00086 //============================================================================== 00087 /** 00088 * Add and return an edge between two node u and v in the map. This edge is added in 00089 * face f, and e1 and e2 will be predecessor of respectively v and w in the 00090 * cycles around v and w. The new face is put into new_face. 00091 * This edge is also added in all the super-graph of the map to maintain 00092 * the sub-graph relation between graphs. 00093 * Warning, the edge must be element of the graph hierarchy, thus it must be 00094 * element of the root graph. 00095 * Warning : One can't add an existing edge to the root graph 00096 */ 00097 edge addEdgeMap(const node v, const node w, Face f, const edge e1, const edge e2, Face new_face= Face()); 00098 00099 /** Split the face by adding an edge between the two nodes and return the 00100 * new face. Possibility to specify which will be the new face, by giving a 00101 * node that will be contained into the new face. 00102 * Warning, the edge must be element of the graph hierarchy, thus it must be 00103 * element of the root graph. 00104 */ 00105 Face splitFace(Face, const node, const node, node = node()); 00106 00107 /** Split the face by adding the edge and return the new face. 00108 * Warning, the edge must be element of the graph hierarchy, thus it must be 00109 * element of the root graph. 00110 */ 00111 Face splitFace(Face, const edge); 00112 00113 /** Merge two faces into one and put the new computed face into f. 00114 * Warning, the edge must be element of the graph hierarchy, thus it must be 00115 * element of the root graph. 00116 */ 00117 void mergeFaces(Face f, Face g); 00118 00119 00120 //================================================================================ 00121 //Iterators on the graph structure. 00122 //================================================================================ 00123 00124 ///Return an iterator on the faces. 00125 Iterator<Face>* getFaces(); 00126 ///Return an iterator on the adjacent faces of a node. 00127 Iterator<Face>* getFacesAdj(const node); 00128 ///Return an iterator on the nodes of a face. 00129 Iterator<node>* getFaceNodes(const Face); 00130 ///Return an iterator on the edges of a face. 00131 Iterator<edge>* getFaceEdges(const Face); 00132 00133 //================================================================================ 00134 // Graph, nodes and edges information about the graph stucture 00135 //================================================================================ 00136 ///Return the edge which is the succcessor of an edge in the cycle of a node. 00137 edge succCycleEdge(const edge, const node) const; 00138 ///Return the edge which is the predecessor of an edge in the cycle of a node. 00139 edge predCycleEdge(const edge, const node) const; 00140 ///Return the node which is the succcessor of a node in the cycle of a node. 00141 node succCycleNode(const node, const node) const; 00142 ///Return the node which is the predecessor of a node in the cycle of a node. 00143 node predCycleNode(const node, const node) const; 00144 00145 ///Return the number of faces. 00146 unsigned int nbFaces(); 00147 ///Return the number of nodes contained into a face. 00148 unsigned int nbFacesNodes(const Face); 00149 ///Return the number of edges contained into a face. 00150 unsigned int nbFacesEdges(const Face); 00151 00152 ///Return true if the face contains the node. 00153 bool containNode(const Face, const node) ; 00154 ///Return true if the face contains the edge. 00155 bool containEdge(const Face, const edge); 00156 /** Returns the face containing the two nodes in this order 00157 * and the edge between this two nodes. 00158 * Warning, the edge must exists in the map. 00159 */ 00160 Face getFaceContaining(const node, const node); 00161 /// Return a face containing the two nodes if it exists and Face() otherwise 00162 Face sameFace(const node, const node); 00163 00164 00165 private: 00166 00167 /** Compute faces and initialize all variables. 00168 */ 00169 void computeFaces(); 00170 /** 00171 * Delete the edge in the map. The new face can be put into a specified face, 00172 * otherwise, one of the two adjacent faces will be updated. 00173 * Warning, the edge must not be an isthm of the map, otherwize the map will be deconnected 00174 * and so won't be valid any more. 00175 */ 00176 void delEdgeMap(edge, Face = Face()); 00177 00178 typedef TLP_HASH_MAP<Face , std::vector<edge> > faceMap; 00179 typedef faceMap::value_type faceMapEntry; 00180 typedef TLP_HASH_MAP<edge, std::vector<Face> > edgeMap; 00181 typedef edgeMap::value_type edgeMapEntry; 00182 typedef TLP_HASH_MAP<node, std::vector<Face> > nodeMap; 00183 typedef nodeMap::value_type nodeMapEntry; 00184 00185 /** storage of faces */ 00186 faceMap facesEdges; 00187 edgeMap edgesFaces; 00188 nodeMap nodesFaces; 00189 mutable std::vector<Face > faces; 00190 00191 IdManager *faceId; 00192 00193 }; 00194 00195 // Compute a PlanarConMap from a graph. 00196 // return a NULL value if the graph is not connected 00197 TLP_SCOPE PlanarConMap* computePlanarConMap(Graph* graph); 00198 00199 } 00200 00201 ///Print the map (only faces, nodes and edges) in ostream, in the tulip format 00202 TLP_SCOPE std::ostream& operator<< (std::ostream &, tlp::PlanarConMap *); 00203 00204 #endif 00205 #endif //DOXYGEN_NOTFOR_DEVEL 00206 ///@endcond