Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/BiconnectedTest.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 
00020 #ifndef TULIP_BICONNEX_H
00021 #define TULIP_BICONNEX_H
00022 
00023 #include <tulip/MutableContainer.h>
00024 #include <tulip/Observable.h>
00025 #include <tulip/Graph.h>
00026 
00027 namespace tlp {
00028 
00029 /**
00030  * @ingroup Checks
00031  * @brief Performs a test of biconnexity on the graph, and provides a function to make a graph biconnected.
00032  * From Wikipedia: "A biconnected graph is connected and nonseparable, meaning that if any vertex were to be removed, the graph will remain connected."
00033  **/
00034 class TLP_SCOPE BiconnectedTest : private Observable {
00035 
00036 public:
00037   /**
00038    * @brief Checks whether the graph is biconnected (i.e. removing one edge does not disconnect the graph, at least two must be removed).
00039    *
00040    * @param graph The graph to check for biconnectivity.
00041    * @return bool True if the graph is biconnected, false otherwise.
00042    **/
00043   static bool isBiconnected(const Graph *graph);
00044 
00045   /**
00046    * If the graph is not biconnected, adds edges in order to make the graph
00047    * biconnected. The new edges are added in addedEdges.
00048    */
00049   /**
00050    * @brief Adds edges to make the graph biconnected.
00051    *
00052    * @param graph The graph to make biconnected.
00053    * @param addedEdges The edges that were added in the process.
00054    * @return void
00055    **/
00056   static void makeBiconnected(Graph *graph, std::vector<edge>& addedEdges);
00057 
00058 private:
00059   BiconnectedTest();
00060 
00061   /**
00062    * @brief Makes the graph biconnected.
00063    *
00064    * @param graph The graph to make biconnected.
00065    * @param addedEdges The edges that were added to make it biconnected.
00066    * @return void
00067    **/
00068   void connect(Graph * graph, std::vector<edge>& addedEdges);
00069 
00070   /**
00071    * @brief check if the graph is biconnected.
00072    *
00073    * @param graph the graph to check.
00074    * @return bool true if the graph is biconnected, false otherwise.
00075    **/
00076   bool compute(const Graph * graph);
00077 
00078   //override of Observable::treatEvent to remove the cached result for a graph if it is modified.
00079   virtual void treatEvent(const Event&);
00080 
00081   /**
00082    * @brief Singleton instance of this class.
00083    **/
00084   static BiconnectedTest * instance;
00085   /**
00086    * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap.
00087    **/
00088   TLP_HASH_MAP<const Graph*,bool> resultsBuffer;
00089 };
00090 }
00091 
00092 #endif
 All Classes Files Functions Variables Enumerations Enumerator Properties