nodeCentricSteinerForestProblem: Solve multiple bootstrap Minimum Steiner Tree problems (aka...

In adamsardar/stoneTrees: Solve Node Centric Steiner Tree Problems

Solve multiple bootstrap Minimum Steiner Tree problems (aka Steiner Forest procedure)

Description

Given a set of seeds/fixed terminals a Minimum Steiner Tree can be found. One might well be interested in studying the common nodes that would be included with, say, just 50 repeatedly sample seeds to produce a consensus set of MStTP solutions. Sub-solutions can also be collected, albeit at an increased burden on the solver (and therefore dramatically increasing the time).

Format

R6Class nodeCentricSteinerForestProblem Construct an object representation of the bootstraped Steiner Tree process (aka Steiner Forest routine)

Details

This class is derived from *subOptimalSteinerProblem* and in turn *nodeCentricSteinerTreeProblem*: all methods available in the superclass are available here. The difference is that after each acceptable solution is found, the solution is a.) stored in a bootstrap solution pool and b.) used to generate a 'novelty' constraint on future solutions. For each bootstrap run, the solution pool is flushed and the process re-rerun. In the end, all of the boostrap solutions are in the bootstrap solution pool.

methods

Alongisde those for *nodeCentricSteinerTreeProblem* and *subOptimalSteinerProblem*

new(network, solverChoice = chooseSolver(), verbose = TRUE, solverTimeLimit = 300, solverTrace = as.integer(verbose), solutionTolerance = 0)

Constructor for the nodeCentricSteinerForestProblem class. Note the loss of 'presolveGraph'; the repeated resampling of fixed terminal nodes prevents this.

sampleMultipleBootstrapSteinerSolutions(nBootstraps = 5, maxItr = 0, resamplingProbability= 0.5)

Run the bootstrap procedure nBootstraps times, each time resampling seeds with pSuccess = resamplingProbability, collecting degenerate or suboptimal solutions for maxItr times.

getBootstrapSolutionPoolGraphs(collapseSols = TRUE)

Either return a list of solutions within tolerance (collapseSols = FALSE) or pool all solutions together and return a single graph (collapseSols = TRUE, defaults)

...

Other methods are self explanatory and likely uninteresting to a general user

'

Super classes

stoneTrees::nodeCentricSteinerTreeProblem -> stoneTrees::subOptimalSteinerProblem -> nodeCentricSteinerForestProblem

Methods

Public methods

• nodeCentricSteinerForestProblem$new()

• nodeCentricSteinerForestProblem$sampleMultipleBootstrapSteinerSolutions()

• nodeCentricSteinerForestProblem$getBootstrapSolutionPool()

• nodeCentricSteinerForestProblem$getNconnectivityConstraintsCallsPool()

• nodeCentricSteinerForestProblem$getSolutionPool()

• nodeCentricSteinerForestProblem$getBootstrapSolutionPoolGraphs()

• nodeCentricSteinerForestProblem$getSolutionPoolGraphs()

• nodeCentricSteinerForestProblem$findSingleSteinerSolution()

• nodeCentricSteinerForestProblem$getInitialSeed()

• nodeCentricSteinerForestProblem$getLatestSeed()

• nodeCentricSteinerForestProblem$getAllSeeds()

• nodeCentricSteinerForestProblem$clone()

Inherited methods

• stoneTrees::nodeCentricSteinerTreeProblem$getConnectivityConstraints()

• stoneTrees::nodeCentricSteinerTreeProblem$getCurrentSolutionGraph()

• stoneTrees::nodeCentricSteinerTreeProblem$getCurrentSolutionScore()

• stoneTrees::nodeCentricSteinerTreeProblem$getEdgeDT()

• stoneTrees::nodeCentricSteinerTreeProblem$getFixedTerminalConstraints()

• stoneTrees::nodeCentricSteinerTreeProblem$getNodeDT()

• stoneTrees::nodeCentricSteinerTreeProblem$getNodeDegreeConstraints()

• stoneTrees::nodeCentricSteinerTreeProblem$getTerminals()

• stoneTrees::nodeCentricSteinerTreeProblem$getTwoCycleConstraints()

• stoneTrees::nodeCentricSteinerTreeProblem$getnConnectivityConstraintsCalls()

• stoneTrees::nodeCentricSteinerTreeProblem$isSolutionConnected()

• stoneTrees::subOptimalSteinerProblem$getNconnectivityConstraintsCalls()

• stoneTrees::subOptimalSteinerProblem$getNoveltyConstraints()

• stoneTrees::subOptimalSteinerProblem$getOptimumScore()

• stoneTrees::subOptimalSteinerProblem$getSolutionPoolScores()

• stoneTrees::subOptimalSteinerProblem$getSolutionTolerance()

• stoneTrees::subOptimalSteinerProblem$identifyMultipleSteinerSolutions()

• stoneTrees::subOptimalSteinerProblem$setSolutionTolerance()

---

Method new()

Usage

nodeCentricSteinerForestProblem$new(
  network,
  solverChoice = chooseSolver(),
  verbose = TRUE,
  solverTimeLimit = 300,
  solutionTolerance = 0,
  solverTrace = as.integer(verbose),
  RNGseed = sample.int(size = 1, .Machine$integer.max)
)

---

Method sampleMultipleBootstrapSteinerSolutions()

Usage

nodeCentricSteinerForestProblem$sampleMultipleBootstrapSteinerSolutions(
  nBootstraps = 5,
  maxItr = 0,
  resamplingProbability = 0.5
)

---

Method getBootstrapSolutionPool()

Usage

nodeCentricSteinerForestProblem$getBootstrapSolutionPool()

---

Method getNconnectivityConstraintsCallsPool()

Usage

nodeCentricSteinerForestProblem$getNconnectivityConstraintsCallsPool()

---

Method getSolutionPool()

Usage

nodeCentricSteinerForestProblem$getSolutionPool()

---

Method getBootstrapSolutionPoolGraphs()

Usage

nodeCentricSteinerForestProblem$getBootstrapSolutionPoolGraphs(
  collapseSols = TRUE
)

---

Method getSolutionPoolGraphs()

Usage

nodeCentricSteinerForestProblem$getSolutionPoolGraphs()

---

Method findSingleSteinerSolution()

Usage

nodeCentricSteinerForestProblem$findSingleSteinerSolution(maxItr = 20)

---

Method getInitialSeed()

Usage

nodeCentricSteinerForestProblem$getInitialSeed()

---

Method getLatestSeed()

Usage

nodeCentricSteinerForestProblem$getLatestSeed()

---

Method getAllSeeds()

Usage

nodeCentricSteinerForestProblem$getAllSeeds()

---

Method clone()

The objects of this class are cloneable with this method.

Usage

nodeCentricSteinerForestProblem$clone(deep = FALSE)

Arguments

deep

Whether to make a deep clone.

References

Fischetti M, Leitner M, Ljubić I, Luipersbeck M, Monaci M, Resch M, et al. Thinning out Steiner trees: a node-based model for uniform edge costs. Math Program Comput. dimacs11.cs.princeton.edu; 2017;9: 203–229.

Beisser D, Klau GW, Dandekar T, Müller T, Dittrich MT. BioNet: An R-Package for the functional analysis of biological networks. Bioinformatics. 2010;26: 1129–1130.

https://en.wikipedia.org/wiki/Steiner_tree_problem

See Also

nodeCentricSteinerTreeProblem

subOptimalSteinerProblem

Other SteinerProblemSolver: nodeCentricSteinerTreeProblem, subOptimalSteinerProblem

Examples

library(igraph)

#Prepare a simple seed-based Steiner sampling in a reasonable sized network

fixedTerminalLymphomaGraph = lymphomaGraph
V(fixedTerminalLymphomaGraph)$isTerminal = FALSE
V(fixedTerminalLymphomaGraph)[nodeScore > 0]$isTerminal = TRUE
fixedTerminalLymphomaGraph = delete_vertex_attr(fixedTerminalLymphomaGraph, "nodeScore")


# Example of solving *just* the single-solution Minimum Steiner Tree Problem
MStTPsingle = nodeCentricSteinerTreeProblem$new(fixedTerminalLymphomaGraph)
MStTPsingle$findSingleSteinerSolution()

#Solve multiple bootstrap Steiner Trees (Steiner Forest)
SteinFor = nodeCentricSteinerForestProblem$new(fixedTerminalLymphomaGraph)

#Run two bootstrap routines (resample fixed terminals and solve) and 
#ALSO run the sub-optimal solution searcher thrice
SteinFor$sampleMultipleBootstrapSteinerSolutions(nBootstraps = 2, maxItr = 3)
## Takes around a minute using RGLPK as the solver

adamsardar/stoneTrees documentation built on May 20, 2022, 7:38 p.m.