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