Open
Graph Drawing
Framework

 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.

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
Gis 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
Gis the input graph.
sinkis 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
Gis 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
Gis the input graph.
sourceis 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
Gis 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
Gis the input graph
backedgesis 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
Gis 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
Gis the input graph
backedgesis 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
Gis 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
Gis the input graph.
sis assigned the single source (if true is returned).
tis assigned the single sink (if true is returned).
stis 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
Gis 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
Gis 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
Gis 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
Gis the input graph.
newEdgesis 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
Gis the input graph.
componentis 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
Gis the input graph.
numis assigned the topological numbering (0, 1, ...).