OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 809 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 787 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 721 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 743 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 838 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 889 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, ...).