Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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
25namespace tlp {
26
27class Graph;
28class PluginProgress;
29struct 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 **/
38class TLP_SCOPE TreeTest {
39public:
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 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 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 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