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