Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/PlanarityTestImpl.h
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
 All Classes Files Functions Variables Enumerations Enumerator Properties