You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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
The text was updated successfully, but these errors were encountered:
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.
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 =
then
Actual behavior
steiner_tree(g,[1,3])
with terminal vertices 1 and 3 outputs the graphwhereas
Expected behavior
I would have expected the output to be
without vertex 2 being included.
Code demonstrating bug
which outputs
Version information
Output from
versioninfo()
surrounded by backticks (``)Output from
] status Graphs
surrounded by backticks (``)[86223c79] Graphs v1.11.0
The text was updated successfully, but these errors were encountered: