knitr::opts_chunk$set( collapse = TRUE, comment = "#>" )

This vignette document sets the following goals:

- point out the discrepancy between the descriptions of algorithms in the original article and in the package
- provide several examples of working with the library
- provide a workflow to reproduce results of the original article (since several function was slightly changed in version 3.0)

Note, that here you do not find detailed explanation of all algorithms. For that purposes, see the original article.

The Steiner tree problem on unweighted graphs seeks a minimum subtree (i.e. subtree with minimal number of edges), containing a given subset of the vertices (terminals). This problem is NP-complete. This package provides several heuristic and one exact approach for finding Steiner trees, as well as tools for analyzing resultant trees and comparing different algorithms. This R package was originally applied to analyzing biological networks.

Heuristic approaches:

- shortest paths based approximation (SP)
- minimum spanning tree based approximation (KB)
- randomized all shortest paths approximation (RSP)
- all shortest paths between terminals (ASP)
- (SPM)

Before we start, let's attach several packages.

library(igraph) library(SteinerNet)

As an example of graph, we are going to take well-known "Cubical" graph. Also let's randomly pick 4 terminals using `generate_st_samples`

. We also specify `prob`

variable, so at each step of random walk procedure node is accepted with probability `prob = 0.1`

.

g <- graph("Cubical") set.seed(4) terminal_nodes <- generate_st_samples(graph = g, ter_number = 2, prob = 0.1) terminal_nodes

As we can see, there is only one element in a list and it contains ids of selected vertices. Of course, we can generate more sets of terminals (e.g. pass a vector to ter_number variable), but we do not need it now.

V(g)$color <- "yellow" V(g)[terminal_nodes[[1]]]$color <- "red" plot(g)

`repeattimes`

, and `merge`

variables are ignored for "SP".

steinertree(type = "SP", terminals = terminal_nodes[[1]], graph = g, color = FALSE, merge = FALSE)

**Note, that in 3.0 version (as well as in 2.0 version) Steiner trees with different randomly chosen start nodes are not repetitively constructed, as it is written in article.** This can be done by hand as follows:

tree_list <- c() for (i in 1:20) tree_list[[i]] <- steinertree(type = "SP", terminals = terminal_nodes[[1]], graph = g, color = FALSE, merge = FALSE) # calculate sizes of trees tree_list_len <- unlist(lapply(tree_list, function (x) length(E(x[[1]])))) # select trees with minimal size index <- which(tree_list_len == min(tree_list_len))

`repeattimes`

, and `merge`

variables are ignored for "KB".

steinertree(type = "KB", terminals = terminal_nodes[[1]], graph = g, color = FALSE, merge = FALSE)

`merge`

variable is ignored for "RSP".

steinertree(type = "RSP", terminals = terminal_nodes[[1]], graph = g, color = FALSE, merge = FALSE)

This method is provided **only for comparison reasons**. In version 2.0 it was hidden, however it is now available for the sake of convenience.

`repeattimes`

, and `merge`

variables are ignored for "ASP".

steinertree(type = "ASP", terminals = terminal_nodes[[1]], graph = g, color = FALSE, merge = FALSE)

Note, that this method can find multiple exact solutions, if they exist. In the following example we specify `merge`

variable equals to `FALSE`

, because we want to get a list of steiner trees.

`repeattimes`

and `optimize`

variables are ignored for "EXA".

steinertree(type = "EXA", terminals = terminal_nodes[[1]], graph = g, color = FALSE, merge = FALSE)

As we can see, two steiner trees are found.

"SPM" algorithm can return multiple graphs. Note, that in article this method is called "STM".

steinertree(type = "SPM", terminals = terminal_nodes[[1]], graph = g, color = FALSE, merge = FALSE)

Optimization means returning the minimum spanning tree on resultant graph and removing all non-terminal nodes of degree one. **Note, that in version 2.0 this function was run by default for several algorithms.** Again it is explicitly available in version 3.0 for the sake of convenience.

If you want to reproduce results of the article, you need to specify `optimize = TRUE`

for the following algorithms:

- "SP"
- "KB"
- "RSP"
- "SPM"

For "EXA" algorithm this option is ignored. **Note, that in version 2.0 for "ASP" algorithm optimization was not avaliable at all.** It means, that experiments was conducted without further optimization.

For experiments terminal sets of the following size are used:

- 50 sets with 5 randomly selected terminals
- 50 sets with 8 randomly selected terminals
- etc.

All vertices was selected with 0.5 probability. Therefore in `generate_st_samples`

you probably passed the following:

# in version 2.0 # eval = FALSE listofterminaltest <- c(5, 8, 15, 50, 70) repetition <- rep(x = 0.5, 50)

However, simultaneous work with the number of terminals selected and size of sets makes an output of some function too wired. So now you need to specify:

`ter_number`

. Each element indicates the number of terminals to be selected and length of vector indicates the number of terminal sets to be picked.`prob`

. prob[i] defines a propability with which each next node accepted or rejected while selecting ter_number[i] terminals. Usually this probability is the same for all terminals, so you may write something like this`prob = rep(0.5, #len of ter_number#)`

The main difference is that you can now operate with **only one value** of number of terminal sets. So to reproduce results of the article, firstly, you need, for example, generate 50 terminal sets with 5 terminals in each.

# in version 3.0 # eval = FALSE generate_st_samples(graph = #your graph#, ter_number = rep(x = 5, 50), prob = rep(x = 5, 50))

After running some simulations, secondly, you may want to generate 50 terminal sets with 8 terminals in each.

# in version 3.0 # eval = FALSE generate_st_samples(graph = #your graph#, ter_number = rep(x = 8, 50), prob = rep(x = 8, 50))

**Any scripts or data that you put into this service are public.**

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.