Tulip  4.8.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
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/Graph.h>
28 
29 namespace tlp {
30 
31 class PluginProgress;
32 /**
33  * @ingroup Checks
34  * @brief Performs test to check whether a graph is a simple or rooted tree.
35  * From wikipedia: "A tree is an undirected graph in which any two vertices are connected by exactly one simple path."
36  * Free trees have no designated root, while rooted trees do.
37  **/
38 class TLP_SCOPE TreeTest : private Observable {
39 public:
40 
41  /**
42  * @brief Checks if the graph is a rooted tree (i.e. one node is designated as the root).
43  *
44  * @param graph The graph to check is a tree.
45  * @return bool True if the graph is a tree, false otherwise.
46  **/
47  static bool isTree(const Graph *graph);
48 
49  /**
50  * Returns true if the graph is a topological tree
51  * (i.e. if the graph was undirected, there would be no cycle),
52  * false otherwise.
53  */
54  /**
55  * @brief Checks if the graph is a topological tree (i.e. if the graph was undirected, there would be no cycle).
56  *
57  * @param graph The graph to check is a free tree.
58  * @return bool True if the graph is a free tree, false otherwise.
59  **/
60  static bool isFreeTree(const Graph *graph);
61 
62  /**
63  * Turns a free tree into a rooted tree.
64  */
65  /**
66  * @brief Makes a free tree into a rooted tree.
67  *
68  * @param freeTree The free tree to make a rooted tree.
69  * @param root The root of the tree.
70  * @return void
71  **/
72  static void makeRootedTree(Graph *freeTree, node root);
73 
74  /**
75  * @brief Computes a rooted tree from the graph.
76  * If the graph is a rooted tree, the input graph is returned as is.
77  * If the graphs is a free tree, a rooted clone subgraph is returned.
78  * If the graph is connected, a rooted spanning tree of a clone subgraph is returned
79  * 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.
80  *
81  * @param graph The graph to compute a tree on.
82  * @param pluginProgress reports progress on the computation. Defaults to 0.
83  * @return :Graph* If the input graph is a rooted tree, returns it as is, otherwise a clone subgraph transformed into a rooted tree.
84  **/
85  static Graph *computeTree(Graph* graph, PluginProgress *pluginProgress = 0);
86 
87  /**
88  * @brief Removes subgraphs created during tree computation.
89  * If graph and tree are the same graph, does nothing.
90  *
91  * @param graph The graph to clean from tree subgraphs.
92  * @param tree The tree subgraph to remove.
93  * @return void
94  * @note this deletes the root of the graph from graph's root (i.e. calls graph->getRoot()->delNode()).
95  **/
96  static void cleanComputedTree(Graph *graph, Graph *tree);
97 
98 private:
99  TreeTest();
100 
101  bool compute(const Graph * graph);
102 
103  bool isFreeTree (const Graph *graph, node curRoot);
104 
105  // override Observable::treatEvent
106  void treatEvent(const Event&);
107 
108  /**
109  * @brief Singleton instance of this class.
110  **/
111  static TreeTest * instance;
112  /**
113  * @brief Stored results for graphs. When a graph is updated, its entry is removed from the hashmap.
114  **/
115  TLP_HASH_MAP<const Graph*,bool> resultsBuffer;
116 };
117 
118 
119 }
120 #endif
121 ///@endcond