Provides functions for orienting graphs like st-numbering. More...
Functions | |
int | ogdf::computeSTNumbering (const Graph &G, NodeArray< int > &numbering, node s=nullptr, node t=nullptr, bool randomized=false) |
Computes an st-Numbering of G . | |
bool | ogdf::isSTNumbering (const Graph &G, NodeArray< int > &st_no, int max) |
Tests, whether a numbering of the nodes is an st-numbering. | |
Provides functions for orienting graphs like st-numbering.
int ogdf::computeSTNumbering | ( | const Graph & | G, |
NodeArray< int > & | numbering, | ||
node | s = nullptr , |
||
node | t = nullptr , |
||
bool | randomized = false |
||
) |
Computes an st-Numbering of G
.
G
must be biconnected and simple, with the exception that the graph is allowed to have isolated nodes. If both s
and t
are set to nodes (both are not 0), they must be adjacent.G | is the input graph. |
numbering | is assigned the st-number for each node. |
s | is the source node for the st-numbering. |
t | is the target node for the st-numbering. |
randomized | is only used when both s and t are not set (both are 0); in this case a random edge (s,t) is chosen; otherwise the first node s with degree > 0 is chosen and its first neighbor is used as t. |
t
, or 0 if no st-numbering could be computed.