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

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

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.

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.