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