Tulip  5.7.4
Large graphs analysis and drawing
TreeTest.h
1 /*
2  *
3  * This file is part of Tulip (https://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/tulipconf.h>
24 
25 namespace tlp {
26 
27 class Graph;
28 class PluginProgress;
29 struct node;
30 
31 /**
32  * @ingroup Checks
33  * @brief Performs test to check whether a graph is a simple or rooted tree.
34  * From wikipedia: "A tree is an undirected graph in which any two vertices are connected by exactly
35  *one simple path."
36  * Free trees have no designated root, while rooted trees do.
37  **/
38 class TLP_SCOPE TreeTest {
39 public:
40  /**
41  * @brief Checks if the graph is a rooted tree (i.e. one node is designated as the root).
42  *
43  * @param graph The graph to check is a tree.
44  * @return bool True if the graph is a tree, false otherwise.
45  **/
46  static bool isTree(const Graph *graph);
47 
48  /**
49  * Returns true if the graph is a topological tree
50  * (i.e. if the graph was undirected, there would be no cycle),
51  * false otherwise.
52  */
53  /**
54  * @brief Checks if the graph is a topological tree (i.e. if the graph was undirected, there would
55  *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
80  *subgraph, adds a simple source and returns the clone.
81  *
82  * @param graph The graph to compute a tree on.
83  * @param pluginProgress reports progress on the computation. Defaults to 0.
84  * @return :Graph* If the input graph is a rooted tree, returns it as is, otherwise a clone
85  *subgraph transformed into a rooted tree.
86  **/
87  static Graph *computeTree(Graph *graph, PluginProgress *pluginProgress = nullptr);
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
97  *graph->getRoot()->delNode()).
98  **/
99  static void cleanComputedTree(Graph *graph, Graph *tree);
100 };
101 } // namespace tlp
102 #endif
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:38
static void cleanComputedTree(Graph *graph, Graph *tree)
Removes subgraphs created during tree computation. If graph and tree are the same graph,...
static bool isFreeTree(const Graph *graph)
Checks if the graph is a topological tree (i.e. if the graph was undirected, there would be no cycle)...
static Graph * computeTree(Graph *graph, PluginProgress *pluginProgress=nullptr)
Computes a rooted tree from the graph. If the graph is a rooted tree, the input graph is returned as ...
static void makeRootedTree(Graph *freeTree, node root)
Makes a free tree into a rooted tree.
static bool isTree(const Graph *graph)
Checks if the graph is a rooted tree (i.e. one node is designated as the root).
The node struct represents a node in a Graph object.
Definition: Node.h:40