Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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. More...
 
bool ogdf::isArborescenceForest (const Graph &G, List< node > &roots)
 Returns true iff G is a forest consisting only of arborescences. More...
 
bool ogdf::isArborescenceForest (const Graph &G)
 Returns true iff G is a forest consisting only of arborescences. More...
 
bool ogdf::isArborescence (const Graph &G, node &root)
 Returns true iff G represents an arborescence. More...
 
bool ogdf::isArborescence (const Graph &G)
 Returns true iff G represents an arborescence. More...
 

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
Gis the input graph.
Returns
true if G represents an arborescence, false otherwise.

Definition at line 1023 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
Gis the input graph.
rootis 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
Gis the input graph.
Returns
true if G represents an arborescence forest, false otherwise.

Definition at line 981 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
Gis the input graph.
rootsis 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
Gis the input graph.
Returns
true if G is a tree, false otherwise.

Definition at line 956 of file simple_graph_alg.h.