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.

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 1086 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 1040 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:

• 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