![]() |
Tulip
4.6.0
Better Visualization Through Research
|
00001 /* 00002 * 00003 * This file is part of Tulip (www.tulip-software.org) 00004 * 00005 * Authors: David Auber and the Tulip development Team 00006 * from LaBRI, University of Bordeaux 00007 * 00008 * Tulip is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU Lesser General Public License 00010 * as published by the Free Software Foundation, either version 3 00011 * of the License, or (at your option) any later version. 00012 * 00013 * Tulip is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00016 * See the GNU General Public License for more details. 00017 * 00018 */ 00019 ///@cond DOXYGEN_HIDDEN 00020 00021 00022 #ifndef TULIP_PLANARITYIMPL_H 00023 #define TULIP_PLANARITYIMPL_H 00024 00025 #ifndef DOXYGEN_NOTFOR_USER 00026 00027 #include <list> 00028 #include <vector> 00029 00030 #include <tulip/Edge.h> 00031 #include <tulip/MutableContainer.h> 00032 #include <tulip/BmdList.h> 00033 #include <tulip/tulipconf.h> 00034 #include <tulip/Node.h> 00035 00036 namespace tlp { 00037 class Graph; 00038 enum { NOT_VISITED, VISITED, TERMINAL, VISITED_IN_RBC }; 00039 static const node NULL_NODE = node(); 00040 static const edge NULL_EDGE = edge(); 00041 00042 class TLP_SCOPE PlanarityTestImpl { 00043 00044 public: 00045 PlanarityTestImpl(Graph *sg); 00046 bool isPlanar(bool embedsg = false); 00047 static bool isPlanarEmbedding(const Graph *sG); 00048 std::list<edge> getObstructions(); 00049 00050 private: 00051 bool compute(Graph *); 00052 void init(); 00053 void restore(); 00054 edge edgeReversal( edge e); 00055 void makeBidirected(Graph *sG); 00056 void swapNode(node &n1, node &n2); 00057 void findTerminalNodes(Graph *sG, node n, std::list<node>& listOfComponents, 00058 std::map<node, std::list<node> > &terminalNodes); 00059 bool findObstruction(Graph *sG, node n, std::list<node>& terminalNodes); 00060 void setInfoForNewCNode(Graph *sG, node n, node newCNode, 00061 std::list<node>& terminalNodes); 00062 node findActiveCNode(node, node, std::list<node>&); 00063 void preProcessing(Graph *); 00064 tlp::BmdLink<node>* searchRBC(int, tlp::BmdLink<node>*, node, std::list<node>&); 00065 bool isT0Edge(Graph *, edge); 00066 bool isBackEdge(Graph *, edge); 00067 bool isCNode(node); 00068 void sortNodesIncreasingOrder(Graph *, MutableContainer<int>&, std::vector<node>&); 00069 node activeCNodeOf(bool, node); 00070 void addOldCNodeRBCToNewRBC(node, node, node, node, node, BmdList<node>&); 00071 void updateLabelB(node); 00072 void calcNewRBCFromTerminalNode(node, node, node, node, BmdList<node>&); 00073 node lastPNode(node, node); 00074 node lcaBetween(node, node, const MutableContainer<node>&); 00075 node lcaBetweenTermNodes(node, node); 00076 void calculateNewRBC(Graph *, node, node, std::list<node>&); 00077 node findNodeWithLabelBGreaterThanDfsN(bool, Graph *, node, node); 00078 void setPossibleK33Obstruction(node, node, node, node); 00079 bool testCNodeCounter(Graph *, node, node, node, node, node&, node&); 00080 bool testObstructionFromTerminalNode(Graph *, node, node, node); 00081 00082 //functions PlanarityTestObstr.cpp 00083 bool listEdgesUpwardT0(node n1, node n2); 00084 void extractBoundaryCycle(Graph *sG, node cNode, std::list<edge>& listEdges); 00085 // edge findEdge(Graph *sG, node n1, node n2); 00086 void obstrEdgesTerminal(Graph* G, node w, node t, node u); 00087 void addPartOfBc(Graph *sG, node cNode, node n1, node n2, node n3); 00088 void sortByLabelB(node &n1, node &n2, node &n3); 00089 void obstrEdgesPNode(Graph *sG, node p, node u); 00090 void calcInfo3Terminals(node &t1, node &t2, node &t3, int &countMin, int &countF, node &cNode, node &q); 00091 void obstructionEdgesT0(Graph *sG, node w, node t1, node t2, node t3, node v); 00092 void obstructionEdgesCountMin1(Graph *sG, node n, node cNode, node t1, node t2, node t3); 00093 void obstructionEdgesCountMin23(Graph *sG, node n, node cNode, node t1, node t2, node t3, node q, node v); 00094 // void obstrEdgesTermCNode(Graph *sG, node w, node t); 00095 void obstructionEdgesK5(Graph *sG, node w, node cNode, node t1, node t2, node t3); 00096 void obstructionEdgesPossibleObstrConfirmed(Graph *sG, node w, node t, node v); 00097 void obstructionEdgesCNodeCounter(Graph *sG, node cNode, node w, node jl, node jr, node t1, node t2); 00098 00099 // functions PlanarityTestEmbed.cpp 00100 void embedRoot(Graph *sG, int n); 00101 void calculatePartialEmbedding(Graph *sG, node w, node newCNode, std::list<edge>& listBackEdges, std::list<node>& terminalNodes); 00102 void markPathInT(node t, node w, std::map<node, node>& backEdgeRepresentant, std::list<node>& traversedNodes); 00103 std::map< node, std::list<edge> > groupBackEdgesByRepr(Graph *sG, std::list<edge>& listBackEdges, 00104 std::map<node, node>& backEdgeRepresentant, 00105 std::list<node>& traversedNodes, 00106 std::list<node>& listRepresentants); 00107 std::list<node> embedUpwardT(bool embBackEdgesOutW, node t1, node t2, Graph *sG, node w, 00108 std::map< node, std::list<edge> > &bEdgesRepres, 00109 std::list<node>& traversedNodes, 00110 BmdList<edge>& embList); 00111 void addOldCNodeToEmbedding(bool embBackEdgesOutW, Graph *sG, node w, node oldCNode, node u, 00112 std::map<node,std::list<edge> >& bEdgesRepres, 00113 std::list<node>& traversedNodes, 00114 std::list<node>& toEmbedLater, 00115 BmdList<edge>& embList); 00116 void embedBackEdges(bool embBackEdgesOutW, Graph *sG, node repr, 00117 std::list<node>& traversedNodes, 00118 std::list<edge>& listBackEdges, 00119 BmdList<edge>& embList); 00120 int sortBackEdgesByDfs(Graph *sG, node w, node repr, 00121 std::list<edge>& listBackEdges, 00122 std::vector<edge>& backEdge); 00123 00124 // void cleanPtrItem (node n, tlp::BmdLink<node>* item); 00125 00126 Graph *sg; 00127 int totalCNodes; 00128 bool embed, biconnected; 00129 node lastNodeInQLinha; 00130 std::map<edge, edge> bidirectedEdges; 00131 std::map<edge, edge> reversalEdge; 00132 00133 // // auxiliary variable to help detecting obstruction; 00134 node cNodeOfPossibleK33Obstruction; 00135 00136 // // for each node u in T, children is the list of u's children 00137 // // ordered in decreasing order by label_b 00138 // // (it helps to update label_b's in constant time); 00139 // //node_array<list<node>> childrenInT0; 00140 // //std::map<node, std::list<node>* > childrenInT0; 00141 std::map<node, std::list<node> > childrenInT0; 00142 00143 // // for each 2-connected component represented by r, 00144 // // list_back_edges[r] is the list of all back-edges in component r 00145 // // (it helps to calculate an embedding of G, if G is planar); 00146 // //node_array<list<edge> > listBackEdges; 00147 // //std::map<node, std::list<edge>* > listBackEdges; 00148 std::map<node, std::list<edge> > listBackEdges; 00149 00150 // // the Representative Boundary Cycle for each c-node; 00151 // //std::map<node, BmdList<node> > RBC; 00152 std::map<node, BmdList<node> > RBC; 00153 00154 // // for each node u in G, the algorithm calculates the 00155 // // clockwise ordering of edges with source u around u, such that 00156 // // G.sort_edges(embed_list) is a plane map, if it exists 00157 std::map<node, BmdList<edge> > embedList; 00158 00159 // // to avoid path compression of c-nodes; 00160 std::map<tlp::BmdLink<node>*, node> activeCNode; 00161 00162 // // (it helps to calculate an embedding of G, if G is planar, in 00163 // // case of 2 terminal nodes); 00164 BmdList<edge> listBackEdgesOutW; 00165 00166 // // list of nodes in an obstruction found in G if G is not planar 00167 // // (it helps to calculate "obstruction_edges"); 00168 std::list<node> obstructionNodes; 00169 00170 // // list of edges in an obstruction found int G if G is not planar; 00171 std::list<edge> obstructionEdges; 00172 00173 00174 // //node_array<edge> backEdgeOut; NON UTILISE 00175 00176 // //node_map<BmdListItem> ptrItem; 00177 MutableContainer< tlp::BmdLink<node>*> ptrItem; 00178 00179 // //node_map<int> dfsPosNum; 00180 MutableContainer<int> dfsPosNum; 00181 00182 // //array<node> nodeWithDfsPos; 00183 MutableContainer<node> nodeWithDfsPos; 00184 00185 // // to help calculate an embedding or an obstruction; 00186 // //node_array<edge> T0EdgeIn; 00187 MutableContainer<edge> T0EdgeIn; 00188 00189 // //node_map<node> 00190 // //p0 saves initial DFS tree T_0 of G; 00191 MutableContainer<node> parent; 00192 MutableContainer<node> p0; 00193 00194 // // for each node u in T, 00195 // // largest_neighbor[u] = max{dfspos_num[v] : v is a neighbor of u in G}; 00196 // //node_map<int> largestNeighbor; 00197 MutableContainer<int> largestNeighbor; 00198 00199 // // for each node u in T, 00200 // // label_b[u] = max{largest_neighbor[v] : v is a descendat of u in T_u} 00201 // // where T_u is the subtree of T rooted at u; 00202 // //node_map<int> labelB; 00203 MutableContainer<int> labelB; 00204 00205 // // for each node u in T, node_label_b[u] = v 00206 // // where v is a descendant of u in T and largest_neighbor[v] == label_b[u] 00207 // // (it helps to find an obstruction in G, if G is not planar); 00208 // //node_map<node> nodeLabelB; 00209 MutableContainer<node> nodeLabelB; 00210 00211 // // to help find the lca between two terminal nodes; 00212 // //node_map<node> lastVisited; 00213 MutableContainer<node> lastVisited; 00214 00215 // // given w, for each terminal node u of w, neighbor_w_terminal[u] is 00216 // // a descendant of u that is a neighbor of w in G; 00217 // //node_map<node> neighborWTerminal; 00218 MutableContainer<node> neighborWTerminal; 00219 00220 // // to help search for terminal nodes and calculate an embedding of G if G is 00221 // // planar (states: VISITED, NOT_VISITED, TERMINAL); 00222 // //node_map<int> state; 00223 MutableContainer<int> state; 00224 00225 // // for each (active) c-node d, counter[d] is the number of children of d 00226 // // with a descendant that are neighbor of w in G; 00227 MutableContainer<int> counter; 00228 00229 // // (it helps to calculate an embedding of G, if G is planar); 00230 // //node_array<bool> hasBackEdge; 00231 MutableContainer<bool> hasBackEdge; 00232 unsigned int numberOfNodesInG; 00233 }; 00234 00235 } 00236 00237 //std::ostream& operator <<(std::ostream &os , node n); 00238 //std::ostream& operator <<(std::ostream &os , edge e); 00239 std::list<tlp::edge> posDFS(tlp::Graph *sG, tlp::MutableContainer<int> &dfsPos); 00240 00241 #endif 00242 #endif 00243 ///@endcond