Tulip
4.6.0
Better Visualization Through Research
|
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