Provides various graph generator functions. 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 . | |
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 . | |
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. | |
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\}
\). | |
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\}
\). | |
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\}
\). | |
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\}
\). | |
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\}
\). | |
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\}
\). | |
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 . | |
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. | |
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. | |
void | ogdf::circulantGraph (Graph &G, int n, Array< int > jumps) |
Creates a circulant graph. | |
void | ogdf::regularLatticeGraph (Graph &G, int n, int k) |
Creates a regular lattice graph. | |
void | ogdf::regularTree (Graph &G, int n, int children) |
Creates a regular tree. | |
void | ogdf::completeGraph (Graph &G, int n) |
Creates the complete graph K_n. | |
void | ogdf::completeKPartiteGraph (Graph &G, const Array< int > &signature) |
Creates the complete k-partite graph K_{k1,k2,...,kn}. | |
void | ogdf::completeBipartiteGraph (Graph &G, int n, int m) |
Creates the complete bipartite graph K_{n,m}. | |
void | ogdf::wheelGraph (Graph &G, int n) |
Creates the graph W_n: A wheel graph. | |
void | ogdf::cubeGraph (Graph &G, int n) |
Creates the graph Q^n: A n -cube graph. | |
void | ogdf::globeGraph (Graph &G, int meridians, int latitudes) |
Creates a globe graph with a given number of meridians and latitudes. | |
void | ogdf::suspension (Graph &G, int s) |
Modifies G by adding its s -th suspension. | |
void | ogdf::gridGraph (Graph &G, int n, int m, bool loopN, bool loopM) |
Creates a (toroidal) grid graph on n x m nodes. | |
void | ogdf::petersenGraph (Graph &G, int n=5, int m=2) |
Creates a generalized Petersen graph. | |
void | ogdf::emptyGraph (Graph &G, int nodes) |
Creates a graph with nodes nodes and no edges. | |
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. | |
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. | |
void | ogdf::randomHierarchy (Graph &G, int n, int m, bool planar, bool singleSource, bool longEdges) |
Creates a random hierarchical graph. | |
void | ogdf::randomRegularGraph (Graph &G, int n, int d) |
Creates a random d -regular graph. | |
void | ogdf::randomGraph (Graph &G, int n, int m) |
Creates a random graph. | |
bool | ogdf::randomSimpleGraph (Graph &G, int n, int m) |
Creates a random simple graph. | |
bool | ogdf::randomSimpleGraphByProbability (Graph &G, int n, double pEdge) |
Creates a random simple graph. | |
bool | ogdf::randomSimpleConnectedGraph (Graph &G, int n, int m) |
Creates a random simple and connected graph. | |
void | ogdf::randomBiconnectedGraph (Graph &G, int n, int m) |
Creates a random biconnected graph. | |
void | ogdf::randomPlanarConnectedGraph (Graph &G, int n, int m) |
Creates a random connected (simple) planar (embedded) graph. | |
void | ogdf::randomPlanarBiconnectedGraph (Graph &G, int n, int m, bool multiEdges=false) |
Creates a random planar biconnected (embedded) graph. | |
void | ogdf::randomPlanarBiconnectedDigraph (Graph &G, int n, int m, double p=0, bool multiEdges=false) |
Creates a random planar biconnected acyclic (embedded) digraph. | |
void | ogdf::randomUpwardPlanarBiconnectedDigraph (Graph &G, int n, int m) |
Creates a random upward planar biconnected (embedded) digraph. | |
void | ogdf::randomPlanarCNBGraph (Graph &G, int n, int m, int b) |
Creates a random planar graph, that is connected, but not biconnected. | |
void | ogdf::randomTriconnectedGraph (Graph &G, int n, double p1, double p2) |
Creates a random triconnected (and simple) graph. | |
void | ogdf::randomPlanarTriconnectedGraph (Graph &G, int n, int m) |
Creates a random planar triconnected (and simple) graph. | |
void | ogdf::randomPlanarTriconnectedGraph (Graph &G, int n, double p1, double p2) |
Creates a random planar triconnected (and simple) graph. | |
void | ogdf::randomTree (Graph &G, int n) |
Creates a random tree (simpler version. | |
void | ogdf::randomTree (Graph &G, int n, int maxDeg, int maxWidth) |
Creates a random tree. | |
void | ogdf::randomClusterPlanarGraph (ClusterGraph &C, Graph &G, int cNum) |
Assigns random clusters to a given graph G . | |
void | ogdf::randomClusterGraph (ClusterGraph &C, Graph &G, int cNum) |
Assigns random clusters to a given graph G . | |
void | ogdf::randomClusterGraph (ClusterGraph &C, const Graph &G, const node root, int moreInLeaves) |
Assigns a specified cluster structure to a given graph G , and assigns vertices to clusters. | |
void | ogdf::randomDigraph (Graph &G, int n, double p) |
Creates a random (simple) directed graph. | |
void | ogdf::randomSeriesParallelDAG (Graph &G, int edges, double p=0.5, double flt=0.0) |
Creates a random (simple, biconnected) series parallel DAG. | |
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. | |
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. | |
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. | |
void | ogdf::randomWattsStrogatzGraph (Graph &G, int n, int k, double probability) |
Creates a "small world" graph as described by Watts & Strogatz. | |
void | ogdf::randomChungLuGraph (Graph &G, Array< int > expectedDegreeDistribution) |
Creates a graph where edges are inserted based on given weights. | |
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. | |
Provides various graph generator functions.
Definition at line 72 of file operations.h.
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.
G1 | is the first input graph. |
G2 | is the second input graph. |
product | is assigned the graph product. |
nodeInProduct | is assigned a mapping from nodes of (G1 , G2 ) to product . |
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.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
jumps | is the array of distances for edges to be created. ogdf::Graph G;
ogdf::circulantGraph(G, 11, ogdf::Array<int>({1,2,4}));
Data type for general directed graphs (adjacency list representation). Definition Graph_d.h:521 void circulantGraph(Graph &G, int n, Array< int > jumps) Creates a circulant graph. |
Creates the complete bipartite graph K_{n,m}.
The returned graph is directed acyclic.
G | is assigned the generated graph. |
n | is the number of nodes of the first partition set. |
m | is the number of nodes of the second partition set. |
Creates the complete graph K_n.
The returned graph is directed acyclic.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
Creates the complete k-partite graph K_{k1,k2,...,kn}.
The returned graph is directed acyclic.
G | is assigned the generated graph. |
signature | contains the positive values k1, k2, ..., kn. |
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.
G1 | is the first input graph. |
G2 | is the second input graph. |
product | is assigned the graph product. |
nodeInProduct | is assigned a mapping from nodes of (G1 , G2 ) to product . |
Creates the graph Q^n: A n
-cube graph.
G | is assigned the generated graph. |
n | is the number of the cube's dimensions (n>=0). |
Creates a custom graph using a list of pairs to determine the graph's edges.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
edges | is a list of pairs, each one representing two nodes that should be connected by an edge in the generated graph. |
Definition at line 59 of file deterministic.h.
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.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
edges | is a list of pairs, each one representing two nodes that should be connected by an edge in the generated graph. |
nodes | resulting array mapping node index to the actual node |
Creates a graph with nodes
nodes and no edges.
G | is assigned the generated graph. |
nodes | is the number of nodes of the generated graph. |
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.
G | is assigned the generated graph. |
meridians | is the number of meridians. |
latitudes | is the number of latitudes. |
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)\).
G1 | is the first input graph. |
G2 | is the second input graph. |
product | is assigned the graph product. |
nodeInProduct | is assigned a mapping from nodes of (G1 , G2 ) to product . |
addEdges | A function that adds edges to the graph product for each pair of nodes in \(V(G1) \times V(G2)\). |
Forms the disjoint union of G1
and G2
.
G1 | is the first graph and assigned the graph union. |
G2 | is the second graph. |
Definition at line 52 of file operations.h.
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
.
G1 | is the first graph and assigned the graph union. |
G2 | is the second graph. |
map2to1 | identifies 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 . |
parallelfree | sets whether the resulting graph union should not contain multi-edges. |
directed | sets whether the graph union is treated as directed or undirected when detecting multi-edges. It only has an effect if parallelfree is set. |
Creates a (toroidal) grid graph on n
x m
nodes.
G | is assigned the generated graph. |
n | is the number of nodes on first axis. |
m | is the number of nodes on second axis. |
loopN | if the grid is cyclic on first axis |
loopM | if the grid is cyclic on second axis |
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\}
\).
Multi-edges are kept and incorporated into the graph product.
G1 | is the first input graph. |
G2 | is the second input graph. |
product | is assigned the graph product. |
nodeInProduct | is assigned a mapping from nodes of (G1 , G2 ) to product . |
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.
G1 | is the first input graph. |
G2 | is the second input graph. |
product | is assigned the graph product. |
nodeInProduct | is assigned a mapping from nodes of (G1 , G2 ) to product . |
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
.
G | is assigned the generated graph. |
n | is the number of nodes on the outer cycle. |
m | is the length of jumps for the inner part. |
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.
G | is the input graph (see above) and is assigned the expanded graph. |
nodes | is the number of nodes to be added to graph. |
minDegree | is the minimum degree of new nodes. |
Creates a random biconnected graph.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
m | is the number of edges of the generated graph. |
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. 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\).
G | is assigned the generated graph. |
expectedDegreeDistribution | is a list of expected degrees, or weights, for the individual nodes. Its length defines the number of nodes n. |
void ogdf::randomClusterGraph | ( | ClusterGraph & | C, |
const Graph & | G, | ||
const node | root, | ||
int | moreInLeaves | ||
) |
Assigns a specified cluster structure to 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)
C | is a cluster graph for G , to be assigned the solution. |
G | is the input graph. |
root | is 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. |
moreInLeaves | is a factor such that leaf-clusters have on average moreInLeaves-times more vertices than inner clusters |
G
contains at least twice as many nodes as T has leaves. void ogdf::randomClusterGraph | ( | ClusterGraph & | C, |
Graph & | G, | ||
int | cNum | ||
) |
Assigns random clusters to a given graph G
.
This function is called with a graph G
and creates randomly clusters.
G | is the input graph. |
C | is a cluster graph for G . |
cNum | is the maximal number of clusters introduced. |
G
is connected and not empty and C
is initialized with G
. void ogdf::randomClusterPlanarGraph | ( | ClusterGraph & | C, |
Graph & | G, | ||
int | cNum | ||
) |
Assigns random clusters to a given graph G
.
This function is called with a graph G
and creates randomly clusters. The resulting cluster graph is always c-connected and, if G is planar, also c-planar.
G | is the input graph. |
C | is a cluster graph for G . |
cNum | is the maximal number of Clusters introduced. |
G
is connected and not empty and C is initialized with G. Creates a random (simple) directed graph.
G | is assigned the generated graph. |
n | is the number of nodes in the generated graph. |
p | is the probability that an edge is created (for each node pair) |
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:
G | is a graph that should have at least two nodes (so edges can be generated) |
probability | is a callback function that, for any given pair of nodes, returns a probability between 0 and 1 for the two nodes to be connected. |
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.
D | the random distribution to use (see dist ). |
G | is assigned the generated graph. |
weights | has the weights for all nodes in the graph. |
dist | is 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 | is the threshold for edge insertion. |
alpha | is the constant in the heuristic function. |
dimension | is the dimension the nodes are laid out in. |
Definition at line 120 of file randomGeographicalThresholdGraph.h.
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}\).
D | the random distribution to use (see dist ). |
G | is assigned the generated graph. |
weights | has the weights for all nodes in the graph. |
dist | is 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 ). |
threshold | is the threshold for edge insertion. |
h | is a function that should be decreasing in the distance supplied to it. |
dimension | is the dimension the nodes are laid out in. |
Definition at line 67 of file randomGeographicalThresholdGraph.h.
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.
G | is assigned the generated graph. |
nodes | is the number of nodes of the generated graph. |
threshold | is threshold radius of nodes which will be connected. |
dimension | is the dimension of the cube. |
Creates a random graph.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
m | is the number of edges of the generated graph. |
void ogdf::randomHierarchy | ( | Graph & | G, |
int | n, | ||
int | m, | ||
bool | planar, | ||
bool | singleSource, | ||
bool | longEdges | ||
) |
Creates a random hierarchical graph.
G | is assigned the generated graph. |
n | is the number of nodes. |
m | is the number of edges. |
planar | determines if the resulting graph is (level-)planar. |
singleSource | determines if the graph is a single-source graph. |
longEdges | determines if the graph has long edges (spanning 2 layers or more); otherwise the graph is proper. |
void ogdf::randomPlanarBiconnectedDigraph | ( | Graph & | G, |
int | n, | ||
int | m, | ||
double | p = 0 , |
||
bool | multiEdges = false |
||
) |
Creates a random planar biconnected acyclic (embedded) digraph.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
m | is the number of edges of the generated graph. |
p | up to m * p edges will be reversed preversing acyclicity; default = 0.0. |
multiEdges | determines if the generated graph may contain multi-edges; default = false. |
d
is between 0.0 and 1.0 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. Creates a random planar biconnected (embedded) graph.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
m | is the number of edges of the generated graph. |
multiEdges | determines if the generated graph may contain multi-edges. |
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. Creates a random planar graph, that is connected, but not biconnected.
G | is assigned the generated graph. |
n | is the max. number of nodes in each biconnected component |
m | is the max. number of edges in each biconnected component |
b | is the number of biconnected components |
Creates a random connected (simple) planar (embedded) graph.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
m | is the number of edges of the generated graph. |
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. 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.
p1
, p2
<= 1.0.G | is assigned the generated graph. |
n | is the number of nodes in the generated graph. |
p1 | is the probability for the first additional edge to be added. |
p2 | is the probability for the second additional edge to be added. |
n
has a lower bound of 4 and will get increased to this if smaller. Creates a random planar triconnected (and simple) graph.
This graph generator works in two steps.
n
nodes and 1.5n
edges.G | is assigned the generated graph. |
n | is the number of nodes in the generated graph. |
m | is the number of edges in the generated graph. |
n
>= 4 and n
must be even; otherwise, n
is adjusted to the next feasible integer.n
<= m
<= 3n
-6; otherwise, m
is adjusted to a feasible value. Creates a random d
-regular graph.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
d | is the degree of each vertex |
n
* d
must be even 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.
G | is assigned the generated graph. |
edges | is 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 |
p
is in \([0.0, 1.0]\), and flt
is in \([0.0, 1.0)\). Creates a random simple and connected graph.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
m | is the number of edges of the generated graph. |
Creates a random simple graph.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
m | is the number of edges of the generated graph. |
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
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
pEdge | is the probability for each edge to be added into the graph. |
Creates a random tree (simpler version.
G | is assigned the tree. |
n | is the number of nodes of the tree. |
Creates a random tree.
G | is assigned the tree. |
n | is the number of nodes of the tree. |
maxDeg | is the maximal allowed node degree; 0 means no restriction. |
maxWidth | is the maximal allowed width of a level; 0 means no restriction. |
maxDeg
or maxWidth
are 0 (or negative), they are set to n
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
p1
;p1
;p1
- p2
.G | is assigned the generated graph. |
n | is the number of nodes in the generated graph. |
p1 | is the probability that an edge is moved only to the left node after splitting a node. |
p2 | is 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.
p1
+ p2
<= 1.0. n
has a lower bound of 4 and will get increased to this if smaller. Creates a random upward planar biconnected (embedded) digraph.
G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
m | is the number of edges of the generated graph. |
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. 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
k
is close to half of n
for large graphs.G | is assigned the generated graph. |
n | is the number of nodes of the generated graph. |
k | is the initial degree of each node and must be even and smaller than half of n . |
probability | determines how likely each edge is rewired. A probability of 0 will not modify the graph, while one of 1 will cause full randomness. |
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||\).
G | is assigned the generated graph. |
nodes | is the number of nodes of the generated graph. |
alpha | is a parameter for the probability in the range (0,1]. Small values increase the density of short edges relative to longer ones. |
beta | is a parameter for the probability in the range (0,1]. Large values result in a graph with higher edge density. |
width | is the width of the area the nodes are distributed in. |
height | is the height of the area the nodes are distributed in. |
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.
G | is assigned the generated graph. |
n | is the number of nodes in the graph. |
k | is the degree of each node. |
n
must be at least 4, k
must be an even number between 0 and n-2
. Creates a regular tree.
G | is assigned the tree. |
n | is the number of nodes of the tree. |
children | is 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. |
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.
G1 | is the first input graph. |
G2 | is the second input graph. |
product | is assigned the graph product. |
nodeInProduct | is assigned a mapping from nodes of (G1 , G2 ) to product . |
rootInG2 | is the node of G2 that is identified with every node of G1 once in order to create the rooted product. |
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.
G1 | is the first input graph. |
G2 | is the second input graph. |
product | is assigned the graph product. |
nodeInProduct | is assigned a mapping from nodes of (G1 , G2 ) to product . |
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.
G | is the graph to extend. |
s | is the amount of suspension nodes to add. |
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.
G1 | is the first input graph. |
G2 | is the second input graph. |
product | is assigned the graph product. |
nodeInProduct | is assigned a mapping from nodes of (G1 , G2 ) to product . |