Persistent vertex identities for Steiner tree, vertex removal

Specific Domains Graphs
, , ,
1

I have a use case for a large graph, from which I iteratively remove vertices, and at each step compute some Steiner trees from its current state. Specifically, my use case requires to know to which vertices in the original father-graph the vertices in the Steiner tree corresponds to. However, I find that the implementation available in Graphs.jl is unsuitable, since vertex indices are not preserved upon vertex deletion*, and that steiner_tree returns a new graph object that does not carry any information about the tree’s embedding in the graph from which it was computed. Are there some parameters I am missing, or other Steiner tree implementations in the ecosystem, that can give me this information?

* I can at least get around this by removing vertices in reverse order from last to first. This is not totally ideal, as I would like the order of vertex removal to be a parameter I can play around with.

1 Like
2

I don’t think there’s a great solution to your problem at the moment. You can get around the first issue at the cost of vertex reordering, but the fact that steiner_tree doesn’t map to the identities in the original graph makes it useless to you apparently. A better implementation would probably return such a mapping, like for induced_subgraph.

Much ink has been spilled on the topic of vertex identities, and while the ecosystem looks very peaceful at the moment, I hope to get some funding next year and start working on a revamp with a student or two.

1 Like
3

Thank you for the honest answer. One option I see for now is to interface with NetworkX. If you are familiar with it, do you have a sense of how terrible of an overhead I can expect by ferrying such deletions and Steiner tree queries across the language barrier?

Alternatively, I’m willing to look at how difficult it would be to adapt steiner_tree to return a mapping like you suggest.

Out of curiosity, what kind of funding supports development like that? Institutional? Funding agency?

4

Follow-up: If I am reading this correctly, all up to the return statement of steiner_tree, all the information about the required mapping is available? i.e. mst_mst_mc is a vector of edges still specified by the vertex indices in the original graph. I think an adaptation into returning a mapping should be a relatively low-hanging fruit, no?

Actually I don’t remember when was the last time I checked this out and the indices of the Steiner tree were not aligned to (a lower subrange of) the original graph indices; I just returned to thinking about this project after a while. Trying this out on grid graphs at least seems to not suffer from this problem?

julia> steiner_tree(grid((10,10)), [44, 77]) |> edges |> collect
6-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int64}}:
 Edge 44 => 45
 Edge 45 => 46
 Edge 46 => 56
 Edge 56 => 57
 Edge 57 => 67
 Edge 67 => 77
5

I’m not sure. I know the overhead of networkX is terrible in general, but I don’t know about conversion specifically. That’s more of a PythonCall.jl question I guess.

That would be great. There are presumably other similar functions which return a subgraph, and for which a mapping from old vertex indices to new vertex indices would be handy.

At the moment none, which is precisely why all is quiet on the graphs front. Yesterday I wrapped up an application for a big grant from the French government on transportation and logistics, in which I included a 2-year postdoc on “Scaling up graph machine learning and software in Julia”. That might no start for a while though.

On a less ambitious but more immediate scale, @Krastanov has been working to set up some bounties for specific issues in the ecosystem which were deemed more important. The first of these bounties was for graph matching algorithms, but maybe there is room for more.

1 Like
6

Thanks for the pointers! Thoughts about my secondary post yesterday? Might I have been mistaken about the impersistent identities? I don’t see that this is strictly guaranteed by the implementation, but I’m struggling to find a counter-example where this breaks down.

7

Oops I had forgotten about it. Indeed, after glancing at the implementation, it seems to remove only vertices and not edges, which doesn’t trigger a renumbering? Definitely something one may want to indicate in the docstring though.

8

That’s great! I don’t even mind pushing a PR with a docstring update.
Last question: For each Steiner tree I find, I would like to fix certain vertices as the roots, and them perform several pre/in/post-order tree traversals. I thought to use the implementations available in AbtractTrees.jl, but it is not clear to me how to feed the Steiner trees into it. Would I need to implement my own implementation of AbstractTree’s interface, that is backed by Graphs.jl behind the scenes?