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