1 /** \file 2 * \brief Declaration of the class BoyerMyrvoldPlanar 3 * 4 * \author Jens Schmidt 5 * 6 * 7 * \par License: 8 * This file is part of the Open Graph Drawing Framework (OGDF). 9 * 10 * \par 11 * Copyright (C)<br> 12 * See README.md in the OGDF root directory for details. 13 * 14 * \par 15 * This program is free software; you can redistribute it and/or 16 * modify it under the terms of the GNU General Public License 17 * Version 2 or 3 as published by the Free Software Foundation; 18 * see the file LICENSE.txt included in the packaging of this file 19 * for details. 20 * 21 * \par 22 * This program is distributed in the hope that it will be useful, 23 * but WITHOUT ANY WARRANTY; without even the implied warranty of 24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 25 * GNU General Public License for more details. 26 * 27 * \par 28 * You should have received a copy of the GNU General Public 29 * License along with this program; if not, see 30 * http://www.gnu.org/copyleft/gpl.html 31 */ 32 33 #pragma once 34 35 #include <random> 36 #include <ogdf/basic/NodeArray.h> 37 #include <ogdf/basic/EdgeArray.h> 38 #include <ogdf/basic/List.h> 39 #include <ogdf/basic/SList.h> 40 41 namespace ogdf { 42 43 //! Type of edge 44 enum class BoyerMyrvoldEdgeType { 45 Undefined=0, //!< undefined 46 Selfloop=1, //!< selfloop 47 Back=2, //!< backedge 48 Dfs=3, //!< DFS-edge 49 DfsParallel=4, //!< parallel DFS-edge 50 BackDeleted=5 //!< deleted backedge 51 }; 52 53 class KuratowskiStructure; 54 class FindKuratowskis; 55 namespace boyer_myrvold { 56 class BoyerMyrvoldInit; 57 } 58 59 //! This class implements the extended BoyerMyrvold planarity embedding algorithm 60 class BoyerMyrvoldPlanar 61 { 62 friend class BoyerMyrvold; 63 friend class boyer_myrvold::BoyerMyrvoldInit; 64 friend class FindKuratowskis; 65 friend class ExtractKuratowskis; 66 67 public: 68 //! Direction for counterclockwise traversal 69 const static int DirectionCCW; 70 71 //! Direction for clockwise traversal 72 const static int DirectionCW; 73 74 //! Denotes the different embedding options 75 enum class EmbeddingGrade { 76 doNotEmbed=-3, // and not find any kuratowski subdivisions 77 doNotFind=-2, // but embed 78 doFindUnlimited=-1, // and embed 79 doFindZero=0 // and embed 80 }; 81 82 //! Constructor, for parameters see BoyerMyrvold 83 BoyerMyrvoldPlanar( 84 Graph& g, 85 bool bundles, 86 int embeddingGrade, 87 bool limitStructures, 88 SListPure<KuratowskiStructure>& output, 89 double randomness, 90 bool avoidE2Minors, 91 bool extractSubgraph, 92 const EdgeArray<int> *edgeCosts = nullptr); 93 94 //! Constructor, for parameters see BoyerMyrvold 95 BoyerMyrvoldPlanar( 96 Graph& g, 97 bool bundles, 98 EmbeddingGrade embeddingGrade, 99 bool limitStructures, 100 SListPure<KuratowskiStructure>& output, 101 double randomness, 102 bool avoidE2Minors, 103 bool extractSubgraph, 104 const EdgeArray<int> *edgeCosts = nullptr) BoyerMyrvoldPlanar(g,bundles,static_cast<int> (embeddingGrade),limitStructures,output,randomness,avoidE2Minors,extractSubgraph,edgeCosts)105 : BoyerMyrvoldPlanar(g, bundles, static_cast<int>(embeddingGrade), limitStructures, output, randomness, avoidE2Minors, extractSubgraph, edgeCosts) 106 {} 107 108 //! Starts the embedding algorithm 109 bool start(); 110 111 //! Flips all nodes of the bicomp with unique, real, rootchild c as necessary 112 /** @param c is the unique rootchild of the bicomp 113 * @param marker is the value which marks nodes as visited 114 * @param visited is the array containing visiting information 115 * @param wholeGraph Iff true, all bicomps of all connected components will be traversed 116 * @param deleteFlipFlags Iff true, the flipping flags will be deleted after flipping 117 */ 118 void flipBicomp( 119 int c, 120 int marker, 121 NodeArray<int>& visited, 122 bool wholeGraph, 123 bool deleteFlipFlags); 124 125 // avoid automatic creation of assignment operator 126 //! Assignment operator is undefined! 127 BoyerMyrvoldPlanar &operator=(const BoyerMyrvoldPlanar &); 128 129 130 //! Seeds the random generator for performing a random DFS. 131 //! If this method is never called the random generator will be seeded by a value 132 //! extracted from the global random generator. seed(const std::minstd_rand rand)133 void seed(const std::minstd_rand rand) { 134 m_rand = rand; 135 } 136 137 protected: 138 //! \name Methods for Walkup and Walkdown 139 //! @{ 140 141 //! Checks whether node \p w is pertinent. \p w has to be non-virtual. pertinent(node w)142 inline bool pertinent(node w) const { 143 OGDF_ASSERT(w!=nullptr); 144 return m_dfi[w] > 0 && (!m_backedgeFlags[w].empty() || !m_pertinentRoots[w].empty()); 145 } 146 147 //! Checks whether real node \p w is internally active while embedding node with DFI \p v internallyActive(node w,int v)148 inline bool internallyActive(node w, int v) const { 149 OGDF_ASSERT(w!=nullptr); 150 return m_dfi[w] > 0 && pertinent(w) && !externallyActive(w, v); 151 } 152 153 //! Checks whether real node \p w is externally active while embedding node with DFI \p v externallyActive(node w,int v)154 inline bool externallyActive(node w, int v) const { 155 OGDF_ASSERT(w!=nullptr); 156 if (m_dfi[w] <= 0) return false; 157 if (m_leastAncestor[w] < v) return true; 158 return !m_separatedDFSChildList[w].empty() && m_lowPoint[m_separatedDFSChildList[w].front()] < v; 159 } 160 161 //! Checks whether real node \p w is inactive while embedding node with DFI \p v inactive(node w,int v)162 inline bool inactive(node w, int v) { 163 OGDF_ASSERT(w!=nullptr); 164 if (m_dfi[w] <= 0) return true; 165 if (!m_backedgeFlags[w].empty() || !m_pertinentRoots[w].empty() 166 || m_leastAncestor[w] < v) return false; 167 return m_separatedDFSChildList[w].empty() || m_lowPoint[m_separatedDFSChildList[w].front()] >= v; 168 } 169 170 //! Checks all dynamic information about a node \p w while embedding node with DFI \p v 171 /** 172 * @return This method returns the following values: 173 * - 0 = inactive 174 * - 1 = internallyActive 175 * - 2 = pertinent and externallyActive 176 * - 3 = externallyActive and not pertinent 177 */ infoAboutNode(node w,int v)178 inline int infoAboutNode(node w, int v) const { 179 OGDF_ASSERT(w!=nullptr); 180 if (m_dfi[w] <= 0) return 0; 181 if (!m_pertinentRoots[w].empty() || !m_backedgeFlags[w].empty()) { 182 // pertinent 183 if (m_leastAncestor[w] < v) return 2; 184 if (m_separatedDFSChildList[w].empty()) return 1; 185 return m_lowPoint[m_separatedDFSChildList[w].front()] < v ? 2 : 1; 186 } else { 187 // not pertinent 188 if (m_leastAncestor[w] < v) return 3; 189 if (m_separatedDFSChildList[w].empty()) return 0; 190 return m_lowPoint[m_separatedDFSChildList[w].front()] < v ? 3 : 0; 191 } 192 } 193 194 //! Walks upon external face in the given \p direction starting at \p w 195 /** If none of the bicomps has been flipped then CW = clockwise and 196 * CCW = counterclockwise holds. In general, the traversaldirection could have 197 * been changed due to flipped components. If this occurs, the 198 * traversaldirection is flipped. 199 */ successorOnExternalFace(node w,int & direction)200 inline node successorOnExternalFace(node w, int& direction) const { 201 OGDF_ASSERT(w!=nullptr); 202 OGDF_ASSERT(w->degree()>0); 203 OGDF_ASSERT(m_link[BoyerMyrvoldPlanar::DirectionCW][w]!=nullptr); 204 OGDF_ASSERT(m_link[BoyerMyrvoldPlanar::DirectionCCW][w]!=nullptr); 205 adjEntry adj = m_link[direction][w]; 206 OGDF_ASSERT(adj->theNode()!=nullptr); 207 208 if (w->degree() > 1) direction = 209 adj==beforeShortCircuitEdge(adj->theNode(),BoyerMyrvoldPlanar::DirectionCCW)->twin(); 210 OGDF_ASSERT(direction || adj==beforeShortCircuitEdge(adj->theNode(),BoyerMyrvoldPlanar::DirectionCW)->twin()); 211 return adj->theNode(); 212 } 213 214 //! Walks upon external face in given \p direction avoiding short circuit edges successorWithoutShortCircuit(node w,int & direction)215 inline node successorWithoutShortCircuit(node w, int& direction) { 216 OGDF_ASSERT(w!=nullptr); 217 OGDF_ASSERT(w->degree()>0); 218 OGDF_ASSERT(m_link[BoyerMyrvoldPlanar::DirectionCW][w]!=nullptr); 219 OGDF_ASSERT(m_link[BoyerMyrvoldPlanar::DirectionCCW][w]!=nullptr); 220 adjEntry adj = beforeShortCircuitEdge(w,direction); 221 OGDF_ASSERT(adj->theNode()!=nullptr); 222 223 if (w->degree() > 1) direction = 224 adj==beforeShortCircuitEdge(adj->theNode(),BoyerMyrvoldPlanar::DirectionCCW)->twin(); 225 OGDF_ASSERT(direction || adj==beforeShortCircuitEdge(adj->theNode(),BoyerMyrvoldPlanar::DirectionCW)->twin()); 226 return adj->theNode(); 227 } 228 229 //! Returns the successornode on the external face in given \p direction 230 /** \p direction is not changed. 231 */ constSuccessorOnExternalFace(node v,int direction)232 inline node constSuccessorOnExternalFace(node v, int direction) { 233 OGDF_ASSERT(v!=nullptr); 234 OGDF_ASSERT(v->degree()>0); 235 return m_link[direction][v]->theNode(); 236 } 237 238 //! Walks upon external face in \p direction avoiding short circuit edges 239 /** \p direction is not changed. 240 */ constSuccessorWithoutShortCircuit(node v,int direction)241 inline node constSuccessorWithoutShortCircuit(node v, int direction) const { 242 OGDF_ASSERT(v!=nullptr); 243 OGDF_ASSERT(v->degree()>0); 244 return beforeShortCircuitEdge(v,direction)->theNode(); 245 } 246 247 //! Returns underlying former adjEntry, if a short circuit edge in \p direction of \p v exists 248 /** Otherwise the common edge is returned. In every case the returned adjEntry 249 * points to the targetnode. 250 */ beforeShortCircuitEdge(node v,int direction)251 inline adjEntry beforeShortCircuitEdge(node v, int direction) const { 252 OGDF_ASSERT(v!=nullptr); 253 return (m_beforeSCE[direction][v]==nullptr) ? m_link[direction][v] : m_beforeSCE[direction][v]; 254 } 255 256 //! Walks upon external face in the given \p direction starting at \p w until an active vertex is reached 257 /** Returns dynamical typeinformation \p info of that endvertex. 258 */ 259 node activeSuccessor(node w, int& direction, int v, int& info) const; 260 261 //! Walks upon external face in the given \p direction (without changing it) until an active vertex is reached 262 /** Returns dynamical typeinformation \p info of that endvertex. But does not change the \p direction. 263 */ constActiveSuccessor(node w,int direction,int v,int & info)264 inline node constActiveSuccessor(node w, int direction, int v, int& info) const { 265 return activeSuccessor(w,direction,v,info); 266 } 267 268 //! Checks, if one ore more wNodes exist between the two stopping vertices \p stopx and \p stopy 269 /** The node \p root is root of the bicomp containing the stopping vertices 270 */ wNodesExist(node root,node stopx,node stopy)271 inline bool wNodesExist(node root, node stopx, node stopy) const { 272 OGDF_ASSERT(root != stopx); 273 OGDF_ASSERT(root != stopy); 274 OGDF_ASSERT(stopx != stopy); 275 int dir = BoyerMyrvoldPlanar::DirectionCCW; 276 bool between = false; 277 while (root != nullptr) { 278 root = successorOnExternalFace(root,dir); 279 if (between && pertinent(root)) { 280 return true; 281 } 282 if (root == stopx || root == stopy) { 283 if (between) { 284 return false; 285 } 286 between = true; 287 } 288 } 289 return false; 290 } 291 292 //! Prints informations about node \p v printNodeInfo(node v)293 inline void printNodeInfo(node v) { 294 std::cout 295 << "\nprintNodeInfo(" << m_dfi[v] << "): " 296 << "CCW=" << m_dfi[constSuccessorOnExternalFace(v, BoyerMyrvoldPlanar::DirectionCCW)] 297 << ",CW=" << m_dfi[constSuccessorOnExternalFace(v, BoyerMyrvoldPlanar::DirectionCW)] 298 << "\tCCWBefore=" << m_dfi[constSuccessorWithoutShortCircuit(v, BoyerMyrvoldPlanar::DirectionCCW)] 299 << ",CWBefore=" << m_dfi[constSuccessorWithoutShortCircuit(v, BoyerMyrvoldPlanar::DirectionCW)] 300 << "\tadjList: "; 301 adjEntry adj; 302 for (adj = v->firstAdj(); adj; adj = adj->succ()) { 303 std::cout << adj->twinNode() << " "; 304 } 305 } 306 307 //! Merges the last two biconnected components saved in \p stack. 308 //! Embeds them iff #m_embeddingGrade != EmbeddingGrade::doNotEmbed. 309 void mergeBiconnectedComponent(ArrayBuffer<int>& stack); 310 311 //! Links (and embeds iff #m_embeddingGrade != EmbeddingGrade::doNotEmbed) backedges from node 312 //! \p v with direction \p v_dir to node \p w with direction \p w_dir. 313 void embedBackedges(const node v, const int v_dir, const node w, const int w_dir); 314 315 //! Creates a short circuit edge from node \p v with direction \p v_dir to node \p w with direction \p w_dir 316 void createShortCircuitEdge(const node v, const int v_dir, 317 const node w, const int w_dir); 318 319 //! Walkup: Builds the pertinent subgraph for the backedge \p back. 320 /** \p back is the backedge between nodes \p v and \p w. \p v is the current node to embed. 321 * All visited nodes are marked with value \p marker. The Function returns the last traversed node. 322 */ 323 node walkup(const node v, const node w, const int marker, const edge back); 324 325 //! Walkdown: Embeds all backedges with DFI \p i as targetnode to node \p v 326 /** 327 * @param i is the DFI of the current vertex to embed 328 * @param v is the virtual node being the root of the bicomp attached to \p i 329 * @param findKuratowskis collects information in order to extract Kuratowski Subdivisions later 330 * @return 1, iff the embedding process found a stopping configuration 331 */ 332 int walkdown(const int i, const node v, FindKuratowskis* findKuratowskis); 333 334 //! Merges unprocessed virtual nodes such as the dfs-roots with their real counterpart 335 void mergeUnprocessedNodes(); 336 337 //! Postprocessing of the graph, so that all virtual vertices are embedded and all bicomps are flipped 338 /** In addition, embedding steps for parallel edges and self-loops are implemented. 339 */ 340 void postProcessEmbedding(); 341 342 //! Starts the embedding phase, which embeds #m_g node by node in descending DFI-order. 343 /** Returns true, if graph is planar, false otherwise. 344 */ 345 bool embed(); 346 347 //! @} 348 349 //! Input graph, which can be altered 350 Graph& m_g; 351 352 //! \name Some parameters... see BoyerMyrvold for further options 353 //! @{ 354 const bool m_bundles; 355 const int m_embeddingGrade; 356 const bool m_limitStructures; 357 const double m_randomness; 358 const bool m_avoidE2Minors; 359 const EdgeArray<int> *m_edgeCosts; 360 std::minstd_rand m_rand; 361 //! @} 362 363 //! Flag for extracting a planar subgraph instead of testing for planarity 364 bool m_extractSubgraph = true; 365 366 //! The whole number of bicomps, which have to be flipped 367 int m_flippedNodes; 368 369 //! \name Members from BoyerMyrvoldInit 370 //! @{ 371 372 //! Link to non-virtual vertex of a virtual Vertex. 373 /** A virtual vertex has negative DFI of the DFS-Child of related non-virtual Vertex 374 */ 375 NodeArray<node> m_realVertex; 376 377 //! The one and only DFI-NodeArray 378 NodeArray<int> m_dfi; 379 380 //! Returns appropriate node from given DFI 381 Array<node> m_nodeFromDFI; 382 383 //! Links to opposite adjacency entries on external face in clockwise resp. ccw order 384 /** m_link[0]=CCW, m_link[1]=CW 385 */ 386 NodeArray<adjEntry> m_link[2]; 387 388 //! Links for short circuit edges. 389 /** If short circuit edges are introduced, the former adjEntries to the neighbors 390 * have to be saved here for embedding and merging purposes. If there is no 391 * short circuit edge, this adjEntry is nullptr. 392 */ 393 NodeArray<adjEntry> m_beforeSCE[2]; 394 395 //! The adjEntry which goes from DFS-parent to current vertex 396 NodeArray<adjEntry> m_adjParent; 397 398 //! The DFI of the least ancestor node over all backedges 399 /** If no backedge exists, the least ancestor is the DFI of that node itself 400 */ 401 NodeArray<int> m_leastAncestor; 402 403 //! Contains the type of each edge 404 EdgeArray<BoyerMyrvoldEdgeType> m_edgeType; 405 406 //! The lowpoint of each node 407 NodeArray<int> m_lowPoint; 408 409 //! The highest DFI in a subtree with node as root 410 NodeArray<int> m_highestSubtreeDFI; 411 412 //! A list to all separated DFS-children of node 413 /** The list is sorted by lowpoint values (in linear time) 414 */ 415 NodeArray<ListPure<node> > m_separatedDFSChildList; 416 417 //! Pointer to node contained in the DFSChildList of his parent, if exists. 418 /** If node isn't in list or list doesn't exist, the pointer is set to nullptr. 419 */ 420 NodeArray<ListIterator<node> > m_pNodeInParent; 421 422 //! @} 423 //! \name Members for Walkup and Walkdown 424 //! @{ 425 426 //! This Array keeps track of all vertices that are visited by current walkup 427 NodeArray<int> m_visited; 428 429 //! Identifies the rootnode of the child bicomp the given backedge points to 430 EdgeArray<node> m_pointsToRoot; 431 432 /** 433 * Stores for each (real) non-root vertex v with which backedge it was 434 * visited during the walkup. This is done to later identify the root vertex 435 * of the bicomp v belongs to. 436 */ 437 NodeArray<edge> m_visitedWithBackedge; 438 439 /** 440 * Stores for each (virtual) bicomp root how many backedges to its bicomp 441 * still have to be embedded. The value is set during the walkup, and it is 442 * used and decreased while embedding backedges during the walkdown. 443 */ 444 NodeArray<int> m_numUnembeddedBackedgesInBicomp; 445 446 //! Iff true, the node is the root of a bicomp which has to be flipped. 447 /** The DFS-child of every bicomp root vertex is unique. if a bicomp 448 * is flipped, this DFS-child is marked to check whether the bicomp 449 * has to be flipped or not. 450 */ 451 NodeArray<bool> m_flipped; 452 453 //! Holds information, if node is the source of a backedge. 454 /** This information refers to the adjEntries on the targetnode 455 * and is used during the walkdown 456 */ 457 NodeArray<SListPure<adjEntry> > m_backedgeFlags; 458 459 //! List of virtual bicomp roots, that are pertinent to the current embedded node 460 NodeArray<SListPure<node> > m_pertinentRoots; 461 462 //! Data structure for the Kuratowski subdivisions, which will be returned 463 SListPure<KuratowskiStructure>& m_output; 464 465 //! @} 466 }; 467 468 inline bool operator > (int lhs, BoyerMyrvoldPlanar::EmbeddingGrade rhs) { 469 return lhs > static_cast<int>(rhs); 470 } 471 472 inline bool operator == (int lhs, BoyerMyrvoldPlanar::EmbeddingGrade rhs) { 473 return lhs == static_cast<int>(rhs); 474 } 475 476 inline bool operator != (int lhs, BoyerMyrvoldPlanar::EmbeddingGrade rhs) { 477 return lhs != static_cast<int>(rhs); 478 } 479 480 inline bool operator <= (int lhs, BoyerMyrvoldPlanar::EmbeddingGrade rhs) { 481 return lhs <= static_cast<int>(rhs); 482 } 483 484 } 485