Tulip  4.1.0
Better Visualization Through Research
 All Classes 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 #include <tulip/ObservableGraph.h>
30 #include <tulip/Edge.h>
31 #include <tulip/MutableContainer.h>
32 #include <tulip/BmdList.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,
59  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, 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, node v);
92  // void obstrEdgesTermCNode(Graph *sG, node w, node t);
93  void obstructionEdgesK5(Graph *sG, node w, node cNode, node t1, node t2, node t3);
94  void obstructionEdgesPossibleObstrConfirmed(Graph *sG, node w, node t, node v);
95  void obstructionEdgesCNodeCounter(Graph *sG, node cNode, node w, node jl, node jr, node t1, node t2);
96 
97  // functions PlanarityTestEmbed.cpp
98  void embedRoot(Graph *sG, int n);
99  void calculatePartialEmbedding(Graph *sG, node w, node newCNode, std::list<edge>& listBackEdges, std::list<node>& terminalNodes);
100  void markPathInT(node t, node w, std::map<node, node>& backEdgeRepresentant, std::list<node>& traversedNodes);
101  std::map< node, std::list<edge> > groupBackEdgesByRepr(Graph *sG, std::list<edge>& listBackEdges,
102  std::map<node, node>& backEdgeRepresentant,
103  std::list<node>& traversedNodes,
104  std::list<node>& listRepresentants);
105  std::list<node> embedUpwardT(bool embBackEdgesOutW, node t1, node t2, Graph *sG, node w,
106  std::map< node, std::list<edge> > &bEdgesRepres,
107  std::list<node>& traversedNodes,
108  BmdList<edge>& embList);
109  void addOldCNodeToEmbedding(bool embBackEdgesOutW, Graph *sG, node w, node oldCNode, node u,
110  std::map<node,std::list<edge> >& bEdgesRepres,
111  std::list<node>& traversedNodes,
112  std::list<node>& toEmbedLater,
113  BmdList<edge>& embList);
114  void embedBackEdges(bool embBackEdgesOutW, Graph *sG, node repr,
115  std::list<node>& traversedNodes,
116  std::list<edge>& listBackEdges,
117  BmdList<edge>& embList);
118  int sortBackEdgesByDfs(Graph *sG, node w, node repr,
119  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::map<edge, edge> bidirectedEdges;
129  std::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::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::map<node, BmdList<edge> > embedList;
156 
157 // // to avoid path compression of c-nodes;
158  std::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 
172 // //node_array<edge> backEdgeOut; NON UTILISE
173 
174 // //node_map<BmdListItem> ptrItem;
175  MutableContainer< tlp::BmdLink<node>*> ptrItem;
176 
177 // //node_map<int> dfsPosNum;
178  MutableContainer<int> dfsPosNum;
179 
180 // //array<node> nodeWithDfsPos;
181  MutableContainer<node> nodeWithDfsPos;
182 
183 // // to help calculate an embedding or an obstruction;
184 // //node_array<edge> T0EdgeIn;
185  MutableContainer<edge> T0EdgeIn;
186 
187 // //node_map<node>
188 // //p0 saves initial DFS tree T_0 of G;
189  MutableContainer<node> parent;
190  MutableContainer<node> p0;
191 
192 // // for each node u in T,
193 // // largest_neighbor[u] = max{dfspos_num[v] : v is a neighbor of u in G};
194 // //node_map<int> largestNeighbor;
195  MutableContainer<int> largestNeighbor;
196 
197 // // for each node u in T,
198 // // label_b[u] = max{largest_neighbor[v] : v is a descendat of u in T_u}
199 // // where T_u is the subtree of T rooted at u;
200 // //node_map<int> labelB;
201  MutableContainer<int> labelB;
202 
203 // // for each node u in T, node_label_b[u] = v
204 // // where v is a descendant of u in T and largest_neighbor[v] == label_b[u]
205 // // (it helps to find an obstruction in G, if G is not planar);
206 // //node_map<node> nodeLabelB;
207  MutableContainer<node> nodeLabelB;
208 
209 // // to help find the lca between two terminal nodes;
210 // //node_map<node> lastVisited;
211  MutableContainer<node> lastVisited;
212 
213 // // given w, for each terminal node u of w, neighbor_w_terminal[u] is
214 // // a descendant of u that is a neighbor of w in G;
215 // //node_map<node> neighborWTerminal;
216  MutableContainer<node> neighborWTerminal;
217 
218 // // to help search for terminal nodes and calculate an embedding of G if G is
219 // // planar (states: VISITED, NOT_VISITED, TERMINAL);
220 // //node_map<int> state;
221  MutableContainer<int> state;
222 
223 // // for each (active) c-node d, counter[d] is the number of children of d
224 // // with a descendant that are neighbor of w in G;
225  MutableContainer<int> counter;
226 
227 // // (it helps to calculate an embedding of G, if G is planar);
228 // //node_array<bool> hasBackEdge;
229  MutableContainer<bool> hasBackEdge;
230  unsigned int numberOfNodesInG;
231 };
232 
233 }
234 
235 //std::ostream& operator <<(std::ostream &os , node n);
236 //std::ostream& operator <<(std::ostream &os , edge e);
237 std::list<tlp::edge> posDFS(tlp::Graph *sG, tlp::MutableContainer<int> &dfsPos);
238 
239 #endif
240 #endif
241 ///@endcond