Tree Generator

This notebook is published under the Creative Commons Attribution 3.0 Unported license.

Introduction

We demonstrate a simple (?) function to generate a random tree (a connected, cycle-free undirected graph with a single root node).

Libraries used

The graph generation function is self-contained (uses only elements of base R). To display the graph, we import the DiagrammeR package.

library(DiagrammeR)

Function definition

The following function generates a random tree graph with a specified number of nodes and a specified number of layers. Every layer contains at least one node, with the first layer containing exactly one node (the root of the tree). The user can specify names to be assigned (randomly or in raster scan order) to the nodes. By default, the nodes are named with their index numbers.

The tree is output as an \((N-1)\times 2\) matrix of edges, where \(N\) is the number of nodes. The user can choose whether to order the edges (matrix rows) by the node names (which is the default choice), by layer, or randomly.

#
# This script defines a function `randomTree` that generates a random tree (connected acyclic graph)
# and outputs it in the form of a matrix of edges.
#
# Inputs:
#   nodes = the number of nodes in the tree (>= 1)
#   layers = the number of layers in the tree (>= 1, <= nodes)
#   node_labels = an optional vector of labels for the nodes (1 : nodes if omitted)
#   label_order = the order to apply node labels to nodes ("R" = random order (default),
#                "S" = raster scan order (top to bottom, left to right))
#   edge_order = the order of edges in the edge list ("N" = ordered by name (default),
#                "L" = ordered by layer, "R" = random)
#
# Output:
#   an (N-1) x 2 matrix of edges in the tree, where N is the number of nodes
#
randomTree <- function(nodes, layers, node_labels = NULL, label_order = "R", edge_order = "N") {
  ## Process the arguments.
  # Check the requested dimensions.
  if (nodes <= 1) {
    stop("The number of nodes must be at least 2.")
  } else if (layers > nodes) {
    stop("The tree cannot contain more layers than nodes.")
  }
  # Process the node labels argument.
  if (is.null(node_labels)) {
    node_labels <- 1:nodes
  } else if (length(node_labels) < nodes) {
    stop("An insufficient number of node labels was provided.")
  }
  # If the edge order argument is not one of the choices, default it to "N".
  edge_order <- toupper(edge_order)
  if (!edge_order %in% c("N", "L", "R")) {
    edge_order <- "N"
  }
  # If the label order argument is not one of the choices, default it to "R".
  label_order <- toupper(label_order)
  if (!label_order %in% c("S", "R")) {
    label_order <- "R"
  }
  ## Create a data frame of nodes.
  # Randomly generate a layer for every node, ensuring that no layer is empty and that the first
  # layer is a singleton.
  layer_no <- c(1:layers, sample(2:layers, size = nodes - layers, replace = TRUE)) |> sort()
  # Initialize a data frame with a row for every node, containing the nodel index and layer number
  # and a placeholder for the predecessor.
  df <- data.frame(
    Label = 1:nodes,
    Layer = layer_no,
    Predecessor = NA
  )
  # Compute the layer sizes.
  layer_size <- tabulate(layer_no)
  # Proceed layer by layer, assigning predecessors randomly from the previous layer.
  previous <- df[df$Layer == 1, "Label"]  # labels of nodes in the previous layer
  for (i in 2:layers) {
    parents <- unique(df[df$Layer == i - 1, "Label"])
    df[df$Layer == i, "Predecessor"] <- 
      parents |> sample(size = layer_size[i], replace = TRUE) |> sort()
  }
  # Randomize the node labels if desired.
  if (label_order == "R") {
    node_labels <- sample(node_labels, nodes, replace = FALSE)
  }
  # Replace label and predecessor numbers with the corresponding labels.
  df$Label <- node_labels[df$Label]
  df$Predecessor <- node_labels[df$Predecessor]
  # Drop the first row (root node) and sort the rest of the data frame according to the `edge_order`
  # argument.
  df <- df[-1, ]
  if (edge_order == "L") {
    # Sort by layer.
    df <- df[order(df$Layer), ]
  } else if (edge_order == "R") {
    # Randomize the order of the rows.
    df <- df[sample.int(nodes - 1, size = nodes - 1, replace = FALSE), ]
  } else {
    # Order the rows by the predecessor label first, node label second.
    df <- df[with(df, order(df$Predecessor, df$Label)), ]
  }
  ## Produce a matrix of edges.
  edges <- as.matrix(df[, c("Predecessor", "Label")])
  colnames(edges) <- c("Tail", "Head")
  # Get rid of row names (indices).
  rownames(edges) <- NULL
  # Return the result
  edges
}

Demonstration

We demonstrate the use of the function by generating an example tree, naming the nodes with capital letters.

# Set the random seed (for reproducibility).
set.seed(12345)
# Set the tree size (number of nodes, number of layers) and node labels.
nNodes <- 15
nLayers <- 4
node_names <- LETTERS[1:nNodes]
# Generate the tree as a matrix of edges, with node labels randomized and edges in name order.
tree <- randomTree(nNodes, nLayers, node_names, "R", "N")

This is the edge matrix (ordered by node name).

tree

      Tail Head
 [1,] "B"  "E" 
 [2,] "B"  "K" 
 [3,] "B"  "O" 
 [4,] "G"  "F" 
 [5,] "I"  "M" 
 [6,] "I"  "N" 
 [7,] "J"  "A" 
 [8,] "M"  "B" 
 [9,] "M"  "C" 
[10,] "M"  "H" 
[11,] "M"  "L" 
[12,] "N"  "D" 
[13,] "N"  "G" 
[14,] "N"  "J" 

We can plot the graph to verify that it is a rooted tree.

# Create a data frame of nodes.
nodes <- create_node_df(nNodes, label = node_names)
# Convert the edge tails and heads from character to integer.
nodeID <- function(x) nodes[nodes$label == x, "id"]
arcs <- create_edge_df(from = sapply(tree[, "Tail"], nodeID),
                       to = sapply(tree[, "Head"], nodeID))
# Create a graph object.
graph <- create_graph(nodes_df = nodes, edges_df = arcs, directed = TRUE)
render_graph(graph, layout = "tree")

We can produce the same graph but with node labels in raster scan order and the edge matrix in random order.

# Reset the random seed so as to get the same graph structure.
set.seed(12345)
# Generate the tree as a matrix of edges, with node labels in raster scan order and edges
# in random order.
tree <- randomTree(nNodes, nLayers, node_names, "S", "R")
# Display the edge matrix.
tree

      Tail Head
 [1,] "C"  "J" 
 [2,] "G"  "N" 
 [3,] "B"  "E" 
 [4,] "E"  "K" 
 [5,] "C"  "H" 
 [6,] "A"  "C" 
 [7,] "G"  "M" 
 [8,] "B"  "D" 
 [9,] "C"  "I" 
[10,] "A"  "B" 
[11,] "C"  "G" 
[12,] "B"  "F" 
[13,] "G"  "O" 
[14,] "F"  "L" 

We again plot the graph to verify the changes we made. Unfortunately, the rendering process may not preserve the order of nodes within a layer.

# Create a data frame of nodes.
nodes <- create_node_df(nNodes, label = node_names)
# Convert the edge tails and heads from character to integer.
nodeID <- function(x) nodes[nodes$label == x, "id"]
arcs <- create_edge_df(from = sapply(tree[, "Tail"], nodeID),
                       to = sapply(tree[, "Head"], nodeID))
# Create a graph object.
graph <- create_graph(nodes_df = nodes, edges_df = arcs, directed = TRUE)
render_graph(graph, layout = "tree")