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