# steinertree: Find Steiner Tree In SteinerNet: Steiner Tree Approach for Graph Analysis

## Description

A set of functions for finding Steiner Tree. Includes both exact and heuristic approaches.

## Usage

 ```1 2``` ```steinertree(type, repeattimes = 70, optimize = TRUE, terminals, graph, color = TRUE, merge = FALSE) ```

## Arguments

 `type` a character scalar, which indicates type of algorithms to perform. Can be "EXA", "SP", "KB", "RSP", "SPM" or "ASP". `repeattimes` a numeric scalar to specify "RSP" algorithm; number of times the optimization procedure is repeated. `optimize` a logical scalar to specify all algorithms except "EXA"; if TRUE, an optimization of the resultant steiner tree is performed, otherwise nothing is done. `terminals` a numeric vector (ids of terminals are passed) or character vector (vertices must have 'name' attribute). `graph` an igraph graph; should be undirected, otherwise it is converted to undirected. `color` a logical scalar; whether to return an original graph with terminals colored in red and steiner nodes colored in green. Note, if several trees will be found, steiner nodes from all trees are colored in green. `merge` a logical scalar to specify "EXA" and "SPM" algorithms; if several trees will be found, whether to return a list with trees or merge them

## Details

If input graph doesn't have 'name' attribute, one is created. In this case it will contain character ids of vertices. Also before execution all vertices will be colored in yellow and terminals will be colored in red.

## Value

(color = FALSE) Returns a list first element of which is a steiner tree (or a graph of merged trees). If several steiner trees are found, return a list, each element of which is a steiner tree.

(color = TRUE) Returns a list, first element of which is a colored original graph and second element is a steiner tree (or a graph of merged trees) or list of steiner trees.

## References

1. Path heuristic and Original path heuristic ,Section 4.1.3 of the book "The Steiner tree Problem", Petter,L,Hammer

2. "An approximate solution for the Steiner problem in graphs", H Takahashi, A Matsuyama

3. F K. Hwang, D S. Richards and P Winter, "The steiner tree Problem", Kruskal-Based Heuristic Section 4.1.4, ISBN: 978-0-444-89098-6

4. Afshin Sadeghi and Holger Froehlich, "Steiner tree methods for optimal sub-network identification: an empirical study", BMC Bioinformatics 2013 14:144

5. F K. Hwang, D S. Richards and P Winter, "The steiner tree Problem", Kruskal-Based Heuristic Section 4.1.4, The Optimal solution for steiner trees on networks, ISBN: 978-0-444-89098-6.

`generate_st_samples`
 ```1 2 3 4``` ```steinertree(type = "RSP", optimize = FALSE, terminals = c(1, 3), graph = graph("Cubical"), color = TRUE, merge = FALSE) ```