Tulip  4.10.0
Better Visualization Through Research
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
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 #ifndef Tulip_PlanarConMap_H
22 #define Tulip_PlanarConMap_H
23 
24 #include <vector>
25 #include <tulip/tuliphash.h>
26 #include <tulip/Face.h>
27 #include <tulip/GraphDecorator.h>
28 
29 namespace tlp {
30 
31 struct Face;
32 class IdManager;
33 
34 /**
35  * \brief interface for a topological graph
36  */
37 /**
38  * The class PlanarConMap is an interface for map in the Tulip Library. This only
39  * considers connected planar map, moreover the graph must be simple.
40  * After, its initialization, if modifications, such as additions or deletions of
41  * edges or/and nodes, are made on the supergraph, the map will not be
42  * valid any more. In this case, one can calls update() function to update the map
43  * but it completely compute the map.
44  */
45 
46 
47 class TLP_SCOPE PlanarConMap : public GraphDecorator {
48 
49  /* for test classes */
50  friend class FaceIteratorTest;
51  friend class PlanarConMapTest;
52 
53 
54  friend class FaceIterator;
55  friend class FaceAdjIterator;
56  friend class NodeFaceIterator;
57  friend class EdgeFaceIterator;
58 
59  friend TLP_SCOPE PlanarConMap* computePlanarConMap(Graph* graph);
60 
61 protected:
62  /** Constructor
63  * Warning, the graph must be planar, connected and simple.
64  */
65  PlanarConMap(Graph* s);
66 
67 
68 public:
69 
70  //Destructor.
71  virtual ~PlanarConMap();
72 
73  /**
74  * Remove all nodes, edges, faces and subgraphs of the map
75  */
76  void clear();
77 
78  /** Update the map : this recompute completely the map.
79  * To do when an operation on one of the super-graphs of the map has been done.
80  */
81  void update();
82 
83  //==============================================================================
84  // Modification of the graph structure
85  //==============================================================================
86  /**
87  * Add and return an edge between two node u and v in the map. This edge is added in
88  * face f, and e1 and e2 will be predecessor of respectively v and w in the
89  * cycles around v and w. The new face is put into new_face.
90  * This edge is also added in all the super-graph of the map to maintain
91  * the sub-graph relation between graphs.
92  * Warning, the edge must be element of the graph hierarchy, thus it must be
93  * element of the root graph.
94  * Warning : One can't add an existing edge to the root graph
95  */
96  edge addEdgeMap(const node v, const node w, Face f, const edge e1, const edge e2, Face new_face= Face());
97 
98  /** Split the face by adding an edge between the two nodes and return the
99  * new face. Possibility to specify which will be the new face, by giving a
100  * node that will be contained into the new face.
101  * Warning, the edge must be element of the graph hierarchy, thus it must be
102  * element of the root graph.
103  */
104  Face splitFace(Face, const node, const node, node = node());
105 
106  /** Split the face by adding the edge and return the new face.
107  * Warning, the edge must be element of the graph hierarchy, thus it must be
108  * element of the root graph.
109  */
110  Face splitFace(Face, const edge);
111 
112  /** Merge two faces into one and put the new computed face into f.
113  * Warning, the edge must be element of the graph hierarchy, thus it must be
114  * element of the root graph.
115  */
116  void mergeFaces(Face f, Face g);
117 
118 
119  //================================================================================
120  //Iterators on the graph structure.
121  //================================================================================
122 
123  ///Return an iterator on the faces.
124  Iterator<Face>* getFaces();
125  ///Return an iterator on the adjacent faces of a node.
126  Iterator<Face>* getFacesAdj(const node);
127  ///Return an iterator on the nodes of a face.
128  Iterator<node>* getFaceNodes(const Face);
129  ///Return an iterator on the edges of a face.
130  Iterator<edge>* getFaceEdges(const Face);
131 
132  //================================================================================
133  // Graph, nodes and edges information about the graph stucture
134  //================================================================================
135  ///Return the edge which is the succcessor of an edge in the cycle of a node.
136  edge succCycleEdge(const edge, const node) const;
137  ///Return the edge which is the predecessor of an edge in the cycle of a node.
138  edge predCycleEdge(const edge, const node) const;
139  ///Return the node which is the succcessor of a node in the cycle of a node.
140  node succCycleNode(const node, const node) const;
141  ///Return the node which is the predecessor of a node in the cycle of a node.
142  node predCycleNode(const node, const node) const;
143 
144  ///Return the number of faces.
145  unsigned int nbFaces();
146  ///Return the number of nodes contained into a face.
147  unsigned int nbFacesNodes(const Face);
148  ///Return the number of edges contained into a face.
149  unsigned int nbFacesEdges(const Face);
150 
151  ///Return true if the face contains the node.
152  bool containNode(const Face, const node) ;
153  ///Return true if the face contains the edge.
154  bool containEdge(const Face, const edge);
155  /** Returns the face containing the two nodes in this order
156  * and the edge between this two nodes.
157  * Warning, the edge must exists in the map.
158  */
159  Face getFaceContaining(const node, const node);
160  /// Return a face containing the two nodes if it exists and Face() otherwise
161  Face sameFace(const node, const node);
162 
163 
164 private:
165 
166  /** Compute faces and initialize all variables.
167  */
168  void computeFaces();
169  /**
170  * Delete the edge in the map. The new face can be put into a specified face,
171  * otherwise, one of the two adjacent faces will be updated.
172  * Warning, the edge must not be an isthm of the map, otherwize the map will be deconnected
173  * and so won't be valid any more.
174  */
175  void delEdgeMap(edge, Face = Face());
176 
177  typedef TLP_HASH_MAP<Face , std::vector<edge> > faceMap;
178  typedef faceMap::value_type faceMapEntry;
179  typedef TLP_HASH_MAP<edge, std::vector<Face> > edgeMap;
180  typedef edgeMap::value_type edgeMapEntry;
181  typedef TLP_HASH_MAP<node, std::vector<Face> > nodeMap;
182  typedef nodeMap::value_type nodeMapEntry;
183 
184  /** storage of faces */
185  faceMap facesEdges;
186  edgeMap edgesFaces;
187  nodeMap nodesFaces;
188  mutable std::vector<Face > faces;
189 
190  IdManager *faceId;
191 
192 };
193 
194 // Compute a PlanarConMap from a graph.
195 // return a NULL value if the graph is not connected
196 TLP_SCOPE PlanarConMap* computePlanarConMap(Graph* graph);
197 
198 }
199 
200 ///Print the map (only faces, nodes and edges) in ostream, in the tulip format
201 TLP_SCOPE std::ostream& operator<< (std::ostream &, tlp::PlanarConMap *);
202 
203 #endif
204 
205 ///@endcond
std::ostream & operator<<(std::ostream &os, const Array< Obj, SIZE > &array)
operator << stream operator to easily print an array, or save it to a file.
Definition: Array.cxx:34
Interface for Tulip iterators. Allows basic iteration operations only.
Definition: Iterator.h:39