pcs.tree {pcSteiner}

Solve the Prize-Collecting Steiner Tree problem

Description

Solve the Prize-Collecting Steiner Tree problem.

Usage

pcs.tree(graph, terminals, lambda, root, depth, eps, max_iter, terminal_infty=10000)

Arguments

graph

an igraph graph.

terminals

a numeric or character vector which contains either ids or names of terminal nodes.

lambda

a numeric parameter which establishes a ratio between edge costs and node prizes (see Sec.1 or Sec.3 in the vignette).

root

a numeric or character scalar which corresponds to either id or name of a root (see Sec.3 in the vignette).

depth

a numeric scalar which sets depth of the resultant tree (see Sec.3 in the vignette).

eps

a numeric scalar which specifies tolerance for termination.

max_iter

a numeric scalar which specifies maximum number of iterations.

terminal_infty

a numeric scalar which corresponds to a prize for each terminal node. This value should be large enough to ensure that all terminals will be presented in a solution.

Value

Returns a list with cost and edges of the final tree.

References

1. M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour, and R. Zecchina, "Statistical Mechanics of Steiner Trees". PRL, 2008.

2. M. Bayati, A. Braunstein, and R. Zecchina, "A rigorous analysis of the cavity equations for the minimum spanning tree". Journal of Mathematical Physics, 2008.

3. I. Biazzo, A. Braunstein and R. Zecchina, "Performance of a cavity-method-based algorithm for the prize-collecting Steiner tree problem on graphs". PRL, 2012.

Examples

g <- graph('Bull')
E(g)$costs  <- c(3, 3, 3, 3, 3)
V(g)$prizes <- c(10, 2, 2, 2, 2)
treeData <- pcs.tree(graph=g, terminals=c(4,5), lambda=1, root=3, depth=5, eps=1e-3, max_iter=10)