[BUG] Extra vertices in Steiner tree

[emstoudenmire]

Description of bug Calling the steiner_tree function on a graph sometimes outputs a tree with extra, isolated vertices.

How to reproduce One example is if the graph is g =

1 -- 3
  \
   2

then

Actual behavior

steiner_tree(g,[1,3]) with terminal vertices 1 and 3 outputs the graph

1 ->- 3

     2

whereas

Expected behavior I would have expected the output to be

1 ->- 3 

without vertex 2 being included.

Code demonstrating bug

using Graphs

g = SimpleGraph(3)
add_edge!(g,1,2)
add_edge!(g,1,3)

st = steiner_tree(g,[1,3])

@show nv(st)

println("Steiner tree vertices:")
for v in vertices(st)
  @show v
end
println("Steiner tree edges:")
for e in edges(st)
  @show e
end

which outputs

nv(st) = 3
Steiner tree vertices:
v = 1
v = 2
v = 3
Steiner tree edges:
e = Edge 1 => 3

Version information Output from versioninfo() surrounded by backticks (``)

Julia Version 1.10.3
Commit 0b4590a5507 (2024-04-30 10:59 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: macOS (arm64-apple-darwin22.4.0)
  CPU: 10 × Apple M1 Max
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, apple-m1)
Threads: 1 default, 0 interactive, 1 GC (on 8 virtual cores)

Output from ] status Graphs surrounded by backticks (`) [86223c79] Graphs v1.11.0`

[emstoudenmire]

Nevermind – my colleague just reviewed this report and pointed out that this is probably the expected and/or necessary behavior, since all vertices in the range 1:nv(g) must be stored by the design of SimpleGraph so then vertex 2 must still be present in the above example.