Tulip  4.4.0
Better Visualization Through Research
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Groups Pages
OuterPlanarTest.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux 1 and Inria Bordeaux - Sud Ouest
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef OUTERPLANARTEST_H
22 #define OUTERPLANARTEST_H
23 
24 #include <tulip/tuliphash.h>
25 #include <tulip/Observable.h>
26 #include <tulip/Graph.h>
27 
28 namespace tlp {
29 struct edge;
30 struct node;
31 
32 /**
33  * @ingroup Checks
34  * @brief Provides functions to test if a graph is Outer Planar.
35  *
36  * 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.
37  * 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."
38  **/
39 class TLP_SCOPE OuterPlanarTest : private Observable {
40 public:
41 
42  /**
43  * Returns true if the graph is outerplanar (i.e. a graph with an embedding
44  * in the plane such that all vertices belong to the unbounded face of the embedding),
45  * false otherwise.
46  */
47  /**
48  * @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).
49  *
50  * @param graph The graph to check.
51  * @return bool True if the graph is outer planar, false otherwise.
52  * @note this cannot be const as it uses the planarity test, which is not const and would be complex (impossible?) to make const.
53  **/
54  static bool isOuterPlanar(Graph *graph);
55 
56 private:
57  OuterPlanarTest() {}
58  // override Observable::treatEvent
59  void treatEvent(const Event&);
60 
61  bool compute(Graph *graph);
62 
63  /**
64  * @brief Singleton instance of this class.
65  **/
66  static OuterPlanarTest* instance;
67  /**
68  * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap.
69  **/
70  TLP_HASH_MAP<const Graph*, bool> resultsBuffer;
71 };
72 
73 }
74 
75 #endif
76 ///@endcond