[BUG] watts_strogatz stalling ..l.

[erlebach]

Description of bug TheLightGraphs method watts_strogatz(nb_nodes, nb_edges, p) stalls with a poor choice of arguments. While the code contains an assertion that nb_nodes must be greater than nb_edges, this is not sufficient. If nb_nodes == nb_edges + 1, the routines does not return. How to reproduce Execute the code

funciton test()
     watts_strogatz(25, 24, .2)
end

The code does not exit. However, when the third parameter is 0, the method finishes executing.

Expected behavior Based on the error message, I expect the method to return for all values of parameters when nb_edges > nb_nodes, for al values of the third parameter.

Actual behavior When the second argument is only slightly higher than the first, and the third parameter is not sufficiently small, the routine does not return in a reasonable time (say 1 second, when the first two arguments are less than 30). Or an error message should be emitted.

Code demonstrating bug

funciton test()
     watts_strogatz(25, 24, .2)
end

Version information

Julia Version 1.4.0-rc1.0
Commit b0c33b0cf5 (2020-01-23 17:23 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin19.0.0)
  CPU: Intel(R) Core(TM) i7-6920HQ CPU @ 2.90GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-8.0.1 (ORCJIT, skylake)
Environment:
  JULIA_NUM_THREADS = 4

• output from ] status LightGraphs surrounded by backticks (``)

  Status `~/.julia/environments/v1.4/Project.toml`
  [093fc24a] LightGraphs v1.3.3

Additional context Add any other context about the problem here.

[sbromberger]

This is known behavior and it impacts most random graph generators that add edges iteratively. The reason it's happening is because as the number of edges already selected approaches V(V-1), the probability that the algorithm chooses a random edge that does not exist approaches 1 / (V(V-1)).

This is, incidentally, a good example of why it is not a good idea to benchmark stochastic processes.