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