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