# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
Graph Algorithms

This module contains various basic and advanced graph algorithms. More...

## Modules

Self-Loops and Multi-Edges
Functions dealing with self-loops and multiple (parallel) edges in graphs.

Induced Subgraphs and Cliques
Provides functions dealing with induced subgraphs and finding cliques.

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

Basic Functions for Trees and Forests
Functions for testing if a graph represents a (free) tree or forest.

Basic Functions for Matchings
Simple algorithms for matchings (testing properties, obtaining a maximal matching)

Connectivity in Graphs and Digraphs
Provides functions dealing with connectivity in graphs and clustered.

Shortest Paths
Algorithms for computing shortest paths in graphs (including single-source and all-pairs).

Flow Algorithms
Algorithms for computing min-cost and maximum flows.

Cut Algorithms
Algorithms for computing minimum (s-t-)cuts.

Minimum Spanning Trees
Provides algorithms for minimum spanning trees.

Steiner Trees
Algorithms for computing Steiner trees.

Spanner Algorithms
Algorithms for computing graph spanners.

Planarity and Planarization
Provides algorithms dealing with planarity of graphs.

Cluster-Planarity and Planarization
Provides algorithms dealing with cluster-planarity and embedding.

Augmentation
Provides algorithms for graph augmentation (e.g., adding edges to make a graph biconnected).

Graph Clustering
Provides algorithms for clustering graphs.

Orientations
Provides functions for orienting graphs like st-numbering.

Planar Separator Algorithms
Functions for computing separators in planar graphs.

## Classes

class  ogdf::BasicPageRank
Basic page rank calculation. More...

class  ogdf::ConvexHull
Computes the convex hull of a set of points or a layout. More...

class  ogdf::EdgeIndependentSpanningTrees
Calculates k edge-independent spanning trees of a graph. More...

class  ogdf::Voronoi< T >
Computes Voronoi regions in an edge-weighted graph. More...

## Functions

void ogdf::degreeDistribution (const Graph &G, Array< int > &degdist)
Fills degdist with the degree distribution of graph G.

bool ogdf::isBipartite (const Graph &G)
Checks whether a graph is bipartite.

bool ogdf::isBipartite (const Graph &G, NodeArray< bool > &color)
Checks whether a graph is bipartite.

bool ogdf::isRegular (const Graph &G)
Checks if a graph is regular.

bool ogdf::isRegular (const Graph &G, int d)
Checks if a graph is d-regular.

void ogdf::nodeDistribution (const Graph &G, Array< int > &degdist, std::function< int(node)> func)
Fills dist with the distribution given by a function func in graph G.

## Detailed Description

This module contains various basic and advanced graph algorithms.

## ◆ degreeDistribution()

 void ogdf::degreeDistribution ( const Graph & G, Array< int > & degdist )
inline

Fills degdist with the degree distribution of graph G.

ogdf::nodeDistribution

Definition at line 1065 of file simple_graph_alg.h.

## ◆ isBipartite() [1/2]

 bool ogdf::isBipartite ( const Graph & G )
inline

Checks whether a graph is bipartite.

Parameters
 G is the input graph.
Returns
true if G is bipartite, false otherwise.

Definition at line 1019 of file simple_graph_alg.h.

## ◆ isBipartite() [2/2]

 bool ogdf::isBipartite ( const Graph & G, NodeArray< bool > & color )

Checks whether a graph is bipartite.

Parameters
 G is the input graph. color is assigned the color for each node, i.e. the partition it belongs to, if G is bipartite. Otherwise its contents are undefined.
Returns
true if G is bipartite, false otherwise.

## ◆ isRegular() [1/2]

 bool ogdf::isRegular ( const Graph & G )

Checks if a graph is regular.

Parameters
 G is the input graph.
Returns
true if G is regular, false otherwise.

## ◆ isRegular() [2/2]

 bool ogdf::isRegular ( const Graph & G, int d )

Checks if a graph is d-regular.

Parameters
 G is the input graph. d is the vertex degree.
Returns
true if G is d-regular, false otherwise.

## ◆ nodeDistribution()

 void ogdf::nodeDistribution ( const Graph & G, Array< int > & degdist, std::function< int(node)> func )

Fills dist with the distribution given by a function func in graph G.

The array dist is initialized such that dist.low() represents the minimum function value, and dist.high() represents the maximum function value.

The resulting dist array contains for each function value x the number n of nodes that yield this function value x. In that case, the value at index x of dist is n. Also note that because dist is an array, all intermediate values are 0.

Examples: