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