krashkov / pcsteiner Goto Github PK

I`m having a couple of issues even when only modifying the example in the Vignette. I initially modified it to a classical Steiner tree with all node prizes and edge costs = 1. As in this case there are equivalent solutions, I modified it as follows:

rm(list=ls())
cat("\014") #is the code to send ctrl+L to the console and therefore will clear the screen
plot.new()
library(pcSteiner)

g <- graph('Bull')
par(mar=c(0,0,0,0))
plot(g,edge.label=E(g))

V(g)
V(g)$prizes= c(1,1,1,1,1)
E(g)
E(g)$costs= c(1.1,1,1,1,1)

#run m times
par(mar=c(4,4,1,1))
m= 30
eps_val= 1E-5
costs= c()
for (i in 1:m) {
#set.seed(1)
tree= pcs.tree(graph=g,terminals=c(4,5),lambda=1,root=5,depth=5, eps=eps_val, max_iter=10)
#avoid similar solutions
costs[i]= tree$cost
}
costs[is.infinite(costs)]= 10
plot(1:m,costs,xlab='iteration',ylab='cost',main=paste('eps:',eps_val))

Apparently, running the pcs.tree multiple times leads to different outputs: Either a cost of 4 or no solution. I understand that a heuristic may yield different solutions on repeat runs, but in this case, the tolerance value seems low enough that this should not be the case. Having said that, I dont fully understand what the 'eps' does. In the example in the vignette its '-1', while in the documentation it's 1E-3.
Is it the case that pcs.tree decides to return no solution (cost = Inf; all edges == FALSE) if there are multiple equivalent solutions?
Also, in the above case, why is 4 returned as cost in cases where three edges, each at a cost of 1 are selected?

Thank you.