Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
PlanarityTestImpl.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_PLANARITYIMPL_H
22#define TULIP_PLANARITYIMPL_H
23
24#include <map>
25#include <list>
26#include <vector>
27#include <unordered_map>
28#include <utility>
29
30#include <tulip/Edge.h>
31#include <tulip/MutableContainer.h>
32#include <tulip/BmdList.h>
33#include <tulip/tulipconf.h>
34#include <tulip/Node.h>
35
36namespace tlp {
37class Graph;
38enum { NOT_VISITED, VISITED, TERMINAL, VISITED_IN_RBC };
39#define NULL_NODE node()
40#define NULL_EDGE edge()
41
42class TLP_SCOPE PlanarityTestImpl {
43
44public:
45 PlanarityTestImpl(Graph *sg);
46 bool isPlanar(bool embedsg = false);
47 static bool isPlanarEmbedding(const Graph *sG);
48 std::list<edge> getObstructions();
49
50private:
51 bool compute(Graph *);
52 void init();
53 void restore();
54 edge edgeReversal(edge e);
55 void makeBidirected(Graph *sG);
56 void findTerminalNodes(Graph *sG, node n, std::list<node> &listOfComponents,
57 std::map<node, std::list<node>> &terminalNodes);
58 bool findObstruction(Graph *sG, node n, std::list<node> &terminalNodes);
59 void setInfoForNewCNode(Graph *sG, node n, node newCNode, std::list<node> &terminalNodes);
60 node findActiveCNode(node, node, std::list<node> &);
61 void preProcessing(Graph *);
62 tlp::BmdLink<node> *searchRBC(int, tlp::BmdLink<node> *, node, std::list<node> &);
63 bool isT0Edge(Graph *, edge);
64 bool isBackEdge(Graph *, edge);
65 bool isCNode(node);
66 void sortNodesIncreasingOrder(Graph *, MutableContainer<int> &, std::vector<node> &);
67 node activeCNodeOf(bool, node);
68 void addOldCNodeRBCToNewRBC(node, node, node, node, node, BmdList<node> &);
69 void updateLabelB(node);
70 void calcNewRBCFromTerminalNode(node, node, node, node, BmdList<node> &);
71 node lastPNode(node, node);
72 node lcaBetween(node, node, const MutableContainer<node> &);
73 node lcaBetweenTermNodes(node, node);
74 void calculateNewRBC(Graph *, node, node, std::list<node> &);
75 node findNodeWithLabelBGreaterThanDfsN(bool, Graph *, node, node);
76 void setPossibleK33Obstruction(node, node, node, node);
77 bool testCNodeCounter(Graph *, node, node, node, node, node &, node &);
78 bool testObstructionFromTerminalNode(Graph *, node, node, node);
79
80 // functions PlanarityTestObstr.cpp
81 bool listEdgesUpwardT0(node n1, node n2);
82 void extractBoundaryCycle(Graph *sG, node cNode, std::list<edge> &listEdges);
83 // edge findEdge(Graph *sG, node n1, node n2);
84 void obstrEdgesTerminal(Graph *G, node w, node t, node u);
85 void addPartOfBc(Graph *sG, node cNode, node n1, node n2, node n3);
86 void sortByLabelB(node &n1, node &n2, node &n3);
87 void obstrEdgesPNode(Graph *sG, node p, node u);
88 void calcInfo3Terminals(node &t1, node &t2, node &t3, int &countMin, int &countF, node &cNode,
89 node &q);
90 void obstructionEdgesT0(Graph *sG, node w, node t1, node t2, node t3, node v);
91 void obstructionEdgesCountMin1(Graph *sG, node n, node cNode, node t1, node t2, node t3);
92 void obstructionEdgesCountMin23(Graph *sG, node n, node cNode, node t1, node t2, node t3, node q,
93 node v);
94 // void obstrEdgesTermCNode(Graph *sG, node w, node t);
95 void obstructionEdgesK5(Graph *sG, node w, node cNode, node t1, node t2, node t3);
96 void obstructionEdgesPossibleObstrConfirmed(Graph *sG, node w, node t, node v);
97 void obstructionEdgesCNodeCounter(Graph *sG, node cNode, node w, node jl, node jr, node t1,
98 node t2);
99
100 // functions PlanarityTestEmbed.cpp
101 void embedRoot(Graph *sG, int n);
102 void calculatePartialEmbedding(Graph *sG, node w, node newCNode, std::list<edge> &listBackEdges,
103 std::list<node> &terminalNodes);
104 void markPathInT(node t, node w, std::map<node, node> &backEdgeRepresentant,
105 std::list<node> &traversedNodes);
106 std::map<node, std::list<edge>> groupBackEdgesByRepr(Graph *sG, std::list<edge> &listBackEdges,
107 std::map<node, node> &backEdgeRepresentant,
108 std::list<node> &traversedNodes,
109 std::list<node> &listRepresentants);
110 std::list<node> embedUpwardT(bool embBackEdgesOutW, node t1, node t2, Graph *sG, node w,
111 std::map<node, std::list<edge>> &bEdgesRepres,
112 std::list<node> &traversedNodes, BmdList<edge> &embList);
113 void addOldCNodeToEmbedding(bool embBackEdgesOutW, Graph *sG, node w, node oldCNode, node u,
114 std::map<node, std::list<edge>> &bEdgesRepres,
115 std::list<node> &traversedNodes, std::list<node> &toEmbedLater,
116 BmdList<edge> &embList);
117 void embedBackEdges(bool embBackEdgesOutW, Graph *sG, node repr, std::list<node> &traversedNodes,
118 std::list<edge> &listBackEdges, BmdList<edge> &embList);
119 int sortBackEdgesByDfs(Graph *sG, node w, node repr, std::list<edge> &listBackEdges,
120 std::vector<edge> &backEdge);
121
122 // void cleanPtrItem (node n, tlp::BmdLink<node>* item);
123
124 Graph *sg;
125 int totalCNodes;
126 bool embed, biconnected;
127 node lastNodeInQLinha;
128 std::unordered_map<edge, edge> bidirectedEdges;
129 std::unordered_map<edge, edge> reversalEdge;
130
131 // // auxiliary variable to help detecting obstruction;
132 node cNodeOfPossibleK33Obstruction;
133
134 // // for each node u in T, children is the list of u's children
135 // // ordered in decreasing order by label_b
136 // // (it helps to update label_b's in constant time);
137 // //node_array<list<node>> childrenInT0;
138 // //std::map<node, std::list<node>* > childrenInT0;
139 std::unordered_map<node, std::list<node>> childrenInT0;
140
141 // // for each 2-connected component represented by r,
142 // // list_back_edges[r] is the list of all back-edges in component r
143 // // (it helps to calculate an embedding of G, if G is planar);
144 // //node_array<list<edge> > listBackEdges;
145 // //std::map<node, std::list<edge>* > listBackEdges;
146 std::map<node, std::list<edge>> listBackEdges;
147
148 // // the Representative Boundary Cycle for each c-node;
149 // //std::map<node, BmdList<node> > RBC;
150 std::map<node, BmdList<node>> RBC;
151
152 // // for each node u in G, the algorithm calculates the
153 // // clockwise ordering of edges with source u around u, such that
154 // // G.sort_edges(embed_list) is a plane map, if it exists
155 std::unordered_map<node, BmdList<edge>> embedList;
156
157 // // to avoid path compression of c-nodes;
158 std::unordered_map<tlp::BmdLink<node> *, node> activeCNode;
159
160 // // (it helps to calculate an embedding of G, if G is planar, in
161 // // case of 2 terminal nodes);
162 BmdList<edge> listBackEdgesOutW;
163
164 // // list of nodes in an obstruction found in G if G is not planar
165 // // (it helps to calculate "obstruction_edges");
166 std::list<node> obstructionNodes;
167
168 // // list of edges in an obstruction found int G if G is not planar;
169 std::list<edge> obstructionEdges;
170
171 // //node_array<edge> backEdgeOut; NON UTILISE
172
173 // //node_map<BmdListItem> ptrItem;
174 MutableContainer<tlp::BmdLink<node> *> ptrItem;
175
176 // //node_map<int> dfsPosNum;
177 MutableContainer<int> dfsPosNum;
178
179 // //array<node> nodeWithDfsPos;
180 MutableContainer<node> nodeWithDfsPos;
181
182 // // to help calculate an embedding or an obstruction;
183 // //node_array<edge> T0EdgeIn;
184 MutableContainer<edge> T0EdgeIn;
185
186 // //node_map<node>
187 // //p0 saves initial DFS tree T_0 of G;
188 MutableContainer<node> parent;
189 MutableContainer<node> p0;
190
191 // // for each node u in T,
192 // // largest_neighbor[u] = max{dfspos_num[v] : v is a neighbor of u in G};
193 // //node_map<int> largestNeighbor;
194 MutableContainer<int> largestNeighbor;
195
196 // // for each node u in T,
197 // // label_b[u] = max{largest_neighbor[v] : v is a descendat of u in T_u}
198 // // where T_u is the subtree of T rooted at u;
199 // //node_map<int> labelB;
200 MutableContainer<int> labelB;
201
202 // // for each node u in T, node_label_b[u] = v
203 // // where v is a descendant of u in T and largest_neighbor[v] == label_b[u]
204 // // (it helps to find an obstruction in G, if G is not planar);
205 // //node_map<node> nodeLabelB;
206 MutableContainer<node> nodeLabelB;
207
208 // // to help find the lca between two terminal nodes;
209 // //node_map<node> lastVisited;
210 MutableContainer<node> lastVisited;
211
212 // // given w, for each terminal node u of w, neighbor_w_terminal[u] is
213 // // a descendant of u that is a neighbor of w in G;
214 // //node_map<node> neighborWTerminal;
215 MutableContainer<node> neighborWTerminal;
216
217 // // to help search for terminal nodes and calculate an embedding of G if G is
218 // // planar (states: VISITED, NOT_VISITED, TERMINAL);
219 // //node_map<int> state;
220 MutableContainer<int> state;
221
222 // // for each (active) c-node d, counter[d] is the number of children of d
223 // // with a descendant that are neighbor of w in G;
224 MutableContainer<int> counter;
225
226 // // (it helps to calculate an embedding of G, if G is planar);
227 // //node_array<bool> hasBackEdge;
228 MutableContainer<bool> hasBackEdge;
229 unsigned int numberOfNodesInG;
230};
231} // namespace tlp
232
233// std::ostream& operator <<(std::ostream &os , node n);
234// std::ostream& operator <<(std::ostream &os , edge e);
235std::list<tlp::edge> posDFS(tlp::Graph *sG, tlp::MutableContainer<int> &dfsPos);
236
237#endif
238
239///@endcond