Tulip  4.4.0
Better Visualization Through Research
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Groups Pages
PlanarityTestImpl.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux 1 and Inria Bordeaux - Sud Ouest
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 #ifndef DOXYGEN_NOTFOR_USER
26 
27 #include <list>
28 #include <vector>
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 static const node NULL_NODE = node();
40 static const edge 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 swapNode(node &n1, node &n2);
57  void findTerminalNodes(Graph *sG, node n, std::list<node>& listOfComponents,
58  std::map<node, std::list<node> > &terminalNodes);
59  bool findObstruction(Graph *sG, node n, std::list<node>& terminalNodes);
60  void setInfoForNewCNode(Graph *sG, node n, node newCNode,
61  std::list<node>& terminalNodes);
62  node findActiveCNode(node, node, std::list<node>&);
63  void preProcessing(Graph *);
64  tlp::BmdLink<node>* searchRBC(int, tlp::BmdLink<node>*, node, std::list<node>&);
65  bool isT0Edge(Graph *, edge);
66  bool isBackEdge(Graph *, edge);
67  bool isCNode(node);
68  void sortNodesIncreasingOrder(Graph *, MutableContainer<int>&, std::vector<node>&);
69  node activeCNodeOf(bool, node);
70  void addOldCNodeRBCToNewRBC(node, node, node, node, node, BmdList<node>&);
71  void updateLabelB(node);
72  void calcNewRBCFromTerminalNode(node, node, node, node, BmdList<node>&);
73  node lastPNode(node, node);
74  node lcaBetween(node, node, const MutableContainer<node>&);
75  node lcaBetweenTermNodes(node, node);
76  void calculateNewRBC(Graph *, node, node, std::list<node>&);
77  node findNodeWithLabelBGreaterThanDfsN(bool, Graph *, node, node);
78  void setPossibleK33Obstruction(node, node, node, node);
79  bool testCNodeCounter(Graph *, node, node, node, node, node&, node&);
80  bool testObstructionFromTerminalNode(Graph *, node, node, node);
81 
82  //functions PlanarityTestObstr.cpp
83  bool listEdgesUpwardT0(node n1, node n2);
84  void extractBoundaryCycle(Graph *sG, node cNode, std::list<edge>& listEdges);
85  // edge findEdge(Graph *sG, node n1, node n2);
86  void obstrEdgesTerminal(Graph* G, node w, node t, node u);
87  void addPartOfBc(Graph *sG, node cNode, node n1, node n2, node n3);
88  void sortByLabelB(node &n1, node &n2, node &n3);
89  void obstrEdgesPNode(Graph *sG, node p, node u);
90  void calcInfo3Terminals(node &t1, node &t2, node &t3, int &countMin, int &countF, node &cNode, node &q);
91  void obstructionEdgesT0(Graph *sG, node w, node t1, node t2, node t3, node v);
92  void obstructionEdgesCountMin1(Graph *sG, node n, node cNode, node t1, node t2, node t3);
93  void obstructionEdgesCountMin23(Graph *sG, node n, node cNode, node t1, node t2, node t3, node q, 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, 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, std::list<node>& terminalNodes);
102  void markPathInT(node t, node w, std::map<node, node>& backEdgeRepresentant, std::list<node>& traversedNodes);
103  std::map< node, std::list<edge> > groupBackEdgesByRepr(Graph *sG, std::list<edge>& listBackEdges,
104  std::map<node, node>& backEdgeRepresentant,
105  std::list<node>& traversedNodes,
106  std::list<node>& listRepresentants);
107  std::list<node> embedUpwardT(bool embBackEdgesOutW, node t1, node t2, Graph *sG, node w,
108  std::map< node, std::list<edge> > &bEdgesRepres,
109  std::list<node>& traversedNodes,
110  BmdList<edge>& embList);
111  void addOldCNodeToEmbedding(bool embBackEdgesOutW, Graph *sG, node w, node oldCNode, node u,
112  std::map<node,std::list<edge> >& bEdgesRepres,
113  std::list<node>& traversedNodes,
114  std::list<node>& toEmbedLater,
115  BmdList<edge>& embList);
116  void embedBackEdges(bool embBackEdgesOutW, Graph *sG, node repr,
117  std::list<node>& traversedNodes,
118  std::list<edge>& listBackEdges,
119  BmdList<edge>& embList);
120  int sortBackEdgesByDfs(Graph *sG, node w, node repr,
121  std::list<edge>& listBackEdges,
122  std::vector<edge>& backEdge);
123 
124 // void cleanPtrItem (node n, tlp::BmdLink<node>* item);
125 
126  Graph *sg;
127  int totalCNodes;
128  bool embed, biconnected;
129  node lastNodeInQLinha;
130  std::map<edge, edge> bidirectedEdges;
131  std::map<edge, edge> reversalEdge;
132 
133 // // auxiliary variable to help detecting obstruction;
134  node cNodeOfPossibleK33Obstruction;
135 
136 // // for each node u in T, children is the list of u's children
137 // // ordered in decreasing order by label_b
138 // // (it helps to update label_b's in constant time);
139 // //node_array<list<node>> childrenInT0;
140 // //std::map<node, std::list<node>* > childrenInT0;
141  std::map<node, std::list<node> > childrenInT0;
142 
143 // // for each 2-connected component represented by r,
144 // // list_back_edges[r] is the list of all back-edges in component r
145 // // (it helps to calculate an embedding of G, if G is planar);
146 // //node_array<list<edge> > listBackEdges;
147 // //std::map<node, std::list<edge>* > listBackEdges;
148  std::map<node, std::list<edge> > listBackEdges;
149 
150 // // the Representative Boundary Cycle for each c-node;
151 // //std::map<node, BmdList<node> > RBC;
152  std::map<node, BmdList<node> > RBC;
153 
154 // // for each node u in G, the algorithm calculates the
155 // // clockwise ordering of edges with source u around u, such that
156 // // G.sort_edges(embed_list) is a plane map, if it exists
157  std::map<node, BmdList<edge> > embedList;
158 
159 // // to avoid path compression of c-nodes;
160  std::map<tlp::BmdLink<node>*, node> activeCNode;
161 
162 // // (it helps to calculate an embedding of G, if G is planar, in
163 // // case of 2 terminal nodes);
164  BmdList<edge> listBackEdgesOutW;
165 
166 // // list of nodes in an obstruction found in G if G is not planar
167 // // (it helps to calculate "obstruction_edges");
168  std::list<node> obstructionNodes;
169 
170 // // list of edges in an obstruction found int G if G is not planar;
171  std::list<edge> obstructionEdges;
172 
173 
174 // //node_array<edge> backEdgeOut; NON UTILISE
175 
176 // //node_map<BmdListItem> ptrItem;
177  MutableContainer< tlp::BmdLink<node>*> ptrItem;
178 
179 // //node_map<int> dfsPosNum;
180  MutableContainer<int> dfsPosNum;
181 
182 // //array<node> nodeWithDfsPos;
183  MutableContainer<node> nodeWithDfsPos;
184 
185 // // to help calculate an embedding or an obstruction;
186 // //node_array<edge> T0EdgeIn;
187  MutableContainer<edge> T0EdgeIn;
188 
189 // //node_map<node>
190 // //p0 saves initial DFS tree T_0 of G;
191  MutableContainer<node> parent;
192  MutableContainer<node> p0;
193 
194 // // for each node u in T,
195 // // largest_neighbor[u] = max{dfspos_num[v] : v is a neighbor of u in G};
196 // //node_map<int> largestNeighbor;
197  MutableContainer<int> largestNeighbor;
198 
199 // // for each node u in T,
200 // // label_b[u] = max{largest_neighbor[v] : v is a descendat of u in T_u}
201 // // where T_u is the subtree of T rooted at u;
202 // //node_map<int> labelB;
203  MutableContainer<int> labelB;
204 
205 // // for each node u in T, node_label_b[u] = v
206 // // where v is a descendant of u in T and largest_neighbor[v] == label_b[u]
207 // // (it helps to find an obstruction in G, if G is not planar);
208 // //node_map<node> nodeLabelB;
209  MutableContainer<node> nodeLabelB;
210 
211 // // to help find the lca between two terminal nodes;
212 // //node_map<node> lastVisited;
213  MutableContainer<node> lastVisited;
214 
215 // // given w, for each terminal node u of w, neighbor_w_terminal[u] is
216 // // a descendant of u that is a neighbor of w in G;
217 // //node_map<node> neighborWTerminal;
218  MutableContainer<node> neighborWTerminal;
219 
220 // // to help search for terminal nodes and calculate an embedding of G if G is
221 // // planar (states: VISITED, NOT_VISITED, TERMINAL);
222 // //node_map<int> state;
223  MutableContainer<int> state;
224 
225 // // for each (active) c-node d, counter[d] is the number of children of d
226 // // with a descendant that are neighbor of w in G;
227  MutableContainer<int> counter;
228 
229 // // (it helps to calculate an embedding of G, if G is planar);
230 // //node_array<bool> hasBackEdge;
231  MutableContainer<bool> hasBackEdge;
232  unsigned int numberOfNodesInG;
233 };
234 
235 }
236 
237 //std::ostream& operator <<(std::ostream &os , node n);
238 //std::ostream& operator <<(std::ostream &os , edge e);
239 std::list<tlp::edge> posDFS(tlp::Graph *sG, tlp::MutableContainer<int> &dfsPos);
240 
241 #endif
242 #endif
243 ///@endcond