Basic functions operating on digraphs like testing for single source or sink, st-graph, bimodal. More...

Methods for directed graphs
bool	ogdf::isAcyclic (const Graph &G, List< edge > &backedges)
	Returns true iff the digraph `G` is acyclic. More...

bool	ogdf::isAcyclic (const Graph &G)
	Returns true iff the digraph `G` is acyclic. More...

bool	ogdf::isAcyclicUndirected (const Graph &G, List< edge > &backedges)
	Returns true iff the undirected graph `G` is acyclic. More...

bool	ogdf::isAcyclicUndirected (const Graph &G)
	Returns true iff the undirected graph `G` is acyclic. More...

void	ogdf::makeAcyclic (Graph &G)
	Makes the digraph `G` acyclic by removing edges. More...

void	ogdf::makeAcyclicByReverse (Graph &G)
	Makes the digraph G acyclic by reversing edges. More...

bool	ogdf::hasSingleSource (const Graph &G, node &source)
	Returns true iff the digraph `G` contains exactly one source node (or is empty). More...

bool	ogdf::hasSingleSource (const Graph &G)
	Returns true iff the digraph `G` contains exactly one source node (or is empty). More...

bool	ogdf::hasSingleSink (const Graph &G, node &sink)
	Returns true iff the digraph `G` contains exactly one sink node (or is empty). More...

bool	ogdf::hasSingleSink (const Graph &G)
	Returns true iff the digraph `G` contains exactly one sink node (or is empty). More...

bool	ogdf::isStGraph (const Graph &G, node &s, node &t, edge &st)
	Returns true iff `G` is an st-digraph. More...

bool	ogdf::isStGraph (const Graph &G)
	Returns true if `G` is an st-digraph. More...

void	ogdf::topologicalNumbering (const Graph &G, NodeArray< int > &num)
	Computes a topological numbering of an acyclic digraph `G`. More...

void	ogdf::makeBimodal (Graph &G, List< edge > &newEdges)
	Makes the digraph `G` bimodal. More...

void	ogdf::makeBimodal (Graph &G)
	Makes the digraph `G` bimodal. More...

int	ogdf::strongComponents (const Graph &G, NodeArray< int > &component)
	Computes the strongly connected components of the digraph `G`. More...

Detailed Description

Basic functions operating on digraphs like testing for single source or sink, st-graph, bimodal.

Function Documentation

◆ hasSingleSink() [1/2]

bool ogdf::hasSingleSink ( const Graph & G )

inline

Returns true iff the digraph G contains exactly one sink node (or is empty).

Parameters

G	is the input graph.

Returns: true if G has a single sink, false otherwise.

Definition at line 818 of file simple_graph_alg.h.

◆ hasSingleSink() [2/2]

bool ogdf::hasSingleSink	(	const Graph &	G,
		node &	sink
	)

Returns true iff the digraph G contains exactly one sink node (or is empty).

Parameters

G	is the input graph.
sink	is assigned the single sink if true is returned, or 0 otherwise.

Returns: true if G has a single sink, false otherwise.

◆ hasSingleSource() [1/2]

bool ogdf::hasSingleSource ( const Graph & G )

inline

Returns true iff the digraph G contains exactly one source node (or is empty).

Parameters

G	is the input graph.

Returns: true if G has a single source, false otherwise.

Definition at line 796 of file simple_graph_alg.h.

◆ hasSingleSource() [2/2]

bool ogdf::hasSingleSource	(	const Graph &	G,
		node &	source
	)

Returns true iff the digraph G contains exactly one source node (or is empty).

Parameters

G	is the input graph.
source	is assigned the single source if true is returned, or 0 otherwise.

Returns: true if G has a single source, false otherwise.

◆ isAcyclic() [1/2]

bool ogdf::isAcyclic ( const Graph & G )

inline

Returns true iff the digraph G is acyclic.

Parameters

G	is the input graph

Returns: true if G contains no directed cycle, false otherwise.

Definition at line 730 of file simple_graph_alg.h.

◆ isAcyclic() [2/2]

bool ogdf::isAcyclic	(	const Graph &	G,
		List< edge > &	backedges
	)

Returns true iff the digraph G is acyclic.

Parameters

G	is the input graph
backedges	is assigned the backedges of a DFS-tree.

Returns: true if G contains no directed cycle, false otherwise.

◆ isAcyclicUndirected() [1/2]

bool ogdf::isAcyclicUndirected ( const Graph & G )

inline

Returns true iff the undirected graph G is acyclic.

Parameters

G	is the input graph

Returns: true if G contains no undirected cycle, false otherwise.

Definition at line 752 of file simple_graph_alg.h.

◆ isAcyclicUndirected() [2/2]

bool ogdf::isAcyclicUndirected	(	const Graph &	G,
		List< edge > &	backedges
	)

Returns true iff the undirected graph G is acyclic.

Parameters

G	is the input graph
backedges	is assigned the backedges of a DFS-tree.

Returns: true if G contains no undirected cycle, false otherwise.

◆ isStGraph() [1/2]

bool ogdf::isStGraph ( const Graph & G )

inline

Returns true if G is an st-digraph.

A directed graph is an st-digraph if it is acyclic, contains exactly one source s and one sink t, and the edge (s,t).

Parameters

G	is the input graph.

Returns: true if G is an st-digraph, false otherwise.

Definition at line 847 of file simple_graph_alg.h.

◆ isStGraph() [2/2]

bool ogdf::isStGraph	(	const Graph &	G,
		node &	s,
		node &	t,
		edge &	st
	)

Returns true iff G is an st-digraph.

A directed graph is an st-digraph if it is acyclic, contains exactly one source s and one sink t, and the edge (s,t).

Parameters

G	is the input graph.
s	is assigned the single source (if true is returned).
t	is assigned the single sink (if true is returned).
st	is assigned the edge (s,t) (if true is returned).

Returns: true if G is an st-digraph, false otherwise.

◆ makeAcyclic()

void ogdf::makeAcyclic ( Graph & G )

Makes the digraph G acyclic by removing edges.

The implementation removes all backedges of a DFS tree.

Parameters

G	is the input graph

◆ makeAcyclicByReverse()

void ogdf::makeAcyclicByReverse ( Graph & G )

Makes the digraph G acyclic by reversing edges.

Remarks: The implementation ignores self-loops and reverses the backedges of a DFS-tree.

Parameters

G	is the input graph

◆ makeBimodal() [1/2]

void ogdf::makeBimodal ( Graph & G )

inline

Makes the digraph G bimodal.

The implementation splits all non-bimodal vertices into two vertices.

Parameters

G	is the input graph.

Definition at line 898 of file simple_graph_alg.h.

◆ makeBimodal() [2/2]

void ogdf::makeBimodal	(	Graph &	G,
		List< edge > &	newEdges
	)

Makes the digraph G bimodal.

The implementation splits all non-bimodal vertices into two vertices.

Parameters

G	is the input graph.
newEdges	is the list containing the new edges.

◆ strongComponents()

int ogdf::strongComponents	(	const Graph &	G,
		NodeArray< int > &	component
	)

Computes the strongly connected components of the digraph G.

The function implements the algorithm by Tarjan.

Parameters

G	is the input graph.
component	is assigned a mapping from nodes to component numbers (0, 1, ...).

Returns: the number of strongly connected components.

◆ topologicalNumbering()

void ogdf::topologicalNumbering	(	const Graph &	G,
		NodeArray< int > &	num
	)

Computes a topological numbering of an acyclic digraph G.

Precondition: G is an acyclic directed graph.

Parameters

G	is the input graph.
num	is assigned the topological numbering (0, 1, ...).

OpenGraph DrawingFramework

Methods for directed graphs

Detailed Description

Function Documentation

◆ hasSingleSink() [1/2]

◆ hasSingleSink() [2/2]

◆ hasSingleSource() [1/2]

◆ hasSingleSource() [2/2]

◆ isAcyclic() [1/2]

◆ isAcyclic() [2/2]

◆ isAcyclicUndirected() [1/2]

◆ isAcyclicUndirected() [2/2]

◆ isStGraph() [1/2]

◆ isStGraph() [2/2]

◆ makeAcyclic()

◆ makeAcyclicByReverse()

◆ makeBimodal() [1/2]

◆ makeBimodal() [2/2]

◆ strongComponents()

◆ topologicalNumbering()

Open
Graph Drawing
Framework