# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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.

## ◆ 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.