tlp::TreeTest Class Reference

#include <TreeTest.h>

Inheritance diagram for tlp::TreeTest:

Collaboration diagram for tlp::TreeTest:

Static Public Member Functions
static void	cleanComputedTree (Graph *graph, Graph *tree)
static Graph *	computeTree (Graph *graph, PluginProgress *pluginProgress=0)
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 36 of file TreeTest.h.

Member Function Documentation

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

graph	The graph to clean from tree subgraphs.
tree	The tree subgraph to remove.

Returns

void

Note

this deletes the root of the graph from graph's root (i.e. calls graph->getRoot()->delNode()).

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

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

graph	The graph to compute a tree on.
pluginProgress	reports 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.

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

graph

The graph to check is a free tree.

Returns

bool True if the graph is a free tree, false otherwise.

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

graph

The graph to check is a tree.

Returns

bool True if the graph is a tree, false otherwise.

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

freeTree	The free tree to make a rooted tree.
root	The root of the tree.

Returns

void