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