Functions for testing if a graph represents a (free) tree or forest.
More...
|
| 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...
|
| |
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.
An arborescence is a digraph that has a unique node with indegree 0 (the root) such that, for any other vertex v, there is exactly one directed walk from r to v.
- Parameters
-
- Returns
- true if
G represents an arborescence, false otherwise.
Definition at line 994 of file simple_graph_alg.h.
◆ isArborescence() [2/2]
| bool ogdf::isArborescence |
( |
const Graph & |
G, |
|
|
node & |
root |
|
) |
| |
Returns true iff G represents an arborescence.
An arborescence is a digraph that has a unique node with indegree 0 (the root) such that, for any other vertex v, there is exactly one directed walk from r to v.
- 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.
An arborescence is a digraph that has a unique node with indegree 0 (the root) such that, for any other vertex v, there is exactly one directed walk from r to v.
- Parameters
-
- Returns
- true if
G represents an arborescence forest, false otherwise.
Definition at line 950 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.
An arborescence is a digraph that has a unique node with indegree 0 (the root) such that, for any other vertex v, there is exactly one directed walk from r to v.
- 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
-
- Returns
- true if
G is a tree, false otherwise.
Definition at line 922 of file simple_graph_alg.h.
