Node generators

1. Uniform node generator: Nodes / node coordinates are placed uniformly at random within the bounds.
2. LHS node generator: A Latin-Hypercube-Sample (LHS) is used to place nodes in the Euclidean plane. This is useful if one aims to place cluster centers in a space-filling manner.
3. Grid node generator: Nodes are placed in regular grid.
4. Triangular node generator: Nodes are placed in a grid. Each second line is shifted.

Edge generators

1. Gilbert edge generator [ER59]: Each edge is added independently with some probability p. This way one can generate Gilbert-graphs G(n, p).
2. Erdos-Renyi edge generator [ER59]: m random edges are added.
3. Delauney edge generator: The set of edges added to the graph is based on a Delauney triangulation of the node coordinates.
4. Complete edge generator: All n(n-1)/2 edges are added.
5. Waxman edge generator (Waxman 1988): Edges are added according to Waxman’s prbablistic model.
6. Onion edge generator: The convex hull of the nodes in the Euclidean plane is computed and neighbouring nodes are linked. The process is repeated with the remaining nodes until all nodes are processed.
7. Spanning tree edge generator: A full weight matrix with U(0, 1) distributed random weights is generated internally and a spanning tree is computed based on these weights. All edges of the spanning tree are added.

Weight generators

1. Random weight generator: Edge weights are assigned randomly following a parameterizable probability distribution.
2. Correlated weight generator (Knowles and Corne 2001): Generates two weights per edge. The first weight corresponds to the Euclidean distance between the nodes. The second weight is generated in a way, that both weights are correlated with a predefined correlation rho.
3. Concave weight generator (Knowles and Corne 2001): This is in particular useful for studying the behaviour of algorithms for the multi-criteria spanning tree problem, since the Pareto-front exhibits a concave shape if this weight generator is used to create the weights of the graph.
4. Distance based generator: Weights correspond to some distance metric between the nodes. Internally, the stats::dist function is called.

Custom generators are possible. See the HowTo on custom generators for an example.

Examples

Here, 50 nodes are placed uniformly at random in the square [0, 100] x [0, 100]. Edges are based on a Delauney triangulation. Both weights are random. The first weight is sampled from a uniform distribution U(10, 20), the second one follows a Gaussian distribution N(10, 2).

library(grapherator)
set.seed(1) # reproducability
g = graph(lower = 0, upper = 100)
g = addNodes(g, n = 50, generator = addNodesUniform)
g = addEdges(g, generator = addEdgesDelauney)
g = addWeights(g, generator = addWeightsRandom, method = runif, min = 10, max = 20)
g = addWeights(g, generator = addWeightsRandom, method = rnorm, mean = 10, sd = 2)
print(g)
#> GRAPHERATOR GRAPH
#> #nodes           : 50 (UNG)
#> #edges           : 137 (DEG)
#> #weights per edge: 2 (RWG,RWG)
do.call(gridExtra::grid.arrange, c(plot(g), list(nrow = 1L)))

Example network.

In the following example a clustered graph with 7 clusters is generated. Cluster centers are based on a min-max Latin-Hypercube-Sample (LHS). In a subsequent step, 29 further points are added to each cluster by samling from a uniform distribution U(0, 5) around the cluster center. Edges are based on Waxman’s model with parameters alpha = 0.3, beta = 0.1. Weights are correlated with negative correlation rho = -0.7.

library(grapherator)
set.seed(1) # reproducability
g = graph(lower = c(0, 50), upper = c(100, 100))
#g = addNodes(g, n = 7, generator = addNodesUniform)
g = addNodes(g, n = 7, generator = addNodesLHS)
g = addNodes(g, n = 29, by.centers = TRUE, generator = addNodesUniform, lower = c(0, 0), upper = c(10, 10))
g = addEdges(g, generator = addEdgesWaxman, alpha = 0.3, beta = 0.1)
g = addWeights(g, generator = addWeightsCorrelated, rho = 0.7)
print(g)
#> GRAPHERATOR GRAPH
#> #nodes           : 210 (LHSNG,CLUNG)
#> #edges           : 823 (WEG)
#> #clusters        : 7
#> #weights per edge: 2 (0.70_CORWG)
do.call(gridExtra::grid.arrange, c(plot(g), list(nrow = 1L)))

Example network.

The last example is a another clustered network. Here, 5 cluster centers are placed manually by providing the center coordinates. Next, each cluster is crowded with 10 nodes by sampling node coordinates from a N(1, 0.2)-distribution each. Edges are added in two steps: first we add edges for each cluster seperately at random. In addition – to ensure connectivity – we add edges with the spanning tree edge generator. Next, the cluster centers are linked with another generator. The first weight is the Manhattan distance between the nodes in the plane. The second follows an exponential distribution with rate = 0.1.

library(grapherator)
set.seed(1) # reproducability
g = graph(lower = 0, upper = 100)
g = addNodes(g, n = 5, coordinates = matrix(c(10, 10, 20, 20, 30, 30, 10, 20, 40, 10), byrow = 2, ncol = 2))
g = addNodes(g, n = 10, by.centers = TRUE, generator = addNodesNormal, x.mean = 5, y.mean = 5, x.sd = 2, y.sd = 2, lower = c(0, 0), upper = c(10, 10))
g = addEdges(g, generator = addEdgesGilbert, p = 0.2, type = "intracluster")
g = addEdges(g, generator = addEdgesSpanningTree, type = "intracluster")
g = addEdges(g, generator = addEdgesDelauney, type = "intercenter")
g = addWeights(g, generator = addWeightsDistance, method = "manhattan")
g = addWeights(g, generator = addWeightsRandom, method = rexp, rate = 0.1)
print(g)
#> GRAPHERATOR GRAPH
#> #nodes           : 55 (MANNG,CLNNG)
#> #edges           : 116 (CLGilEG,CLSTEG,DEG)
#> #clusters        : 5
#> #weights per edge: 2 (DWG,RWG)
do.call(gridExtra::grid.arrange, c(plot(g), list(nrow = 1L)))

Example network.