Tulip  5.0.0
Large graphs analysis and drawing
PlanarityTest.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
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 
20 #ifndef TULIP_PLANARITYTESTX_H
21 #define TULIP_PLANARITYTESTX_H
22 
23 #include <list>
24 #include <tulip/tulipconf.h>
25 #include <tulip/tuliphash.h>
26 #include <tulip/Observable.h>
27 #include <tulip/Edge.h>
28 #include <tulip/Graph.h>
29 
30 namespace tlp {
31 
32 /**
33  * @ingroup Checks
34  * @brief performs tests to check whether a graph is planar.
35  * From wikipedia: "A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints."
36  **/
37 class TLP_SCOPE PlanarityTest : private Observable {
38 public:
39  /*
40  The set of edges of the graph is modified during the execution of
41  the methods below. If you call one of them while iterating
42  on the edges of the graph, be careful to use a StableIterator
43  to avoid any possible invalidation of the iterator.
44  */
45 
46  /**
47  * @brief Checks whether the graph is planar (i.e. the graph can be drawn on the plane in such a way that no edges cross each other).
48  *
49  * @param graph The graph to check for planarity.
50  * @return bool True if the graph is planar, false otherwise.
51  * @note The graph is made biconnected to ease (?) the computation.
52  **/
53  static bool isPlanar(Graph *graph);
54 
55  /**
56  * Returns true if the current embedding of the graph is planar, false otherwise.
57  */
58  /**
59  * @brief Checks if the graph is plane (or a planar embedding).
60  * A planar graph *can* be drawn such as no edges cross each other, a plane graph *is* drawn such as no edges cross each other.
61  *
62  * @param graph The graph to check for a planar e;bedding.
63  * @return bool True if the graph is a planar embedding, false otherwise.
64  **/
65  static bool isPlanarEmbedding(const Graph *graph);
66 
67  /**
68  * @brief Makes a planar graph a planar embedding, i.e. makes a graph so that no edges cross each other if it is known to be possible.
69  * This modifies the order of the edges around the nodes.
70  *
71  * @param graph The graph to make a planar embedding of.
72  * @return bool True if the graph is planar, false otherwise.
73  **/
74  static bool planarEmbedding(Graph *graph);
75 
76  /**
77  * @brief Computes a list of edges that prevent the graph from being planar (i.e. part of the minor of K3,3 or K5).
78  *
79  * @param graph The graph on which to compute the obstruction edges.
80  * @return :list< tlp::edge, std::allocator< tlp::edge > > The obstruction edges.
81  **/
82  static std::list<edge> getObstructionsEdges(Graph *graph);
83 
84 private:
85  PlanarityTest() {}
86  //override of Observable::treatEvent to remove the cached result for a graph if it is modified.
87  void treatEvent(const Event&);
88  bool compute(Graph *graph);
89 
90  /**
91  * @brief Singleton instance of this class.
92  **/
93  static PlanarityTest * instance;
94  /**
95  * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap.
96  **/
97  TLP_HASH_MAP<const Graph*, bool> resultsBuffer;
98 };
99 
100 
101 }
102 #endif
performs tests to check whether a graph is planar. From wikipedia: "A planar graph is a graph that ca...
Definition: PlanarityTest.h:37
Event is the base class for all events used in the Observation mechanism.
Definition: Observable.h:47
The Observable class is the base of Tulip&#39;s observation system.
Definition: Observable.h:123