Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Orientations

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. More...
 
bool ogdf::isSTNumbering (const Graph &G, NodeArray< int > &st_no, int max)
 Tests, whether a numbering of the nodes is an st-numbering. More...
 

Detailed Description

Provides functions for orienting graphs like st-numbering.

Function Documentation

◆ computeSTNumbering()

int ogdf::computeSTNumbering ( const Graph G,
NodeArray< int > &  numbering,
node  s = nullptr,
node  t = nullptr,
bool  randomized = false 
)

Computes an st-Numbering of G.

Precondition
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.
Parameters
Gis the input graph.
numberingis assigned the st-number for each node.
sis the source node for the st-numbering.
tis the target node for the st-numbering.
randomizedis 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.
Returns
the number assigned to t, or 0 if no st-numbering could be computed.

◆ isSTNumbering()

bool ogdf::isSTNumbering ( const Graph G,
NodeArray< int > &  st_no,
int  max 
)

Tests, whether a numbering of the nodes is an st-numbering.

Precondition
G must be biconnected and simple, with the exception that the graph is allowed to have isolated nodes.