 # OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

Basic Functions for Digraphs

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.

## ◆ 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 846 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 822 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 752 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 776 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 877 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 930 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, ...).