JuliaGraphs / Graphs.jl

An optimized graphs package for the Julia programming language
http://juliagraphs.org/Graphs.jl/
Other
451 stars 87 forks source link

[BUG] `steiner_tree` fails if only one terminal vertex is passed #362

Closed mtfishman closed 2 months ago

mtfishman commented 3 months ago

Description of bug steiner_tree fails if only one terminal vertex is passed.

How to reproduce

julia> using Graphs

julia> steiner_tree(grid((2, 2)), [2])

Expected behavior I was hoping/expecting it would output a graph with no edges and a number of vertices equal to the specified terminal vertex, i.e.:

julia> steiner_tree(grid((2, 2)), [2])
{2, 0} undirected simple Int64 graph

Actual behavior

julia> steiner_tree(grid((2, 2)), [2])
ERROR: InexactError: check_top_bit(UInt64, -1)
Stacktrace:
  [1] throw_inexacterror(f::Symbol, ::Type{UInt64}, val::Int64)
    @ Core ./boot.jl:634
  [2] check_top_bit
    @ ./boot.jl:648 [inlined]
  [3] toUInt64
    @ ./boot.jl:759 [inlined]
  [4] UInt64
    @ ./boot.jl:789 [inlined]
  [5] convert
    @ ./number.jl:7 [inlined]
  [6] cconvert
    @ ./essentials.jl:543 [inlined]
  [7] sizehint!
    @ ./array.jl:1351 [inlined]
  [8] kruskal_mst(::Type{SimpleTraits.Not{IsDirected{…}}}, g::SimpleGraph{Int64}, distmx::Graphs.DefaultDistance; minimize::Bool)
    @ Graphs ~/.julia/packages/Graphs/czpTe/src/spanningtrees/kruskal.jl:18
  [9] kruskal_mst
    @ ~/.julia/packages/Graphs/czpTe/src/spanningtrees/kruskal.jl:12 [inlined]
 [10] kruskal_mst
    @ ~/.julia/packages/SimpleTraits/l1ZsK/src/SimpleTraits.jl:338 [inlined]
 [11] steiner_tree(::Type{SimpleTraits.Not{…}}, g::SimpleGraph{Int64}, term_vert::Vector{Int64}, distmx::Graphs.DefaultDistance)
    @ Graphs ~/.julia/packages/Graphs/czpTe/src/steinertree/steiner_tree.jl:79
 [12] steiner_tree
    @ ~/.julia/packages/SimpleTraits/l1ZsK/src/SimpleTraits.jl:331 [inlined]
 [13] steiner_tree(g::SimpleGraph{Int64}, term_vert::Vector{Int64})
    @ Graphs ~/.julia/packages/SimpleTraits/l1ZsK/src/SimpleTraits.jl:331
 [14] top-level scope
    @ REPL[13]:1
Some type information was truncated. Use `show(err)` to see complete types.

Code demonstrating bug

julia> steiner_tree(grid((2, 2)), [2])

Version information

Additional context Add any other context about the problem here.

mtfishman commented 2 months ago

Thanks!