nodeCentricSteinerTreeProblem: Solve Steiner problems (MStTP or MWCS) with uniform or no...

In adamsardar/stoneTrees: Solve Node Centric Steiner Tree Problems

Solve Steiner problems (MStTP or MWCS) with uniform or no edge weights.

Description

The base stoneTrees class for solving Steiner Tree problems. Each object constructed represents a single Steiner problem and the associated methods allow for modifications, solution generation etc. See *examples* below.

Format

R6Class nodeCentricSteinerTreeProblem Construct an object representation of a Steiner tree/maximum weight connected subgraph (MWCS) problem, with methods to find solutions

Details

Input networks must be single component igraph objects with node attributes detailing forced node inclusion in solution ($isTerminal = TRUE) and/or node costs or prizes for inclusion ($nodeScore).

Methods

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

Constructor for object. Most options can be left as default, but one can set verbose (boolean) and solverTrace (integer - see ?cplexAPI::CPX_PARAM_SCRIND) as desired to prevent output.

findSingleSteinerSolution()

Initiate a search for a connected solution to the CURRENT constraints. For derived classes this can mean that the solution changes.

getCurrentSolutionGraph()

Retrieve the current solution graph (could be disconnected)

get*Constraints()

Extract relevant constraints

getCurrentSolutionScore()

Compute the objective value of the current solution.

...

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

Methods

Public methods

• nodeCentricSteinerTreeProblem$new()

• nodeCentricSteinerTreeProblem$isSolutionConnected()

• nodeCentricSteinerTreeProblem$getCurrentSolutionGraph()

• nodeCentricSteinerTreeProblem$getCurrentSolutionScore()

• nodeCentricSteinerTreeProblem$getTerminals()

• nodeCentricSteinerTreeProblem$findSingleSteinerSolution()

• nodeCentricSteinerTreeProblem$getNodeDT()

• nodeCentricSteinerTreeProblem$getEdgeDT()

• nodeCentricSteinerTreeProblem$getnConnectivityConstraintsCalls()

• nodeCentricSteinerTreeProblem$getFixedTerminalConstraints()

• nodeCentricSteinerTreeProblem$getNodeDegreeConstraints()

• nodeCentricSteinerTreeProblem$getTwoCycleConstraints()

• nodeCentricSteinerTreeProblem$getConnectivityConstraints()

• nodeCentricSteinerTreeProblem$clone()

---

Method new()

Usage

nodeCentricSteinerTreeProblem$new(
  network,
  solverChoice = chooseSolver(),
  verbose = TRUE,
  presolveGraph = TRUE,
  solverTimeLimit = 300,
  solverTrace = as.integer(verbose)
)

---

Method isSolutionConnected()

Usage

nodeCentricSteinerTreeProblem$isSolutionConnected()

---

Method getCurrentSolutionGraph()

Usage

nodeCentricSteinerTreeProblem$getCurrentSolutionGraph()

---

Method getCurrentSolutionScore()

Usage

nodeCentricSteinerTreeProblem$getCurrentSolutionScore()

---

Method getTerminals()

Usage

nodeCentricSteinerTreeProblem$getTerminals()

---

Method findSingleSteinerSolution()

Usage

nodeCentricSteinerTreeProblem$findSingleSteinerSolution(maxItr = 20)

---

Method getNodeDT()

Usage

nodeCentricSteinerTreeProblem$getNodeDT()

---

Method getEdgeDT()

Usage

nodeCentricSteinerTreeProblem$getEdgeDT()

---

Method getnConnectivityConstraintsCalls()

Usage

nodeCentricSteinerTreeProblem$getnConnectivityConstraintsCalls()

---

Method getFixedTerminalConstraints()

Usage

nodeCentricSteinerTreeProblem$getFixedTerminalConstraints()

---

Method getNodeDegreeConstraints()

Usage

nodeCentricSteinerTreeProblem$getNodeDegreeConstraints()

---

Method getTwoCycleConstraints()

Usage

nodeCentricSteinerTreeProblem$getTwoCycleConstraints()

---

Method getConnectivityConstraints()

Usage

nodeCentricSteinerTreeProblem$getConnectivityConstraints()

---

Method clone()

The objects of this class are cloneable with this method.

Usage

nodeCentricSteinerTreeProblem$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

Other SteinerProblemSolver: nodeCentricSteinerForestProblem, subOptimalSteinerProblem

Examples

library(igraph)

 # Minimum Steiner tree problem

 ## Boolean flags on vertices mark out 'seeds' (nodes that *must* be included)
 unique(V(karateGraph)$isTerminal)
 V(karateGraph)[isTerminal]

 karateMStTP = nodeCentricSteinerTreeProblem$new(karateGraph)
 karateMStTP$findSingleSteinerSolution()

 # Maximum-Weight Connected Subgraph (MWCS)

 ## Vertex attribute details node costs/prizes
 head(V(lymphomaGraph)$nodeScore)

 lymphomaMWCS = nodeCentricSteinerTreeProblem$new(lymphomaGraph)
 lymphomaMWCS$findSingleSteinerSolution()

 # A blend of the two approaches

 ## Say there are some nodes (e.g. drug binding targets) that *must* be included, 
 
 # but otherwise node inclusion should follow node scores
 V(lymphomaGraph)$isTerminal = FALSE
 ## Choose some random nodes to be seeds
 V(lymphomaGraph)[name %in% c("4","8","15","16","23","42")]$isTerminal = TRUE

 hybridSteinProb = nodeCentricSteinerTreeProblem$new(lymphomaGraph)
 hybridSteinProb$findSingleSteinerSolution()

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