Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/PlanarityTest.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 
00022 #ifndef TULIP_PLANARITYTESTX_H
00023 #define TULIP_PLANARITYTESTX_H
00024 
00025 #include <list>
00026 #include <tulip/tulipconf.h>
00027 #include <tulip/tuliphash.h>
00028 #include <tulip/Observable.h>
00029 #include <tulip/Edge.h>
00030 #include <tulip/Graph.h>
00031 
00032 namespace tlp {
00033 
00034 /**
00035  * @ingroup Checks
00036  * @brief performs tests to check zhether a graph is planar.
00037  * 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."
00038  **/
00039 class TLP_SCOPE PlanarityTest : private Observable {
00040 public:
00041   /*
00042     The set of edges of the graph is modified during the execution of
00043     the methods below. If you call one of them while iterating
00044     on the edges of the graph, be careful to use a StableIterator
00045     to avoid any possible invalidation of the iterator.
00046   */
00047 
00048   /**
00049    * @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).
00050    *
00051    * @param graph The graph to check for planarity.
00052    * @return bool True if the graph is planar, false otherwise.
00053    * @note The graph is made biconnected to ease (?) the computation.
00054    **/
00055   static bool isPlanar(Graph *graph);
00056 
00057   /**
00058    * Returns true if the current embedding of the graph is planar, false otherwise.
00059    */
00060   /**
00061    * @brief Checks if the graph is plane (or a planar embedding).
00062    * 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.
00063    *
00064    * @param graph The graph to check for a planar e;bedding.
00065    * @return bool True if the graph is a planar embedding, false otherwise.
00066    **/
00067   static bool isPlanarEmbedding(const Graph *graph);
00068 
00069   /**
00070    * @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.
00071    * This modifies the order of the edges around the nodes.
00072    *
00073    * @param graph The graph to make a planar embedding of.
00074    * @return bool True if the graph is planar, false otherwise.
00075    **/
00076   static bool planarEmbedding(Graph *graph);
00077 
00078   /**
00079    * @brief Computes a list of edges that prevent the graph from being planar (i.e. part of the minor of K3,3 or K5).
00080    *
00081    * @param graph The graph on which to compute the obstruction edges.
00082    * @return :list< tlp::edge, std::allocator< tlp::edge > > The obstruction edges.
00083    **/
00084   static std::list<edge> getObstructionsEdges(Graph *graph);
00085 
00086 private:
00087   PlanarityTest() {}
00088   //override of Observable::treatEvent to remove the cached result for a graph if it is modified.
00089   void treatEvent(const Event&);
00090   bool compute(Graph *graph);
00091 
00092   /**
00093    * @brief Singleton instance of this class.
00094    **/
00095   static PlanarityTest * instance;
00096   /**
00097    * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap.
00098    **/
00099   TLP_HASH_MAP<const Graph*, bool> resultsBuffer;
00100 };
00101 
00102 
00103 }
00104 #endif
00105 ///@endcond
 All Classes Files Functions Variables Enumerations Enumerator Properties