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 > °dist) |
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 > °dist, std::function< int(node)> func) |
Fills dist with the distribution given by a function func in graph G . More... | |
This module contains various basic and advanced graph algorithms.
Fills degdist
with the degree distribution of graph G
.
Definition at line 1066 of file simple_graph_alg.h.
|
inline |
Checks whether a graph is bipartite.
G | is the input graph. |
G
is bipartite, false otherwise. Definition at line 1020 of file simple_graph_alg.h.
Checks whether a graph is bipartite.
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. |
G
is bipartite, false otherwise. bool ogdf::isRegular | ( | const Graph & | G | ) |
Checks if a graph is regular.
G | is the input graph. |
G
is regular, false otherwise. bool ogdf::isRegular | ( | const Graph & | G, |
int | d | ||
) |
Checks if a graph is d-regular.
G | is the input graph. |
d | is the vertex degree. |
G
is d-regular, false otherwise. 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: