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 00021 #ifndef TULIP_CONNECTEDTEST_H 00022 #define TULIP_CONNECTEDTEST_H 00023 00024 #include <set> 00025 #include <vector> 00026 #include <tulip/tuliphash.h> 00027 #include <tulip/Observable.h> 00028 #include <tulip/Graph.h> 00029 00030 namespace tlp { 00031 00032 /** 00033 * @ingroup Checks 00034 * @brief @brief Performs a test of connexity on the graph, and provides a function to make a graph connected. 00035 * From Wikipedia: "A graph is said to be connected if every pair of vertices in the graph are connected." (i.e. there is a path between every pair of vertices). 00036 **/ 00037 class TLP_SCOPE ConnectedTest : public Observable { 00038 public: 00039 00040 /** 00041 * @brief Checks if a graph is connected (i.e. there is a path between every pair of vertices). 00042 * 00043 * @param graph The graph to check. 00044 * @return bool True if the graph is connected, false otherwise. 00045 **/ 00046 static bool isConnected(const Graph* const graph); 00047 00048 /** 00049 * @brief If the graph is not connected, adds edges to make it connected. 00050 * 00051 * @param graph The graph to make connected. 00052 * @param addedEdges The edges that were added to make it connected. 00053 * @return void 00054 **/ 00055 static void makeConnected(Graph *graph, std::vector<edge>& addedEdges); 00056 00057 /** 00058 * @brief Gets the number of connected components in the graph. 00059 * 00060 * @param graph The graph in which to count the number of connected components. 00061 * @return unsigned int The number of connected componments. 00062 **/ 00063 static unsigned int numberOfConnectedComponents(const Graph* const graph); 00064 00065 /** 00066 * @brief Computes the sets of connected components and stores the result in the components vector. 00067 * 00068 * @param graph The graph on which to compute connected components. 00069 * @param components The components that were found. It is passed as a reference to avoid copying the data when returning. 00070 * @return void 00071 * @note The components parameter can be returned with c++11 thanks to move constructors without performance loss, chenge this function once c++11 compilers are used. 00072 **/ 00073 static void computeConnectedComponents(const Graph *graph, std::vector< std::set<node> >& components); 00074 00075 private: 00076 ConnectedTest(); 00077 00078 00079 /** 00080 * @brief Makes the graph connected. 00081 * 00082 * @param graph The graph to make connected. 00083 * @param toLink The nodes that need to be linked so the graph is connected. 00084 * @return void 00085 **/ 00086 void connect(const Graph * const, std::vector<node>& toLink); 00087 00088 /** 00089 * @brief check if the graph is biconnected. 00090 * 00091 * @param graph the graph to check. 00092 * @return bool true if the graph is connected, false otherwise. 00093 **/ 00094 bool compute(const Graph * const); 00095 00096 //override of Observable::treatEvent to remove the cached result for a graph if it is modified. 00097 virtual void treatEvent(const Event&); 00098 00099 /** 00100 * @brief Singleton instance of this class. 00101 **/ 00102 static ConnectedTest * instance; 00103 /** 00104 * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap. 00105 **/ 00106 TLP_HASH_MAP<const Graph*,bool> resultsBuffer; 00107 }; 00108 00109 } 00110 00111 #endif