Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/TriconnectedTest.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_TRICONNECTEDTEST_H
00023 #define TULIP_TRICONNECTEDTEST_H
00024 
00025 #include <tulip/tuliphash.h>
00026 #include <tulip/Observable.h>
00027 #include <tulip/Graph.h>
00028 
00029 namespace tlp {
00030 
00031 /**
00032  * @ingroup Checks
00033  * @brief Provides functions to test if a graph is Triconnected.
00034  **/
00035 class TLP_SCOPE TriconnectedTest : private Observable {
00036 public:
00037 
00038   /**
00039    * Returns true if the graph is triconnected (i.e. a connected graph such that deleting any two nodes (and incident edges)
00040    * results in a graph that is still connected), false otherwise.
00041    */
00042   /**
00043    * @brief Checks if the graph is triconnected.
00044    * Creates a clone sugraph in which to operate, then iterates over the nodes, and deletes them.
00045    * Once the node is deleted, checks if the graph is biconnected.
00046    * If it is not, then the graph is not triconnected.
00047    * If it is, adds back the node and its edges.
00048    *
00049    * @param graph The graph to check is triconnected.
00050    * @return bool True if the graph is triconnected, false otherwise.
00051    **/
00052   static bool isTriconnected(Graph *graph);
00053 
00054 private:
00055   TriconnectedTest();
00056 
00057   bool compute(tlp::Graph* graph);
00058   // override Observable::treatEvent
00059   void treatEvent(const Event&);
00060 
00061   /**
00062    * @brief Singleton instance of this class.
00063    **/
00064   static TriconnectedTest * instance;
00065   /**
00066    * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap.
00067    **/
00068   TLP_HASH_MAP<const Graph*, bool> resultsBuffer;
00069 };
00070 
00071 
00072 }
00073 #endif
00074 ///@endcond
 All Classes Files Functions Variables Enumerations Enumerator Properties