Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Graph Generators

Provides various graph generator functions. More...

Classes

struct  ogdf::RandomClusterConfig
 Parameters for the randomPlanarClustering() method. More...
 

Randomized clustering generators

void ogdf::randomCConnectedClustering (ClusterGraph &C, int cNum)
 Creates a random c-connected clustering for a given graph G. More...
 
void ogdf::randomClustering (ClusterGraph &C, int cNum)
 Creates a random clustering for a given graph G. More...
 
void ogdf::randomClustering (ClusterGraph &C, const node root, int moreInLeaves)
 Creates a specified cluster structure for a given graph G, and assigns vertices to clusters. More...
 
bool ogdf::randomPlanarClustering (ClusterGraph &CG, const RandomClusterConfig &config)
 Creates a random c-planar clustering for a given planar graph G. More...
 
void ogdf::randomClusterPlanarGraph (Graph &G, ClusterGraph &CG, int clusters, int node_per_cluster, int edges_per_cluster)
 Create a random planar graph with a c-planar clustering. More...
 
void ogdf::randomSyncPlanInstance (sync_plan::SyncPlan &pq, int pipe_count, int min_deg=3)
 Create a random SynchronizedPlanarity instance by introducing pipe_count pipes between vertices of degree at least min_deg. More...
 
void ogdf::randomSEFEInstanceBySharedGraph (Graph *sefe, EdgeArray< uint8_t > &edge_types, int edges1, int edges2)
 Create a (simultaneously planar) 2-SEFE instance with a given shared graph. More...
 
void ogdf::randomSEFEInstanceByUnionGraph (const Graph *sefe, EdgeArray< uint8_t > &edge_types, double frac_shared=0.34, double frac_g1=0.33)
 Create a (simultaneously planar) 2-SEFE instance with a given union graph. More...
 

Deterministic graph generators

void ogdf::customGraph (Graph &G, int n, List< std::pair< int, int >> edges, Array< node > &nodes)
 Creates a custom graph using a list of pairs to determine the graph's edges. More...
 
void ogdf::customGraph (Graph &G, int n, List< std::pair< int, int >> edges)
 Creates a custom graph using a list of pairs to determine the graph's edges. More...
 
void ogdf::circulantGraph (Graph &G, int n, Array< int > jumps)
 Creates a circulant graph. More...
 
void ogdf::regularLatticeGraph (Graph &G, int n, int k)
 Creates a regular lattice graph. More...
 
void ogdf::regularTree (Graph &G, int n, int children)
 Creates a regular tree. More...
 
void ogdf::completeGraph (Graph &G, int n)
 Creates the complete graph K_n. More...
 
void ogdf::completeKPartiteGraph (Graph &G, const Array< int > &signature)
 Creates the complete k-partite graph K_{k1,k2,...,kn}. More...
 
void ogdf::completeBipartiteGraph (Graph &G, int n, int m)
 Creates the complete bipartite graph K_{n,m}. More...
 
void ogdf::wheelGraph (Graph &G, int n)
 Creates the graph W_n: A wheel graph. More...
 
void ogdf::cubeGraph (Graph &G, int n)
 Creates the graph Q^n: A n-cube graph. More...
 
void ogdf::globeGraph (Graph &G, int meridians, int latitudes)
 Creates a globe graph with a given number of meridians and latitudes. More...
 
void ogdf::suspension (Graph &G, int s)
 Modifies G by adding its s-th suspension. More...
 
void ogdf::gridGraph (Graph &G, int n, int m, bool loopN, bool loopM)
 Creates a (toroidal) grid graph on n x m nodes. More...
 
void ogdf::petersenGraph (Graph &G, int n=5, int m=2)
 Creates a generalized Petersen graph. More...
 
void ogdf::emptyGraph (Graph &G, int nodes)
 Creates a graph with nodes nodes and no edges. More...
 

Graph operations

using ogdf::NodeMap = NodeArray< NodeArray< node > >
 
void ogdf::graphUnion (Graph &G1, const Graph &G2)
 Forms the disjoint union of G1 and G2. More...
 
void ogdf::graphUnion (Graph &G1, const Graph &G2, NodeArray< node > &map2to1, bool parallelfree=false, bool directed=false)
 Forms the union of G1 and G2 while identifying nodes from G2 with nodes from G1. More...
 
void ogdf::graphProduct (const Graph &G1, const Graph &G2, Graph &product, NodeMap &nodeInProduct, const std::function< void(node, node)> &addEdges)
 Computes the graph product of G1 and G2, using a given function to add edges. More...
 
void ogdf::cartesianProduct (const Graph &G1, const Graph &G2, Graph &product, NodeMap &nodeInProduct)
 Computes the Cartesian product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_1,w_2\rangle) | (w_1,w_2) \in E_2\} \cup \{(\langle v_1,w_1\rangle, \langle v_2,w_1\rangle) | (v_1,v_2) \in E_1\} \). More...
 
void ogdf::tensorProduct (const Graph &G1, const Graph &G2, Graph &product, NodeMap &nodeInProduct)
 Computes the tensor product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \in E_1 \land (w_1,w_2) \in E_2\} \). More...
 
void ogdf::lexicographicalProduct (const Graph &G1, const Graph &G2, Graph &product, NodeMap &nodeInProduct)
 Computes the lexicographical product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \in E_1\} \cup \{(\langle v_1,w_1\rangle, \langle v_1,w_2\rangle) | (w_1,w_2) \in E_2\} \). More...
 
void ogdf::strongProduct (const Graph &G1, const Graph &G2, Graph &product, NodeMap &nodeInProduct)
 Computes the strong product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_1,w_2\rangle) | (w_1,w_2) \in E_2\} \cup \{(\langle v_1,w_1\rangle, \langle v_2,w_1\rangle) | (v_1,v_2) \in E_1\} \cup \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \in E_1 \land (w_1,w_2) \in E_2\} \). More...
 
void ogdf::coNormalProduct (const Graph &G1, const Graph &G2, Graph &product, NodeMap &nodeInProduct)
 Computes the co-normal product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \in E_1 \lor (w_1,w_2) \in E_2\} \). More...
 
void ogdf::modularProduct (const Graph &G1, const Graph &G2, Graph &product, NodeMap &nodeInProduct)
 Computes the modular product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \in E_1 \land (w_1,w_2) \in E_2\} \cup \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \not\in E_1 \land (w_1,w_2) \not\in E_2\} \). More...
 
void ogdf::rootedProduct (const Graph &G1, const Graph &G2, Graph &product, NodeMap &nodeInProduct, node rootInG2)
 Computes the rooted product of G1 and G2, rooted in rootInG2, and assigns it to product. More...
 

Randomized graph generators

template<typename D >
void ogdf::randomGeographicalThresholdGraph (Graph &G, Array< int > &weights, D &dist, double threshold, std::function< double(double)> h, int dimension=2)
 Creates a random geometric graph where edges are created based on their distance and the weight of nodes. More...
 
template<typename D >
void ogdf::randomGeographicalThresholdGraph (Graph &G, Array< int > &weights, D &dist, double threshold, int alpha=2, int dimension=2)
 Creates a random geometric graph where edges are created based on their distance and the weight of nodes. More...
 
void ogdf::randomRegularGraph (Graph &G, int n, int d)
 Creates a random d-regular graph. More...
 
void ogdf::randomGraph (Graph &G, int n, int m)
 Creates a random graph. More...
 
bool ogdf::randomSimpleGraph (Graph &G, int n, int m)
 Creates a random simple graph. More...
 
bool ogdf::randomSimpleGraphByProbability (Graph &G, int n, double pEdge)
 Creates a random simple graph. More...
 
bool ogdf::randomSimpleConnectedGraph (Graph &G, int n, int m)
 Creates a random simple and connected graph. More...
 
void ogdf::randomBiconnectedGraph (Graph &G, int n, int m)
 Creates a random biconnected graph. More...
 
void ogdf::randomPlanarConnectedGraph (Graph &G, int n, int m)
 Creates a random connected (simple) planar (embedded) graph. More...
 
void ogdf::randomPlanarBiconnectedGraph (Graph &G, int n, int m, bool multiEdges=false)
 Creates a random planar biconnected (embedded) graph. More...
 
void ogdf::randomPlanarBiconnectedDigraph (Graph &G, int n, int m, double p=0, bool multiEdges=false)
 Creates a random planar biconnected acyclic (embedded) digraph. More...
 
void ogdf::randomUpwardPlanarBiconnectedDigraph (Graph &G, int n, int m)
 Creates a random upward planar biconnected (embedded) digraph. More...
 
void ogdf::randomPlanarCNBGraph (Graph &G, int n, int m, int b)
 Creates a random planar graph, that is connected, but not biconnected. More...
 
void ogdf::randomTriconnectedGraph (Graph &G, int n, double p1, double p2)
 Creates a random triconnected (and simple) graph. More...
 
void ogdf::randomPlanarTriconnectedGraph (Graph &G, int n, int m)
 Creates a random planar triconnected (and simple) graph. More...
 
void ogdf::randomPlanarTriconnectedGraph (Graph &G, int n, double p1, double p2)
 Creates a random planar triconnected (and simple) graph. More...
 
void ogdf::randomTree (Graph &G, int n)
 Creates a random tree (simpler version. More...
 
void ogdf::randomTree (Graph &G, int n, int maxDeg, int maxWidth)
 Creates a random tree. More...
 
void ogdf::randomDigraph (Graph &G, int n, double p)
 Creates a random (simple) directed graph. More...
 
void ogdf::randomSeriesParallelDAG (Graph &G, int edges, double p=0.5, double flt=0.0)
 Creates a random (simple, biconnected) series parallel DAG. More...
 
void ogdf::randomGeometricCubeGraph (Graph &G, int nodes, double threshold, int dimension=2)
 Creates a random geometric graph by laying out nodes in a unit n-cube. Nodes with a distance < threshold are connected, 0 <= threshold <= sqrt(dimension). The graph is simple. More...
 
void ogdf::randomWaxmanGraph (Graph &G, int nodes, double alpha, double beta, double width=1.0, double height=1.0)
 Generates a Waxman graph where nodes are uniformly randomly placed in a grid, then edges are inserted based on nodes' euclidean distances. More...
 
void ogdf::preferentialAttachmentGraph (Graph &G, int nodes, int minDegree)
 Creates a graph where new nodes are more likely to connect to nodes with high degree. More...
 
void ogdf::randomWattsStrogatzGraph (Graph &G, int n, int k, double probability)
 Creates a "small world" graph as described by Watts & Strogatz. More...
 
void ogdf::randomChungLuGraph (Graph &G, Array< int > expectedDegreeDistribution)
 Creates a graph where edges are inserted based on given weights. More...
 
void ogdf::randomEdgesGraph (Graph &G, std::function< double(node, node)> probability)
 Inserts edges into the given graph based on probabilities given by a callback function. More...
 
void ogdf::randomProperMaximalLevelPlaneGraph (Graph &G, std::vector< std::vector< node >> &emb, int N, int K, bool radial)
 Generates a random proper, maximal (radial) level-plane graph. More...
 
void ogdf::randomHierarchy (Graph &G, int n, int m, bool planar, bool singleSource, bool longEdges)
 Creates a random hierarchical graph. More...
 
void ogdf::pruneEdges (Graph &G, int max_edges, int min_deg)
 Removed random edges from /p G until it has less than /p max_edges edges, not removing edges from nodes with degree less than /p min_deg. More...
 

Detailed Description

Provides various graph generator functions.

Typedef Documentation

◆ NodeMap

using ogdf::NodeMap = typedef NodeArray<NodeArray<node> >

Definition at line 72 of file operations.h.

Function Documentation

◆ cartesianProduct()

void ogdf::cartesianProduct ( const Graph G1,
const Graph G2,
Graph product,
NodeMap nodeInProduct 
)

Computes the Cartesian product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_1,w_2\rangle) | (w_1,w_2) \in E_2\} \cup \{(\langle v_1,w_1\rangle, \langle v_2,w_1\rangle) | (v_1,v_2) \in E_1\} \).

Multi-edges are kept and incorporated into the graph product.

Parameters
G1is the first input graph.
G2is the second input graph.
productis assigned the graph product.
nodeInProductis assigned a mapping from nodes of (G1, G2) to product.

◆ circulantGraph()

void ogdf::circulantGraph ( Graph G,
int  n,
Array< int >  jumps 
)

Creates a circulant graph.

Generates a simple, undirected graph on \(n\) nodes \(V := v_0,v_1,\ldots,v_{n-1}\) that contains exactly the edges \( \{v_iv_{i+d}\colon v_i \in V, d \in \text{jumps}\} \) where node indices are to be understood modulo \(n\). The order of nodes induced by G is the sequence \(V\) given above.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
jumpsis the array of distances for edges to be created.

◆ completeBipartiteGraph()

void ogdf::completeBipartiteGraph ( Graph G,
int  n,
int  m 
)

Creates the complete bipartite graph K_{n,m}.

The returned graph is directed acyclic.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the first partition set.
mis the number of nodes of the second partition set.

◆ completeGraph()

void ogdf::completeGraph ( Graph G,
int  n 
)

Creates the complete graph K_n.

The returned graph is directed acyclic.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.

◆ completeKPartiteGraph()

void ogdf::completeKPartiteGraph ( Graph G,
const Array< int > &  signature 
)

Creates the complete k-partite graph K_{k1,k2,...,kn}.

The returned graph is directed acyclic.

Parameters
Gis assigned the generated graph.
signaturecontains the positive values k1, k2, ..., kn.

◆ coNormalProduct()

void ogdf::coNormalProduct ( const Graph G1,
const Graph G2,
Graph product,
NodeMap nodeInProduct 
)

Computes the co-normal product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \in E_1 \lor (w_1,w_2) \in E_2\} \).

Multi-edges are kept and incorporated into the graph product.

Parameters
G1is the first input graph.
G2is the second input graph.
productis assigned the graph product.
nodeInProductis assigned a mapping from nodes of (G1, G2) to product.

◆ cubeGraph()

void ogdf::cubeGraph ( Graph G,
int  n 
)

Creates the graph Q^n: A n-cube graph.

Parameters
Gis assigned the generated graph.
nis the number of the cube's dimensions (n>=0).

◆ customGraph() [1/2]

void ogdf::customGraph ( Graph G,
int  n,
List< std::pair< int, int >>  edges 
)
inline

Creates a custom graph using a list of pairs to determine the graph's edges.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
edgesis a list of pairs, each one representing two nodes that should be connected by an edge in the generated graph.

Definition at line 64 of file deterministic.h.

◆ customGraph() [2/2]

void ogdf::customGraph ( Graph G,
int  n,
List< std::pair< int, int >>  edges,
Array< node > &  nodes 
)

Creates a custom graph using a list of pairs to determine the graph's edges.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
edgesis a list of pairs, each one representing two nodes that should be connected by an edge in the generated graph.
nodesresulting array mapping node index to the actual node

◆ emptyGraph()

void ogdf::emptyGraph ( Graph G,
int  nodes 
)

Creates a graph with nodes nodes and no edges.

Parameters
Gis assigned the generated graph.
nodesis the number of nodes of the generated graph.

◆ globeGraph()

void ogdf::globeGraph ( Graph G,
int  meridians,
int  latitudes 
)

Creates a globe graph with a given number of meridians and latitudes.

The graph will contain a node at each crossing of a meridian and a latitude, and a node at each pole, hence meridians * latitudes + 2 nodes overall.

Parameters
Gis assigned the generated graph.
meridiansis the number of meridians.
latitudesis the number of latitudes.

◆ graphProduct()

void ogdf::graphProduct ( const Graph G1,
const Graph G2,
Graph product,
NodeMap nodeInProduct,
const std::function< void(node, node)> &  addEdges 
)

Computes the graph product of G1 and G2, using a given function to add edges.

First, product is cleared. \(|V(G1)|\cdot|V(G2)|\) nodes are added to it and addEdges is called for each pair of nodes in \(V(G1) \times V(G2)\).

Parameters
G1is the first input graph.
G2is the second input graph.
productis assigned the graph product.
nodeInProductis assigned a mapping from nodes of (G1, G2) to product.
addEdgesA function that adds edges to the graph product for each pair of nodes in \(V(G1) \times V(G2)\).

◆ graphUnion() [1/2]

void ogdf::graphUnion ( Graph G1,
const Graph G2 
)
inline

Forms the disjoint union of G1 and G2.

Parameters
G1is the first graph and assigned the graph union.
G2is the second graph.

Definition at line 52 of file operations.h.

◆ graphUnion() [2/2]

void ogdf::graphUnion ( Graph G1,
const Graph G2,
NodeArray< node > &  map2to1,
bool  parallelfree = false,
bool  directed = false 
)

Forms the union of G1 and G2 while identifying nodes from G2 with nodes from G1.

Parameters
G1is the first graph and assigned the graph union.
G2is the second graph.
map2to1identifies nodes from G2 with nodes from G1. Empty entries in map2to1 have to be nullptr. It is assigned a mapping from nodes in G2 to the union G1.
parallelfreesets whether the resulting graph union should not contain multi-edges.
directedsets whether the graph union is treated as directed or undirected when detecting multi-edges. It only has an effect if parallelfree is set.

◆ gridGraph()

void ogdf::gridGraph ( Graph G,
int  n,
int  m,
bool  loopN,
bool  loopM 
)

Creates a (toroidal) grid graph on n x m nodes.

Parameters
Gis assigned the generated graph.
nis the number of nodes on first axis.
mis the number of nodes on second axis.
loopNif the grid is cyclic on first axis
loopMif the grid is cyclic on second axis

◆ lexicographicalProduct()

void ogdf::lexicographicalProduct ( const Graph G1,
const Graph G2,
Graph product,
NodeMap nodeInProduct 
)

Computes the lexicographical product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \in E_1\} \cup \{(\langle v_1,w_1\rangle, \langle v_1,w_2\rangle) | (w_1,w_2) \in E_2\} \).

Warning
The lexicographical product is not commutative! Multi-edges are kept and incorporated into the graph product.
Parameters
G1is the first input graph.
G2is the second input graph.
productis assigned the graph product.
nodeInProductis assigned a mapping from nodes of (G1, G2) to product.

◆ modularProduct()

void ogdf::modularProduct ( const Graph G1,
const Graph G2,
Graph product,
NodeMap nodeInProduct 
)

Computes the modular product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \in E_1 \land (w_1,w_2) \in E_2\} \cup \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \not\in E_1 \land (w_1,w_2) \not\in E_2\} \).

Multi-edges are kept and incorporated into the graph product.

Parameters
G1is the first input graph.
G2is the second input graph.
productis assigned the graph product.
nodeInProductis assigned a mapping from nodes of (G1, G2) to product.

◆ petersenGraph()

void ogdf::petersenGraph ( Graph G,
int  n = 5,
int  m = 2 
)

Creates a generalized Petersen graph.

Creates an outer cycle of nodes 1, ..., n, each of which has a direct neighbor (a corresponding inner node). For two outer nodes i, j, there is an edge between their corresponding inner nodes if the absolute difference of i and j equals the jump length m.

If no values for n or m are given, assume the standard Petersen graph of 5 nodes and a jump length of 2.

Parameters
Gis assigned the generated graph.
nis the number of nodes on the outer cycle.
mis the length of jumps for the inner part.

◆ preferentialAttachmentGraph()

void ogdf::preferentialAttachmentGraph ( Graph G,
int  nodes,
int  minDegree 
)

Creates a graph where new nodes are more likely to connect to nodes with high degree.

Implements the Preferential Attachment algorithm as described in: Emergence of Scaling in Random Networks Albert-Laszlo Barabasi and Reka Albert https://arxiv.org/abs/cond-mat/9910332v1 This algorithm creates edges based on the degree of nodes, so it is most useful to apply this to a pre-built graph. If no graph is supplied, a complete graph of minDegree nodes is generated and the algorithm adds nodes - minDegree nodes. If a graph is supplied, it must contain at least minDegree nodes of degree 1.

Parameters
Gis the input graph (see above) and is assigned the expanded graph.
nodesis the number of nodes to be added to graph.
minDegreeis the minimum degree of new nodes.

◆ pruneEdges()

void ogdf::pruneEdges ( Graph G,
int  max_edges,
int  min_deg 
)

Removed random edges from /p G until it has less than /p max_edges edges, not removing edges from nodes with degree less than /p min_deg.

◆ randomBiconnectedGraph()

void ogdf::randomBiconnectedGraph ( Graph G,
int  n,
int  m 
)

Creates a random biconnected graph.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
mis the number of edges of the generated graph.
Note
n has a lower bound of 3, and m a lower bound of n. If the parameters are smaller than that, they get increased prior to the algorithm.

◆ randomCConnectedClustering()

void ogdf::randomCConnectedClustering ( ClusterGraph C,
int  cNum 
)

Creates a random c-connected clustering for a given graph G.

The resulting cluster graph is always c-connected but may or may not be c-planar (e.g. when a connected cluster encloses some outside vertices).

Parameters
Cis a cluster graph for G.
cNumis the maximal number of Clusters introduced.
Precondition
G is connected and not empty.

◆ randomChungLuGraph()

void ogdf::randomChungLuGraph ( Graph G,
Array< int >  expectedDegreeDistribution 
)

Creates a graph where edges are inserted based on given weights.

Implements the algorithm described in: The average distance in a random graph with given expected degrees Fang Chung and Linyuan Lu http://www.math.ucsd.edu/~fan/wp/aveflong.pdf

Given an expected degree distribution of length n: \(w:=(w_1, ..., w_n)\) with \(0 < w_k < n\).

Let \(S:=\sum_{k=1}^{n}w_k\) be the sum over all expected degrees. Consider each edge independently and insert it with probability \(p_{ij} := \frac{w_i \, w_j}{S}\). Therefore, to get percentages in \((0,1)\) we assert that \(\max\limits_k(w_k)^2 < S\).

Precondition
Each degree must be strictly between 0 and n, and the square of the maximal expected degree must be lower than the sum of all expected degrees.
Parameters
Gis assigned the generated graph.
expectedDegreeDistributionis a list of expected degrees, or weights, for the individual nodes. Its length defines the number of nodes n.

◆ randomClustering() [1/2]

void ogdf::randomClustering ( ClusterGraph C,
const node  root,
int  moreInLeaves 
)

Creates a specified cluster structure for a given graph G, and assigns vertices to clusters.

This function is called with a graph G and the root of a second graph, resembling a tree, that gives the cluster structure. Then, the vertices of G are randomly assigned to the clusters, where we can guarantee that any leaf-cluster has (on average) moreInLeaves-times more vertices than a non-leaf cluster. (E.g. if moreInLeaves = 5, any leaf will contain roughly 5 times more vertices than an inner cluster)

Parameters
Cis a cluster graph for G, to be assigned the solution.
rootis a node in some other graph (say T). T is a tree that we will consider rooted at root. T is the pattern for the cluster hierarchy.
moreInLeavesis a factor such that leaf-clusters have on average moreInLeaves-times more vertices than inner clusters
Precondition
G contains at least twice as many nodes as T has leaves.

◆ randomClustering() [2/2]

void ogdf::randomClustering ( ClusterGraph C,
int  cNum 
)

Creates a random clustering for a given graph G.

Parameters
Cis a cluster graph for G.
cNumis the maximal number of clusters introduced.
Precondition
G is connected and not empty.

◆ randomClusterPlanarGraph()

void ogdf::randomClusterPlanarGraph ( Graph G,
ClusterGraph CG,
int  clusters,
int  node_per_cluster,
int  edges_per_cluster 
)

Create a random planar graph with a c-planar clustering.

The graph is iteratively created by starting with a random planar connected graph and then, for each cluster, choosing an arbitrary vertex and replacing it with a cluster containing another new random planar graph. The replacement is done by identifying pairs of incident edges between the chosen vertex and another random vertex from the new graph. Thus, when a cut-vertex is joined in this way, the resulting graph will no longer be c-connected.

Parameters
Gwill be assigned the planar graph.
CGwill be assigned the c-planar clustering of G.
clustershow many clusters to generate.
node_per_clusterhow many nodes each cluster should directly contain.
edges_per_clusterhow many edges to add between each clusters' nodes.

◆ randomDigraph()

void ogdf::randomDigraph ( Graph G,
int  n,
double  p 
)

Creates a random (simple) directed graph.

Parameters
Gis assigned the generated graph.
nis the number of nodes in the generated graph.
pis the probability that an edge is created (for each node pair)

◆ randomEdgesGraph()

void ogdf::randomEdgesGraph ( Graph G,
std::function< double(node, node)>  probability 
)

Inserts edges into the given graph based on probabilities given by a callback function.

Iterates through each distinct pair of nodes and inserts an edge with the probability returned by the provided callback function.

The resulting graph is guaranteed to be simple if:

  • the input graph had no edges, or
  • the input graph was simple and the callback function returns 0 for each pair of nodes that was connected before.
Parameters
Gis a graph that should have at least two nodes (so edges can be generated)
probabilityis a callback function that, for any given pair of nodes, returns a probability between 0 and 1 for the two nodes to be connected.

◆ randomGeographicalThresholdGraph() [1/2]

template<typename D >
void ogdf::randomGeographicalThresholdGraph ( Graph G,
Array< int > &  weights,
D &  dist,
double  threshold,
int  alpha = 2,
int  dimension = 2 
)

Creates a random geometric graph where edges are created based on their distance and the weight of nodes.

This generator uses \(r^{-\alpha}\) for the given alpha as heuristic function.

See also
randomGeographicalThresholdGraph(Graph &G, Array<int> &weights, D &dist, double threshold, std::function<double(double)> h, int dimension) for detailed description.
Template Parameters
Dthe random distribution to use (see dist).
Parameters
Gis assigned the generated graph.
weightshas the weights for all nodes in the graph.
distis a random number distribution, e.g. std::uniform_int_distribution<>. It should likely generate values in roughly the same order of magnitude as 1/threshold.
thresholdis the threshold for edge insertion.
alphais the constant in the heuristic function.
dimensionis the dimension the nodes are laid out in.

Definition at line 120 of file randomGeographicalThresholdGraph.h.

◆ randomGeographicalThresholdGraph() [2/2]

template<typename D >
void ogdf::randomGeographicalThresholdGraph ( Graph G,
Array< int > &  weights,
D &  dist,
double  threshold,
std::function< double(double)>  h,
int  dimension = 2 
)

Creates a random geometric graph where edges are created based on their distance and the weight of nodes.

Geographical threshold graphs with small-world and scale-free properties Naoki Masuda, Hiroyoshi Miwa, Norio Konno https://arxiv.org/abs/cond-mat/0409378

Distribute vertices using an exponential distribution in a d-dimensional Euclidean space. Then a pair of vertices with weights w,w' and Euclidean distance \(r:=||w-w'||\) are connected iff for the heuristic function h holds: \((w+w')*h(r) < \mathrm{threshold}\).

Template Parameters
Dthe random distribution to use (see dist).
Parameters
Gis assigned the generated graph.
weightshas the weights for all nodes in the graph.
distis a random number distribution, e.g. std::uniform_int_distribution<>. It should likely generate values in roughly the same order of magnitude as h(threshold).
thresholdis the threshold for edge insertion.
his a function that should be decreasing in the distance supplied to it.
dimensionis the dimension the nodes are laid out in.

Definition at line 67 of file randomGeographicalThresholdGraph.h.

◆ randomGeometricCubeGraph()

void ogdf::randomGeometricCubeGraph ( Graph G,
int  nodes,
double  threshold,
int  dimension = 2 
)

Creates a random geometric graph by laying out nodes in a unit n-cube. Nodes with a distance < threshold are connected, 0 <= threshold <= sqrt(dimension). The graph is simple.

Parameters
Gis assigned the generated graph.
nodesis the number of nodes of the generated graph.
thresholdis threshold radius of nodes which will be connected.
dimensionis the dimension of the cube.

◆ randomGraph()

void ogdf::randomGraph ( Graph G,
int  n,
int  m 
)

Creates a random graph.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
mis the number of edges of the generated graph.

◆ randomHierarchy()

void ogdf::randomHierarchy ( Graph G,
int  n,
int  m,
bool  planar,
bool  singleSource,
bool  longEdges 
)

Creates a random hierarchical graph.

Parameters
Gis assigned the generated graph.
nis the number of nodes.
mis the number of edges.
planardetermines if the resulting graph is (level-)planar.
singleSourcedetermines if the graph is a single-source graph.
longEdgesdetermines if the graph has long edges (spanning 2 layers or more); otherwise the graph is proper.
See also
randomProperMaximalLevelPlaneGraph() for a simpler alternative

◆ randomPlanarBiconnectedDigraph()

void ogdf::randomPlanarBiconnectedDigraph ( Graph G,
int  n,
int  m,
double  p = 0,
bool  multiEdges = false 
)

Creates a random planar biconnected acyclic (embedded) digraph.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
mis the number of edges of the generated graph.
pup to m * p edges will be reversed preversing acyclicity; default = 0.0.
multiEdgesdetermines if the generated graph may contain multi-edges; default = false.
Precondition
d is between 0.0 and 1.0
Note
n has a lower bound of 3, and m has a lower bound of n and an upper bound of \(3n-6\). The supplied values are adjusted if they are out of these bounds.

◆ randomPlanarBiconnectedGraph()

void ogdf::randomPlanarBiconnectedGraph ( Graph G,
int  n,
int  m,
bool  multiEdges = false 
)

Creates a random planar biconnected (embedded) graph.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
mis the number of edges of the generated graph.
multiEdgesdetermines if the generated graph may contain multi-edges.
Note
n has a lower bound of 3, and m has a lower bound of n and an upper bound of \(3n-6\). The supplied values are adjusted if they are out of these bounds.

◆ randomPlanarClustering()

bool ogdf::randomPlanarClustering ( ClusterGraph CG,
const RandomClusterConfig config 
)

Creates a random c-planar clustering for a given planar graph G.

The clusters are created by working on a copy of G and making it connected as well as triangulated and then:

  1. selecting a random node u and putting it into a new cluster
  2. selecting a random incident edge e such that its other endpoint v and u have at most two common neighbors (this ensures c-planarity)
  3. adding v into the cluster of u by contracting e in the copy of G
  4. going to step 2. if the cluster may grow further or otherwise step 1. if we may another cluster

The clustering is c-connected if we only select edges that were already present in G instead of being added by the triangulation.

Parameters
CGis a cluster graph for some G.
configconfiguration for the random generation
Returns
false if the clustering ran into the configured timeout, true otherwise

◆ randomPlanarCNBGraph()

void ogdf::randomPlanarCNBGraph ( Graph G,
int  n,
int  m,
int  b 
)

Creates a random planar graph, that is connected, but not biconnected.

Parameters
Gis assigned the generated graph.
nis the max. number of nodes in each biconnected component
mis the max. number of edges in each biconnected component
bis the number of biconnected components
Precondition
It holds that n > 1, m >= n (unless n = 2, m = 1) and b > 1.

◆ randomPlanarConnectedGraph()

void ogdf::randomPlanarConnectedGraph ( Graph G,
int  n,
int  m 
)

Creates a random connected (simple) planar (embedded) graph.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
mis the number of edges of the generated graph.
Note
n has a lower bound of 1, and m has a lower bound of n and an upper bound of \(3n-6\). The supplied values are adjusted if they are out of these bounds.

◆ randomPlanarTriconnectedGraph() [1/2]

void ogdf::randomPlanarTriconnectedGraph ( Graph G,
int  n,
double  p1,
double  p2 
)

Creates a random planar triconnected (and simple) graph.

This graph generator creates a planar triconnected graph by successive node splitting. It starts with the K_4 and performs n -4 node splits. Each such split operation distributes a node's neighbors to the two nodes resulting from the split. Aftewards, two further edges can be added; the probability for adding these edges is given by p1 and p2. The higher these probabilities, the denser the resulting graph. Note that a simple planar triconnected graph has between 1.5n and 3n -6 edges.

Precondition
0.0 <= p1, p2 <= 1.0.
Parameters
Gis assigned the generated graph.
nis the number of nodes in the generated graph.
p1is the probability for the first additional edge to be added.
p2is the probability for the second additional edge to be added.
Note
n has a lower bound of 4 and will get increased to this if smaller.

◆ randomPlanarTriconnectedGraph() [2/2]

void ogdf::randomPlanarTriconnectedGraph ( Graph G,
int  n,
int  m 
)

Creates a random planar triconnected (and simple) graph.

This graph generator works in two steps.

  1. A planar triconnected 3-regular graph is constructed using successive splitting of pairs of nodes. The constructed graph has n nodes and 1.5n edges.
  2. The remaining edges are inserted by successive splitting of faces with degree four or greater. The resulting graph also represents a combinatorial embedding.
Parameters
Gis assigned the generated graph.
nis the number of nodes in the generated graph.
mis the number of edges in the generated graph.
Note
  • n >= 4 and n must be even; otherwise, n is adjusted to the next feasible integer.
  • 1.5n <= m <= 3n -6; otherwise, m is adjusted to a feasible value.

◆ randomProperMaximalLevelPlaneGraph()

void ogdf::randomProperMaximalLevelPlaneGraph ( Graph G,
std::vector< std::vector< node >> &  emb,
int  N,
int  K,
bool  radial 
)

Generates a random proper, maximal (radial) level-plane graph.

Use pruneEdges() to obtain a non-maximal (radial) level-plane graph.

Parameters
Gis assigned the generated graph.
embwill be assigned the level-planar embedding, i.e., for each level an order of its vertices
Nthe number of nodes to generate.
Kthe number of levels to generate.
radialwhether the graph/embedding should radial level-plane or just level-plane.

◆ randomRegularGraph()

void ogdf::randomRegularGraph ( Graph G,
int  n,
int  d 
)

Creates a random d-regular graph.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
dis the degree of each vertex
Precondition
n * d must be even
Warning
This method is not guaranteed to terminate!

◆ randomSEFEInstanceBySharedGraph()

void ogdf::randomSEFEInstanceBySharedGraph ( Graph sefe,
EdgeArray< uint8_t > &  edge_types,
int  edges1,
int  edges2 
)

Create a (simultaneously planar) 2-SEFE instance with a given shared graph.

This works by randomly subdividing the faces of the embedded sefe, separately for the two exclusive graphs.

Parameters
sefecontains the shared graph and will be modified to also contain the exclusive edges.
edge_typeswill be assigned 3 for all shared edges and 1 or 2 for edges in either of the exclusive graphs.
edges1the number of edges to create for the first exclusive graph.
edges2the number of edges to create for the second exclusive graph.
Precondition
sefe must contain a connected, planarly embedded graph

◆ randomSEFEInstanceByUnionGraph()

void ogdf::randomSEFEInstanceByUnionGraph ( const Graph sefe,
EdgeArray< uint8_t > &  edge_types,
double  frac_shared = 0.34,
double  frac_g1 = 0.33 
)

Create a (simultaneously planar) 2-SEFE instance with a given union graph.

This works by randomly assigning edges of the embedded sefe to either an exclusive or the shared graph.

Parameters
sefecontains the desired union graph.
edge_typeswill be assigned 3 for all shared edges and 1 or 2 for edges in either of the exclusive graphs.
frac_sharedthe (expected) fraction of edges to make shared (i.e. type 3).
frac_g1the (expected) fraction of edges to assign to exclusive graph 1.

◆ randomSeriesParallelDAG()

void ogdf::randomSeriesParallelDAG ( Graph G,
int  edges,
double  p = 0.5,
double  flt = 0.0 
)

Creates a random (simple, biconnected) series parallel DAG.

This function creates a random series parallel biconnected DAG. Note, that the resulting graph is trivially upward planar! To use this generator for experiments, e.g. concerning upward planarity, you can fit the graph by reversing some edges with the parameter 0 < flt < 1.

Parameters
Gis assigned the generated graph.
edgesis the number of edges in the generated graph.
p= probability of a series composition; default = 0.5
flt= up to edges*flt edges will be reversed preversing acyclicity; default = 0.0
Precondition
p is in \([0.0, 1.0]\), and flt is in \([0.0, 1.0)\).

◆ randomSimpleConnectedGraph()

bool ogdf::randomSimpleConnectedGraph ( Graph G,
int  n,
int  m 
)

Creates a random simple and connected graph.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
mis the number of edges of the generated graph.

◆ randomSimpleGraph()

bool ogdf::randomSimpleGraph ( Graph G,
int  n,
int  m 
)

Creates a random simple graph.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
mis the number of edges of the generated graph.

◆ randomSimpleGraphByProbability()

bool ogdf::randomSimpleGraphByProbability ( Graph G,
int  n,
double  pEdge 
)

Creates a random simple graph.

Algorithm based on PreZER/LogZER from: Sadegh Nobari, Xuesong Lu, Panagiotis Karras, and Stéphane Bressan. 2011. Fast random graph generation. In Proceedings of the 14th International Conference on Extending Database Technology (EDBT/ICDT '11), ACM, New York, NY, USA, 331-342. DOI=http://dx.doi.org/10.1145/1951365.1951406

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
pEdgeis the probability for each edge to be added into the graph.
Precondition
/p pEdge is in [0, 1]

◆ randomSyncPlanInstance()

void ogdf::randomSyncPlanInstance ( sync_plan::SyncPlan pq,
int  pipe_count,
int  min_deg = 3 
)

Create a random SynchronizedPlanarity instance by introducing pipe_count pipes between vertices of degree at least min_deg.

◆ randomTree() [1/2]

void ogdf::randomTree ( Graph G,
int  n 
)

Creates a random tree (simpler version.

Parameters
Gis assigned the tree.
nis the number of nodes of the tree.

◆ randomTree() [2/2]

void ogdf::randomTree ( Graph G,
int  n,
int  maxDeg,
int  maxWidth 
)

Creates a random tree.

Parameters
Gis assigned the tree.
nis the number of nodes of the tree.
maxDegis the maximal allowed node degree; 0 means no restriction.
maxWidthis the maximal allowed width of a level; 0 means no restriction.
Note
if maxDeg or maxWidth are 0 (or negative), they are set to n

◆ randomTriconnectedGraph()

void ogdf::randomTriconnectedGraph ( Graph G,
int  n,
double  p1,
double  p2 
)

Creates a random triconnected (and simple) graph.

The graph generator proceeds as follows. It starts with a K_4 and performs then n -4 split node operations on randomly selected nodes of the graph constructed so far. Each such operation splits a node v into two nodes x and y and distributes v's neighbors to the two nodes such that each node gets at least two neighbors. Additionally, the edge (x,y) is inserted.

The neighbors are distributed such that a neighbor of v becomes

  • only a neighbor of x with probability p1;
  • only a neighbor of y with probability p1;
  • a neighbor of both x and y with probability 1.0 - p1 - p2.
Parameters
Gis assigned the generated graph.
nis the number of nodes in the generated graph.
p1is the probability that an edge is moved only to the left node after splitting a node.
p2is the probability that an edge is moved only to the right node after splitting a node.

The probability for a neighbor to be moved to both split nodes is 1.0 - p1 - p2. The higher this probability, the higher the density of the resulting graph.

Precondition
The probabilities p1 and p2 must lie between 0.0 and 1.0, and p1 + p2 <= 1.0.
Note
n has a lower bound of 4 and will get increased to this if smaller.

◆ randomUpwardPlanarBiconnectedDigraph()

void ogdf::randomUpwardPlanarBiconnectedDigraph ( Graph G,
int  n,
int  m 
)

Creates a random upward planar biconnected (embedded) digraph.

Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
mis the number of edges of the generated graph.
Note
n has a lower bound of 3, and m has a lower bound of n and an upper bound of \(3n-6\). The supplied values are adjusted if they are out of these bounds.

◆ randomWattsStrogatzGraph()

void ogdf::randomWattsStrogatzGraph ( Graph G,
int  n,
int  k,
double  probability 
)

Creates a "small world" graph as described by Watts & Strogatz.

Takes a regular lattice graph and, with given probability, rewires each edge to a random other non-neighbor.

Collective dynamics of ‘small-world’ networks https://www.nature.com/articles/30918.pdf

Warning
This implementation does not perform very well if k is close to half of n for large graphs.
Parameters
Gis assigned the generated graph.
nis the number of nodes of the generated graph.
kis the initial degree of each node and must be even and smaller than half of n.
probabilitydetermines how likely each edge is rewired. A probability of 0 will not modify the graph, while one of 1 will cause full randomness.

◆ randomWaxmanGraph()

void ogdf::randomWaxmanGraph ( Graph G,
int  nodes,
double  alpha,
double  beta,
double  width = 1.0,
double  height = 1.0 
)

Generates a Waxman graph where nodes are uniformly randomly placed in a grid, then edges are inserted based on nodes' euclidean distances.

Routing of Multipoint Connections
Bernard M. Waxman (1988)

After generating the nodes, edges are inserted between each pair of nodes v, w with probability based on their euclidean distance \(\beta \exp{\frac{-||v-w||}{m \, \alpha}}\) where \(m:=\max\limits_{u,v}||u-v||\).

Parameters
Gis assigned the generated graph.
nodesis the number of nodes of the generated graph.
alphais a parameter for the probability in the range (0,1]. Small values increase the density of short edges relative to longer ones.
betais a parameter for the probability in the range (0,1]. Large values result in a graph with higher edge density.
widthis the width of the area the nodes are distributed in.
heightis the height of the area the nodes are distributed in.

◆ regularLatticeGraph()

void ogdf::regularLatticeGraph ( Graph G,
int  n,
int  k 
)

Creates a regular lattice graph.

Generates a cycle on n sequential nodes, where any two nodes whose distance is at most k / 2 are connected by an additional edge.

See also
circulantGraph(Graph&, int, Array<int>)
Parameters
Gis assigned the generated graph.
nis the number of nodes in the graph.
kis the degree of each node.
Precondition
n must be at least 4, k must be an even number between 0 and n-2.

◆ regularTree()

void ogdf::regularTree ( Graph G,
int  n,
int  children 
)

Creates a regular tree.

Parameters
Gis assigned the tree.
nis the number of nodes of the tree.
childrenis the number of children per node. root has index 0, the next level has indizes 1...children, the children of node 1 have indizes children+1...2*children, etc. if number of nodes does not allow a regular node, the "last" node will have fewer children.

◆ rootedProduct()

void ogdf::rootedProduct ( const Graph G1,
const Graph G2,
Graph product,
NodeMap nodeInProduct,
node  rootInG2 
)

Computes the rooted product of G1 and G2, rooted in rootInG2, and assigns it to product.

Multi-edges are kept and incorporated into the graph product.

Parameters
G1is the first input graph.
G2is the second input graph.
productis assigned the graph product.
nodeInProductis assigned a mapping from nodes of (G1, G2) to product.
rootInG2is the node of G2 that is identified with every node of G1 once in order to create the rooted product.

◆ strongProduct()

void ogdf::strongProduct ( const Graph G1,
const Graph G2,
Graph product,
NodeMap nodeInProduct 
)

Computes the strong product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_1,w_2\rangle) | (w_1,w_2) \in E_2\} \cup \{(\langle v_1,w_1\rangle, \langle v_2,w_1\rangle) | (v_1,v_2) \in E_1\} \cup \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \in E_1 \land (w_1,w_2) \in E_2\} \).

Multi-edges are kept and incorporated into the graph product.

Parameters
G1is the first input graph.
G2is the second input graph.
productis assigned the graph product.
nodeInProductis assigned a mapping from nodes of (G1, G2) to product.

◆ suspension()

void ogdf::suspension ( Graph G,
int  s 
)

Modifies G by adding its s-th suspension.

A suspension node is a node that is connected to all other nodes in the graph. This function adds s such suspension nodes that will not be directly connected to each other.

Parameters
Gis the graph to extend.
sis the amount of suspension nodes to add.

◆ tensorProduct()

void ogdf::tensorProduct ( const Graph G1,
const Graph G2,
Graph product,
NodeMap nodeInProduct 
)

Computes the tensor product of G1 and G2 and assigns it to product, with \(E = \{(\langle v_1,w_1\rangle, \langle v_2,w_2\rangle) | (v_1,v_2) \in E_1 \land (w_1,w_2) \in E_2\} \).

Multi-edges are kept and incorporated into the graph product.

Parameters
G1is the first input graph.
G2is the second input graph.
productis assigned the graph product.
nodeInProductis assigned a mapping from nodes of (G1, G2) to product.

◆ wheelGraph()

void ogdf::wheelGraph ( Graph G,
int  n 
)

Creates the graph W_n: A wheel graph.

Parameters
Gis assigned the generated graph.
nis the number of nodes on the rim of the wheel (W_n).
Precondition
n must be at least 2.
ogdf::circulantGraph
void circulantGraph(Graph &G, int n, Array< int > jumps)
Creates a circulant graph.
ogdf::Array< int >
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:862
ogdf::graphml::Attribute::G
@ G