![]() |
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 ///@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