Tulip  5.7.4
Large graphs analysis and drawing
tlp::TreeTest Class Reference

#include <TreeTest.h>

Static Public Member Functions

static void cleanComputedTree (Graph *graph, Graph *tree)
 
static GraphcomputeTree (Graph *graph, PluginProgress *pluginProgress=nullptr)
 
static bool isFreeTree (const Graph *graph)
 
static bool isTree (const Graph *graph)
 
static void makeRootedTree (Graph *freeTree, node root)
 

Detailed Description

Performs test to check whether a graph is a simple or rooted tree. From wikipedia: "A tree is an undirected graph in which any two vertices are connected by exactly one simple path." Free trees have no designated root, while rooted trees do.

Definition at line 38 of file TreeTest.h.

Member Function Documentation

◆ cleanComputedTree()

static void tlp::TreeTest::cleanComputedTree ( Graph graph,
Graph tree 
)
static

Removes subgraphs created during tree computation. If graph and tree are the same graph, does nothing.

Parameters
graphThe graph to clean from tree subgraphs.
treeThe tree subgraph to remove.
Returns
void
Note
this deletes the root of the graph from graph's root (i.e. calls graph->getRoot()->delNode()).

◆ computeTree()

static Graph* tlp::TreeTest::computeTree ( Graph graph,
PluginProgress pluginProgress = nullptr 
)
static

Computes a rooted tree from the graph. If the graph is a rooted tree, the input graph is returned as is. If the graphs is a free tree, a rooted clone subgraph is returned. If the graph is connected, a rooted spanning tree of a clone subgraph is returned 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.

Parameters
graphThe graph to compute a tree on.
pluginProgressreports progress on the computation. Defaults to 0.
Returns
:Graph* If the input graph is a rooted tree, returns it as is, otherwise a clone subgraph transformed into a rooted tree.

◆ isFreeTree()

static bool tlp::TreeTest::isFreeTree ( const Graph graph)
static

Checks if the graph is a topological tree (i.e. if the graph was undirected, there would be no cycle).

Returns true if the graph is a topological tree (i.e. if the graph was undirected, there would be no cycle), false otherwise.

Parameters
graphThe graph to check is a free tree.
Returns
bool True if the graph is a free tree, false otherwise.

◆ isTree()

static bool tlp::TreeTest::isTree ( const Graph graph)
static

Checks if the graph is a rooted tree (i.e. one node is designated as the root).

Parameters
graphThe graph to check is a tree.
Returns
bool True if the graph is a tree, false otherwise.

◆ makeRootedTree()

static void tlp::TreeTest::makeRootedTree ( Graph freeTree,
node  root 
)
static

Makes a free tree into a rooted tree.

Turns a free tree into a rooted tree.

Parameters
freeTreeThe free tree to make a rooted tree.
rootThe root of the tree.
Returns
void