Introduction

Benchmarking algorithms for (combinatorial) optimization problems is usually carried out by running the set of algorithms on a set of test problems. Often, due to a lack of real-world data, the test set consists of artificially generated benchmark problems. Artificial problems allow for: (1) the generation of arbitrary many instances in short time and (2) the generation of problems of different hardness levels by implementing theoretical knowledge.

Illustrated Workflow

The network drawing below implements a modular graph generation approach with an extensible set of node, edge and weight generators allows for fast and convenient graph generation following a three step approach.

  1. Node generation: here the network topology is definined by placing points in the Euclidean plane.
  2. Edge generation: Links between nodes are established.
  3. Weight generation: Costs/weights are assigned to each edge.

Each of the steps may be repeated multiple times (e.g., first some nodes which serve as cluster centers are added before the clusters are filled with nodes in a subsequent step). Once a step is completed, none of the preceeding steps can be performed anymore. E.g., once some edges are added no more nodes may be added. The process is illustrated in the following diagram.

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: Each edge is added independently with some probability p. This way one can generate Gilbert-graphs G(n, p).
  2. Erdos-Renyi edge generator: 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: 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: 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: 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.

Cases

knitr::opts_chunk$set(collapse = T, comment = "#>", warning = FALSE, message = FALSE, fig.align = "center")
options(tibble.print_min = 4L, tibble.print_max = 4L)

The following code supports the workflow diagram with a first example. Here we generate a complete graph with n = 20 nodes placed uniformly at random in the square [0, 10] x [0, 10]. Two weights are assigned to each edge (both weights are drawn from a U(5, 10)-distribution).

## fig.width=8, fig.height=4.2, out.width='100%', fig.cap='Example network.'
library(grapherator)
set.seed(1) # reproducability
g = graph(lower = 0, upper = 10)
g = addNodes(g, n = 20, generator = addNodesUniform)
g = addEdges(g, generator = addEdgesComplete)
g = addWeights(g, generator = addWeightsRandom, method = runif, min = 5, max = 10)
g = addWeights(g, generator = addWeightsRandom, method = runif, min = 5, max = 10)
print(g)
#> GRAPHERATOR GRAPH
#> #nodes           : 20 (UNG)
#> #edges           : 190 (CEG)
#> #weights per edge: 2 (RWG,RWG)
do.call(gridExtra::grid.arrange, c(plot(g), list(nrow = 1)))

## fig.width=8, fig.height=4.2, out.width='100%', fig.cap='Example network.'
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)))

## fig.width=8, fig.height=4.2, out.width='100%', fig.cap='Example network.'
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           : 938 (WEG)
#> #clusters        : 7
#> #weights per edge: 2 (0.70_CORWG)
do.call(gridExtra::grid.arrange, c(plot(g), list(nrow = 1L)))

## fig.width=8, fig.height=4.2, out.width='100%', fig.cap='Example network.'
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)))