Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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.
 

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. More...
 
bool ogdf::isBipartite (const Graph &G)
 Checks whether a graph is bipartite. More...
 
bool ogdf::isBipartite (const Graph &G, NodeArray< bool > &color)
 Checks whether a graph is bipartite. More...
 
bool ogdf::isRegular (const Graph &G)
 Checks if a graph is regular. More...
 
bool ogdf::isRegular (const Graph &G, int d)
 Checks if a graph is d-regular. More...
 
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. More...
 

Detailed Description

This module contains various basic and advanced graph algorithms.

Function Documentation

◆ degreeDistribution()

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

Fills degdist with the degree distribution of graph G.

See also
ogdf::nodeDistribution

Definition at line 1116 of file simple_graph_alg.h.

◆ isBipartite() [1/2]

bool ogdf::isBipartite ( const Graph G)
inline

Checks whether a graph is bipartite.

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

Definition at line 1070 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
Gis the input graph.
coloris 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
Gis 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
Gis the input graph.
dis 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:

  • Getting the in-degree distribution:
    Array<int> indegDist;
    nodeDistribution(G, indegDist, [](node v) { return v->indeg(); });
  • Getting the number of nodes belonging to specific connected components:
    NodeArray<int> component(G);
    Array<int> compDist;
    connectedComponents(G, component);
    nodeDistribution(G, compDist, component);
See also
ogdf::degreeDistribution
ogdf::connectedComponents
int connectedComponents(const Graph &G, NodeArray< int > &component, List< node > *isolated=nullptr)
Computes the connected components of G and optionally generates a list of isolated nodes.
ogdf::node
NodeElement * node
The type of nodes.
Definition: Graph_d.h:63
ogdf::nodeDistribution
void 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.