[BUG] Possible bug in steiner_tree

[emstoudenmire]

Currently, the steiner_tree function reproduces the same behavior that it has for SimpleGraph where in that case, all vertices in the range 1:nv(steiner_tree(g,...)) remain. However, it may be that NamedGraphs should not have this behavior, and that only vertices which are reachable by traversing the Steiner tree should be included in the returned graph.

Here is a small code demonstrating the current behavior and output:

using Graphs: add_edge!, edges, nv, steiner_tree, vertices
using NamedGraphs

g = NamedGraph(["a","b","c"])
add_edge!(g,"a","c")
add_edge!(g,"a","b")

st = steiner_tree(g,["a","c"])
@show st

Output:

st = NamedGraph{String} with 3 vertices:
3-element NamedGraphs.OrderedDictionaries.OrderedIndices{String}
 "a"
 "b"
 "c"

and 1 edge(s):
"a" => "c"

and one can confirm that in this case nv(st) == 3.

[mtfishman]

Seems reasonable to drop the extraneous vertices, it would be simple enough to just remove them if they have degree of zero.

[emstoudenmire]

Glad you agree. I was trying to write a patch, but you might know a more efficient way to do it since you know the internals better. Only thing I could get to work so far was just selectively calling rem_vertex! on the output before returning it.