| Title: | Convenient Tool for Solving the Prize-Collecting Steiner Tree Problem |
|---|---|
| Description: | The Prize-Collecting Steiner Tree problem asks to find a subgraph connecting a given set of vertices with the most expensive nodes and least expensive edges. Since it is proven to be NP-hard, exact and efficient algorithm does not exist. This package provides convenient functionality for obtaining an approximate solution to this problem using loopy belief propagation algorithm. |
| Authors: | Aleksei Krasikov <[email protected]> |
| Maintainer: | Aleksei Krasikov <[email protected]> |
| License: | GPL-3 |
| Version: | 1.0.0 |
| Built: | 2025-01-23 02:53:19 UTC |
| Source: | https://github.com/krashkov/pcsteiner |
Solve the Prize-Collecting Steiner Tree problem.
pcs.tree(graph, terminals, lambda, root, depth, eps, max_iter, terminal_infty=10000)pcs.tree(graph, terminals, lambda, root, depth, eps, max_iter, terminal_infty=10000)
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. |
Returns a list with cost and edges of the final tree.
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.
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)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)