Tulip  4.1.0
Better Visualization Through Research
 All Classes Files Functions Variables Enumerations Enumerator Properties Groups Pages
TreeTest.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux 1 and Inria Bordeaux - Sud Ouest
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 
22 #ifndef TULIP_TREETEST_H
23 #define TULIP_TREETEST_H
24 
25 #include <tulip/tuliphash.h>
26 #include <tulip/Observable.h>
27 #include <tulip/MutableContainer.h>
28 #include <tulip/PluginProgress.h>
29 
30 namespace tlp {
31 
32 class Graph;
33 
34 /**
35  * @ingroup Checks
36  * @brief Performs test to check whether a graph is a simple or rooted tree.
37  * From wikipedia: "A tree is an undirected graph in which any two vertices are connected by exactly one simple path."
38  * Free trees have no designated root, while rooted trees do.
39  **/
40 class TLP_SCOPE TreeTest : private Observable {
41 public:
42 
43  /**
44  * @brief Checks if the graph is a rooted tree (i.e. one node is designated as the root).
45  *
46  * @param graph The graph to check is a tree.
47  * @return bool True if the graph is a tree, false otherwise.
48  **/
49  static bool isTree(const Graph *graph);
50 
51  /**
52  * Returns true if the graph is a topological tree
53  * (i.e. if the graph was undirected, there would be no cycle),
54  * false otherwise.
55  */
56  /**
57  * @brief Checks if the graph is a topological tree (i.e. if the graph was undirected, there would be no cycle).
58  *
59  * @param graph The graph to check is a free tree.
60  * @return bool True if the graph is a free tree, false otherwise.
61  **/
62  static bool isFreeTree(const Graph *graph);
63 
64  /**
65  * Turns a free tree into a rooted tree.
66  */
67  /**
68  * @brief Makes a free tree into a rooted tree.
69  *
70  * @param freeTree The free tree to make a rooted tree.
71  * @param root The root of the tree.
72  * @return void
73  **/
74  static void makeRootedTree(Graph *freeTree, node root);
75 
76  /**
77  * @brief Computes a rooted tree from the graph.
78  * If the graph is a rooted tree, the input graph is returned as is.
79  * If the graphs is a free tree, a rooted clone subgraph is returned.
80  * If the graph is connected, a rooted spanning tree of a clone subgraph is returned
81  * 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.
82  *
83  * @param graph The graph to compute a tree on.
84  * @param pluginProgress reports progress on the computation. Defaults to 0.
85  * @return :Graph* If the input graph is a rooted tree, returns it as is, otherwise a clone subgraph transformed into a rooted tree.
86  **/
87  static Graph *computeTree(Graph* graph, PluginProgress *pluginProgress = 0);
88 
89  /**
90  * @brief Removes subgraphs created during tree computation.
91  * If graph and tree are the same graph, does nothing.
92  *
93  * @param graph The graph to clean from tree subgraphs.
94  * @param tree The tree subgraph to remove.
95  * @return void
96  * @note this deletes the root of the graph from graph's root (i.e. calls graph->getRoot()->delNode()).
97  **/
98  static void cleanComputedTree(Graph *graph, Graph *tree);
99 
100 private:
101  TreeTest();
102 
103  bool compute(const Graph * graph);
104 
105  bool isFreeTree (const Graph *graph, node curRoot);
106 
107  // override Observable::treatEvent
108  void treatEvent(const Event&);
109 
110  /**
111  * @brief Singleton instance of this class.
112  **/
113  static TreeTest * instance;
114  /**
115  * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap.
116  **/
117  TLP_HASH_MAP<unsigned long,bool> resultsBuffer;
118 };
119 
120 
121 }
122 #endif
123 ///@endcond