Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/ConnectedTest.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 
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
 All Classes Files Functions Variables Enumerations Enumerator Properties