Basic Functions for Trees and Forests

Functions for testing if a graph represents a (free) tree or forest. More...

Classes
class	ogdf::LCA
	Implements the <O(n log n), O(1)>-time "sparse table" algorithm by Bender and Farach-Colton to compute lowest common ancestors (LCAs) in arborescences (not arbitrary directed acyclic graphs). More...

Methods for trees and forests
bool	ogdf::isTree (const Graph &G)
	Returns true iff G is a tree, i.e. contains no undirected cycle and is connected.
bool	ogdf::isArborescenceForest (const Graph &G, List< node > &roots)
	Returns true iff G is a forest consisting only of arborescences.
bool	ogdf::isArborescenceForest (const Graph &G)
	Returns true iff G is a forest consisting only of arborescences.
bool	ogdf::isArborescence (const Graph &G, node &root)
	Returns true iff G represents an arborescence.
bool	ogdf::isArborescence (const Graph &G)
	Returns true iff G represents an arborescence.

Detailed Description

Functions for testing if a graph represents a (free) tree or forest.

Function Documentation

isArborescence() [1/2]

bool ogdf::isArborescence ( const Graph &  G )

inline

Returns true iff G represents an arborescence.

Parameters

G	is the input graph.

Returns

true if G represents an arborescence, false otherwise.

Definition at line 973 of file simple_graph_alg.h.

isArborescence() [2/2]

bool ogdf::isArborescence	(	const Graph &	G,
		node &	root
	)

Returns true iff G represents an arborescence.

Parameters

G	is the input graph.
root	is assigned the root node (if true is returned).

Returns

true if G represents an arborescence, false otherwise.

isArborescenceForest() [1/2]

bool ogdf::isArborescenceForest ( const Graph &  G )

inline

Returns true iff G is a forest consisting only of arborescences.

Parameters

G	is the input graph.

Returns

true if G represents an arborescence forest, false otherwise.

Definition at line 935 of file simple_graph_alg.h.

isArborescenceForest() [2/2]

bool ogdf::isArborescenceForest	(	const Graph &	G,
		List< node > &	roots
	)

Returns true iff G is a forest consisting only of arborescences.

Parameters

G	is the input graph.
roots	is assigned the list of root nodes of the arborescences in the forest. If false is returned, roots is undefined.

Returns

true if G represents an arborescence forest, false otherwise.

isTree()

bool ogdf::isTree ( const Graph &  G )

inline

Returns true iff G is a tree, i.e. contains no undirected cycle and is connected.

Parameters

G	is the input graph.

Returns

true if G is a tree, false otherwise.

Definition at line 913 of file simple_graph_alg.h.