APSP fix and new method to track the number of connectivity contstraints cycles

[JulieBorgel]

Bug fixed

• APSP function calculates all shortest paths from all vertices to all vertices.

New functionality

• method to track the number of disconnected solutions are found before finding a connected solution . This can be useful for exploratory analysis but there might be a better way to do that.

[JulieBorgel]

here is an example to get the number of disconnected solutions :

devtools::load_all()

library(igraph)

fixedTerminalLymphomaGraph <- lymphomaGraph

V(fixedTerminalLymphomaGraph)$isTerminal <- FALSE

V(fixedTerminalLymphomaGraph)[nodeScore > 0]$isTerminal <- TRUE

V(fixedTerminalLymphomaGraph)$nodeScore <- -1

##Single Steiner Solution
singleStT <- nodeCentricSteinerTreeProblem$new(fixedTerminalLymphomaGraph,
                                            solverChoice = "cplexAPI",
                                            verbose = TRUE,
                                            solverTrace = 0)
Adding 52 fixed terminal constraints ...
Adding 2019 node degree inequality constraints ...
Adding 0 two-cycle constraints ...
No connectivity constraints to add at this stage ...

singleStT$findSingleSteinerSolution()
SOLVING ...
##Solution is disconnected!##
With 85 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 6 component(s).
Adding 460 connectivity constraints based on node-separators ...
SOLVING ...
##Solution is disconnected!##
With 87 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 3 component(s).
Adding 327 connectivity constraints based on node-separators ...
SOLVING ...
##Solution is disconnected!##
With 87 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 3 component(s).
Adding 196 connectivity constraints based on node-separators ...
SOLVING ...
##Solution is disconnected!##
With 87 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 2 component(s).
Adding 100 connectivity constraints based on node-separators ...
SOLVING ...
##Solution is connected!##
With 87 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 1 component(s).
IGRAPH 40b6006 UN-- 102 141 -- 
+ attr: nodeNameSep (g/c), SearchNetwork (g/c), name (v/c), nodeScore
| (v/n), isTerminal (v/l)
+ edges from 40b6006 (vertex names):
 [1] 57 --58  58 --59  77 --78  58 --96  77 --96  96 --106 77 --143 90 --143
 [9] 137--143 77 --155 143--155 123--180 59 --380 28 --429 143--473 180--491
[17] 490--501 62 --512 77 --512 380--512 393--512 429--512 473--512 323--522
[25] 96 --543 143--543 180--543 77 --556 255--556 512--556 59 --586 96 --586
[33] 490--599 62 --615 77 --650 143--650 28 --653 96 --670 269--670 28 --675
[41] 143--675 290--675 528--696 586--696 58 --731 730--731 39 --745 58 --745
[49] 380--745 528--745 512--766 96 --769 528--769 543--769 702--769 96 --771
+ ... omitted several edges
#how many disconnected solution were found before finding a connected solution.
singleStT$getnConnectivityConstraintsCalls()
[1] 4

##minimum steiner tree collecting multiple degenerated solutions
MStT <- subOptimalSteinerProblem$new(fixedTerminalLymphomaGraph,
                                            solverChoice = "cplexAPI",
                                            verbose = TRUE,
                                            solverTrace = 0)$identifyMultipleSteinerSolutions(maxItr = 5)
Adding 52 fixed terminal constraints ...
Adding 2019 node degree inequality constraints ...
Adding 0 two-cycle constraints ...
No connectivity constraints to add at this stage ...
Adding 0 novelty constraint(s) ...
SOLVING ...
##Solution is disconnected!##
With 85 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 6 component(s).
Adding 460 connectivity constraints based on node-separators ...
SOLVING ...
##Solution is disconnected!##
With 87 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 3 component(s).
Adding 327 connectivity constraints based on node-separators ...
SOLVING ...
##Solution is disconnected!##
With 87 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 3 component(s).
Adding 196 connectivity constraints based on node-separators ...
SOLVING ...
##Solution is disconnected!##
With 87 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 2 component(s).
Adding 100 connectivity constraints based on node-separators ...
SOLVING ...
##Solution is connected!##
With 87 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 1 component(s).
Adding 1 novelty constraint(s) ...
SOLVING ...
Adding 2 novelty constraint(s) ...
SOLVING ...
Adding 3 novelty constraint(s) ...
SOLVING ...
##Solution is disconnected!##
With 87 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 2 component(s).
Adding 100 connectivity constraints based on node-separators ...
Adding 3 novelty constraint(s) ...
SOLVING ...
##Solution is disconnected!##
With 87 nodes, 52 potential terminal(s) and 52 fixed terminal(s) across 2 component(s).
Adding 100 connectivity constraints based on node-separators ...
Adding 3 novelty constraint(s) ...
SOLVING ...

#how many disconnected solution were found before finding a connected solution for each degenerated solution
MStT$getNconnectivityConstraintsCalls()
[1] 4 0 0 2

[adamsardar]

Manually rebased on top of master. Closed.