Non-deterministic results

[krumsiek]

Hi!

Great package first of all. We're using it for k-shortest path finding in very large graphs.

One thing we noticed is that multiple runs with identical inputs can lead to different results. They are very similar, but still not the same. For us, this creates some reproducibility issues for our results.

Here's some code that should reproduce the problem:

# Note: 
# If the code doesn't crash with non-identical results, just re-run it.
# It will happen after a few tries.

# initialize
library(yenpathy)
nodes <- 100
edges <- 500
reps <- 100 # repeats of identical call to find non-deterministic results... will eventually happen

# generate toy graph
graph <- data.frame(
  sample(1:nodes, edges, replace = T),
  sample(1:nodes, edges, replace = T),
  runif(edges)+1
)

r1 <- k_shortest_paths(graph_df = graph, from = 1, to = 6, k = 4, edge_penalty = 2)
# repeat
for (i in 1:reps) {
  # same call as above
  r2 <- k_shortest_paths(graph_df = graph, from = 1, to = 6, k = 4, edge_penalty = 2)
  stopifnot(all.equal(r1,r2))
}

# if this crashed, then r1 and r2 are slightly different
i # which iteration caused the problem
r1
r2

Many thanks, Jan

[krumsiek]

Edit: This originates from the C++ portion of the code, since I also attempted calling yenpathy:::.k_shortest_paths_Cpp directly with the same results.