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