![]() |
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_TREETEST_H 00023 #define TULIP_TREETEST_H 00024 00025 #include <tulip/tuliphash.h> 00026 #include <tulip/Observable.h> 00027 #include <tulip/Graph.h> 00028 00029 namespace tlp { 00030 00031 class PluginProgress; 00032 /** 00033 * @ingroup Checks 00034 * @brief Performs test to check whether a graph is a simple or rooted tree. 00035 * From wikipedia: "A tree is an undirected graph in which any two vertices are connected by exactly one simple path." 00036 * Free trees have no designated root, while rooted trees do. 00037 **/ 00038 class TLP_SCOPE TreeTest : private Observable { 00039 public: 00040 00041 /** 00042 * @brief Checks if the graph is a rooted tree (i.e. one node is designated as the root). 00043 * 00044 * @param graph The graph to check is a tree. 00045 * @return bool True if the graph is a tree, false otherwise. 00046 **/ 00047 static bool isTree(const Graph *graph); 00048 00049 /** 00050 * Returns true if the graph is a topological tree 00051 * (i.e. if the graph was undirected, there would be no cycle), 00052 * false otherwise. 00053 */ 00054 /** 00055 * @brief Checks if the graph is a topological tree (i.e. if the graph was undirected, there would be no cycle). 00056 * 00057 * @param graph The graph to check is a free tree. 00058 * @return bool True if the graph is a free tree, false otherwise. 00059 **/ 00060 static bool isFreeTree(const Graph *graph); 00061 00062 /** 00063 * Turns a free tree into a rooted tree. 00064 */ 00065 /** 00066 * @brief Makes a free tree into a rooted tree. 00067 * 00068 * @param freeTree The free tree to make a rooted tree. 00069 * @param root The root of the tree. 00070 * @return void 00071 **/ 00072 static void makeRootedTree(Graph *freeTree, node root); 00073 00074 /** 00075 * @brief Computes a rooted tree from the graph. 00076 * If the graph is a rooted tree, the input graph is returned as is. 00077 * If the graphs is a free tree, a rooted clone subgraph is returned. 00078 * If the graph is connected, a rooted spanning tree of a clone subgraph is returned 00079 * If the graph is not connected, computes a tree for each of the connected components of a clone subgraph, adds a simple source and returns the clone. 00080 * 00081 * @param graph The graph to compute a tree on. 00082 * @param pluginProgress reports progress on the computation. Defaults to 0. 00083 * @return :Graph* If the input graph is a rooted tree, returns it as is, otherwise a clone subgraph transformed into a rooted tree. 00084 **/ 00085 static Graph *computeTree(Graph* graph, PluginProgress *pluginProgress = 0); 00086 00087 /** 00088 * @brief Removes subgraphs created during tree computation. 00089 * If graph and tree are the same graph, does nothing. 00090 * 00091 * @param graph The graph to clean from tree subgraphs. 00092 * @param tree The tree subgraph to remove. 00093 * @return void 00094 * @note this deletes the root of the graph from graph's root (i.e. calls graph->getRoot()->delNode()). 00095 **/ 00096 static void cleanComputedTree(Graph *graph, Graph *tree); 00097 00098 private: 00099 TreeTest(); 00100 00101 bool compute(const Graph * graph); 00102 00103 bool isFreeTree (const Graph *graph, node curRoot); 00104 00105 // override Observable::treatEvent 00106 void treatEvent(const Event&); 00107 00108 /** 00109 * @brief Singleton instance of this class. 00110 **/ 00111 static TreeTest * instance; 00112 /** 00113 * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap. 00114 **/ 00115 TLP_HASH_MAP<const Graph*,bool> resultsBuffer; 00116 }; 00117 00118 00119 } 00120 #endif 00121 ///@endcond