Tulip  5.7.4
Large graphs analysis and drawing
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 
36 namespace tlp {
37 class Graph;
38 enum { NOT_VISITED, VISITED, TERMINAL, VISITED_IN_RBC };
39 #define NULL_NODE node()
40 #define NULL_EDGE edge()
41 
42 class TLP_SCOPE PlanarityTestImpl {
43 
44 public:
45  PlanarityTestImpl(Graph *sg);
46  bool isPlanar(bool embedsg = false);
47  static bool isPlanarEmbedding(const Graph *sG);
48  std::list<edge> getObstructions();
49 
50 private:
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 descendant 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);
235 std::list<tlp::edge> posDFS(tlp::Graph *sG, tlp::MutableContainer<int> &dfsPos);
236 
237 #endif
238 
239 ///@endcond