![]() |
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 #ifndef OUTERPLANARTEST_H 00022 #define OUTERPLANARTEST_H 00023 00024 #include <tulip/tuliphash.h> 00025 #include <tulip/Observable.h> 00026 #include <tulip/Graph.h> 00027 00028 namespace tlp { 00029 struct edge; 00030 struct node; 00031 00032 /** 00033 * @ingroup Checks 00034 * @brief Provides functions to test if a graph is Outer Planar. 00035 * 00036 * From Wikipedia: "An OuterPlanar Graph is a graph that can be drawn in the plane without crossings in such a way that all of the vertices belong to the unbounded face of the drawing. 00037 * Alternatively, a graph G is outerplanar if the graph formed from G by adding a new vertex, with edges connecting it to all the other vertices, is a planar graph." 00038 **/ 00039 class TLP_SCOPE OuterPlanarTest : private Observable { 00040 public: 00041 00042 /** 00043 * Returns true if the graph is outerplanar (i.e. a graph with an embedding 00044 * in the plane such that all vertices belong to the unbounded face of the embedding), 00045 * false otherwise. 00046 */ 00047 /** 00048 * @brief Checks if a graph is outer planar (i.e. a graph with an embedding in the plane such that all vertices belong to the unbounded face of the embedding). 00049 * 00050 * @param graph The graph to check. 00051 * @return bool True if the graph is outer planar, false otherwise. 00052 * @note this cannot be const as it uses the planarity test, which is not const and would be complex (impossible?) to make const. 00053 **/ 00054 static bool isOuterPlanar(Graph *graph); 00055 00056 private: 00057 OuterPlanarTest() {} 00058 // override Observable::treatEvent 00059 void treatEvent(const Event&); 00060 00061 bool compute(Graph *graph); 00062 00063 /** 00064 * @brief Singleton instance of this class. 00065 **/ 00066 static OuterPlanarTest* instance; 00067 /** 00068 * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap. 00069 **/ 00070 TLP_HASH_MAP<const Graph*, bool> resultsBuffer; 00071 }; 00072 00073 } 00074 00075 #endif 00076 ///@endcond