Tulip  4.1.0
Better Visualization Through Research
 All Classes Files Functions Variables Enumerations Enumerator Properties Groups Pages
PlanarConMap.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux 1 and Inria Bordeaux - Sud Ouest
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 
22 #ifndef DOXYGEN_NOTFOR_DEVEL
23 #ifndef Tulip_PlanarConMap_H
24 #define Tulip_PlanarConMap_H
25 #include <vector>
26 #include <tulip/tuliphash.h>
27 #include <tulip/Face.h>
28 #include <tulip/GraphDecorator.h>
29 
30 namespace tlp {
31 
32 struct Face;
33 class IdManager;
34 
35 /**
36  * \brief interface for a topological graph
37  */
38 /**
39  * The class PlanarConMap is an interface for map in the Tulip Library. This only
40  * considers connected planar map, moreover the graph must be simple.
41  * After, its initialization, if modifications, such as additions or deletions of
42  * edges or/and nodes, are made on the supergraph, the map will not be
43  * valid any more. In this case, one can calls update() function to update the map
44  * but it completely compute the map.
45  */
46 
47 
48 class TLP_SCOPE PlanarConMap : public GraphDecorator {
49 
50  /* for test classes */
51  friend class FaceIteratorTest;
52  friend class PlanarConMapTest;
53 
54 
55  friend class FaceIterator;
56  friend class FaceAdjIterator;
57  friend class NodeFaceIterator;
58  friend class EdgeFaceIterator;
59 
60  friend TLP_SCOPE PlanarConMap* computePlanarConMap(Graph* graph);
61 
62 protected:
63  /** Constructor
64  * Warning, the graph must be planar, connected and simple.
65  */
66  PlanarConMap(Graph* s);
67 
68 
69 public:
70 
71  //Destructor.
72  virtual ~PlanarConMap();
73 
74  /**
75  * Remove all nodes, edges, faces and subgraphs of the map
76  */
77  void clear();
78 
79  /** Update the map : this recompute completely the map.
80  * To do when an operation on one of the super-graphs of the map has been done.
81  */
82  void update();
83 
84  //==============================================================================
85  // Modification of the graph structure
86  //==============================================================================
87  /**
88  * Add and return an edge between two node u and v in the map. This edge is added in
89  * face f, and e1 and e2 will be predecessor of respectively v and w in the
90  * cycles around v and w. The new face is put into new_face.
91  * This edge is also added in all the super-graph of the map to maintain
92  * the sub-graph relation between graphs.
93  * Warning, the edge must be element of the graph hierarchy, thus it must be
94  * element of the root graph.
95  * Warning : One can't add an existing edge to the root graph
96  */
97  edge addEdgeMap(const node v, const node w, Face f, const edge e1, const edge e2, Face new_face= Face());
98 
99  /** Split the face by adding an edge between the two nodes and return the
100  * new face. Possibility to specify which will be the new face, by giving a
101  * node that will be contained into the new face.
102  * Warning, the edge must be element of the graph hierarchy, thus it must be
103  * element of the root graph.
104  */
105  Face splitFace(Face, const node, const node, node = node());
106 
107  /** Split the face by adding the edge and return the new face.
108  * Warning, the edge must be element of the graph hierarchy, thus it must be
109  * element of the root graph.
110  */
111  Face splitFace(Face, const edge);
112 
113  /** Merge two faces into one and put the new computed face into f.
114  * Warning, the edge must be element of the graph hierarchy, thus it must be
115  * element of the root graph.
116  */
117  void mergeFaces(Face f, Face g);
118 
119 
120  //================================================================================
121  //Iterators on the graph structure.
122  //================================================================================
123 
124  ///Return an iterator on the faces.
125  Iterator<Face>* getFaces();
126  ///Return an iterator on the adjacent faces of a node.
127  Iterator<Face>* getFacesAdj(const node);
128  ///Return an iterator on the nodes of a face.
129  Iterator<node>* getFaceNodes(const Face);
130  ///Return an iterator on the edges of a face.
131  Iterator<edge>* getFaceEdges(const Face);
132 
133  //================================================================================
134  // Graph, nodes and edges informations about the graph stucture
135  //================================================================================
136  ///Return the edge which is the succcessor of an edge in the cycle of a node.
137  edge succCycleEdge(const edge, const node) const;
138  ///Return the edge which is the predecessor of an edge in the cycle of a node.
139  edge predCycleEdge(const edge, const node) const;
140  ///Return the node which is the succcessor of a node in the cycle of a node.
141  node succCycleNode(const node, const node) const;
142  ///Return the node which is the predecessor of a node in the cycle of a node.
143  node predCycleNode(const node, const node) const;
144 
145  ///Return the number of faces.
146  unsigned int nbFaces();
147  ///Return the number of nodes contained into a face.
148  unsigned int nbFacesNodes(const Face);
149  ///Return the number of edges contained into a face.
150  unsigned int nbFacesEdges(const Face);
151 
152  ///Return true if the face contains the node.
153  bool containNode(const Face, const node) ;
154  ///Return true if the face contains the edge.
155  bool containEdge(const Face, const edge);
156  /** Returns the face containing the two nodes in this order
157  * and the edge between this two nodes.
158  * Warning, the edge must exists in the map.
159  */
160  Face getFaceContaining(const node, const node);
161  /// Return a face containing the two nodes if it exists and Face() otherwise
162  Face sameFace(const node, const node);
163 
164 
165 private:
166 
167  /** Compute faces and initialize all variables.
168  */
169  void computeFaces();
170  /**
171  * Delete the edge in the map. The new face can be put into a specified face,
172  * otherwise, one of the two adjacent faces will be updated.
173  * Warning, the edge must not be an isthm of the map, otherwize the map will be deconnected
174  * and so won't be valid any more.
175  */
176  void delEdgeMap(edge, Face = Face());
177 
178  typedef TLP_HASH_MAP<Face , std::vector<edge> > faceMap;
179  typedef faceMap::value_type faceMapEntry;
180  typedef TLP_HASH_MAP<edge, std::vector<Face> > edgeMap;
181  typedef edgeMap::value_type edgeMapEntry;
182  typedef TLP_HASH_MAP<node, std::vector<Face> > nodeMap;
183  typedef nodeMap::value_type nodeMapEntry;
184 
185  /** storage of faces */
186  faceMap facesEdges;
187  edgeMap edgesFaces;
188  nodeMap nodesFaces;
189  mutable std::vector<Face > faces;
190 
191  IdManager *faceId;
192 
193 };
194 
195 // Compute a PlanarConMap from a graph.
196 // return a NULL value if the graph is not connected
197 TLP_SCOPE PlanarConMap* computePlanarConMap(Graph* graph);
198 
199 }
200 
201 ///Print the map (only faces, nodes and edges) in ostream, in the tulip format
202 TLP_SCOPE std::ostream& operator<< (std::ostream &, tlp::PlanarConMap *);
203 
204 #endif
205 #endif //DOXYGEN_NOTFOR_DEVEL
206 ///@endcond