Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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 <unordered_map>
26
27#include <tulip/Face.h>
28#include <tulip/GraphDecorator.h>
29
30namespace 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
44class 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
57protected:
58 /** Constructor
59 * Warning, the graph must be planar, connected and simple.
60 */
61 PlanarConMap(Graph *s);
62
63public:
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
154private:
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 std::unordered_map<Face, std::vector<edge>> faceMap;
167 typedef faceMap::value_type faceMapEntry;
168 typedef std::unordered_map<edge, std::vector<Face>> edgeMap;
169 typedef edgeMap::value_type edgeMapEntry;
170 typedef std::unordered_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
184TLP_SCOPE PlanarConMap *computePlanarConMap(Graph *graph);
185} // namespace tlp
186
187/// Print the map (only faces, nodes and edges) in ostream, in the tulip format
188TLP_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.