Tulip
5.5.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/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
private
:
102
static
bool
isFreeTree(
const
Graph
*graph,
node
curRoot);
103
};
104
}
// namespace tlp
105
#endif
tlp::Graph
Definition:
Graph.h:234
tlp::TreeTest
Performs test to check whether a graph is a simple or rooted tree. From wikipedia: "A tree is an undi...
Definition:
TreeTest.h:38
tlp
Definition:
AbstractProperty.h:34
tlp::node
The node struct represents a node in a Graph object.
Definition:
Node.h:40
tlp::PluginProgress
PluginProcess subclasses are meant to notify about the progress state of some process (typically a pl...
Definition:
PluginProgress.h:83
library
tulip-core
include
tulip
TreeTest.h
Generated on Tue Dec 8 2020 14:25:39 for Tulip by
1.8.17