# Persistent vertex identities for Steiner tree, vertex removal
**URL:** https://discourse.julialang.org/t/persistent-vertex-identities-for-steiner-tree-vertex-removal/119568
**Category:** Graphs
**Tags:** data\_structures, tree, graphs, discrete-mathematics
**Created:** [September 18, 2024, 6:08pm UTC](https://discourse.julialang.org/t/persistent-vertex-identities-for-steiner-tree-vertex-removal/119568 "2024-09-18T18:08:15Z")
**Posts on this page:** 8
**Page:** 1
### Author:  [@bremez](https://discourse.julialang.org/u/bremez)
#### Post date: [September 18, 2024, 6:08pm UTC](https://discourse.julialang.org/t/persistent-vertex-identities-for-steiner-tree-vertex-removal/119568/1 "2024-09-18T18:08:15Z")
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.
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [September 18, 2024, 6:16pm UTC](https://discourse.julialang.org/t/persistent-vertex-identities-for-steiner-tree-vertex-removal/119568/2 "2024-09-18T18:16:52Z")
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`](https://juliagraphs.org/Graphs.jl/stable/core_functions/operators/#Graphs.induced_subgraph-Union%7BTuple%7BT%7D,%20Tuple%7BU%7D,%20Tuple%7BT,%20AbstractVector%7BU%7D).
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.
---
### Author:  [@bremez](https://discourse.julialang.org/u/bremez)
#### Post date: [September 18, 2024, 6:30pm UTC](https://discourse.julialang.org/t/persistent-vertex-identities-for-steiner-tree-vertex-removal/119568/3 "2024-09-18T18:30:19Z")
Thank you for the honest answer. One option I see for now is to interface with [`NetworkX`](https://networkx.org/). 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?
---
### Author:  [@bremez](https://discourse.julialang.org/u/bremez)
#### Post date: [September 18, 2024, 8:03pm UTC](https://discourse.julialang.org/t/persistent-vertex-identities-for-steiner-tree-vertex-removal/119568/4 "2024-09-18T20:03:29Z")
Follow-up: If I am reading this correctly, all up to the [return statement](https://github.com/JuliaGraphs/Graphs.jl/blob/8b2cb9445e885324880f45bea7047f75ccecaad3/src/steinertree/steiner_tree.jl#L84) 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
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
```
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [September 19, 2024, 4:30am UTC](https://discourse.julialang.org/t/persistent-vertex-identities-for-steiner-tree-vertex-removal/119568/5 "2024-09-19T04:30:13Z")
> [@bremez](#):
>
> Thank you for the honest answer. One option I see for now is to interface with [`NetworkX`](https://networkx.org/). 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?
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.
> [@bremez](#):
>
> Alternatively, I’m willing to look at how difficult it would be to adapt `steiner_tree` to return a mapping like you suggest.
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.
> [@bremez](#):
>
> Out of curiosity, what kind of funding supports development like that? Institutional? Funding agency?
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.
>
>
> Implement the well-known Blossom algorithm for maximum weight (perfect) matching… in generic graphs.
>
> \- wiki link: https://en.wikipedia.org/wiki/Blossom\_algorithm
> \- many simple (not-optimized) implementations of the algorithm from class projects and the like are available if one searches online for "blossom algorithm simple"
>
> Two bounties are available here:
>
> \- a 500$ bounty for implementing a pure-julia Blossom with tests and documentation, making it the default here, and moving \`BlossomV.jl\` from a dependency to a weak dependency (so that it is not necessary during installation)
> \- a 500$ bounty on improving the performance of the new implementation to no-worse than 90% of \`BlossomV.jl\`
>
> \*\*Required skills\*\*: Both skills in graph theory and high-performance julia.
>
> \*\*Reviewer\*\*: @Krastanov or @gdalle or members of the JuliaGraphs community
>
> \*\*Duration\*\*: 1 month per stage (except potential review overhead)
>
> \#### Payout procedure (for this particular bounty program):
>
> The Funding for these bounties comes from the National Science Foundation and from the NSF Center for Quantum Networks. The payouts are managed by the NumFOCUS foundation and processed in bulk once every two months. If you live in a country in which NumFOCUS can make payments, you can participate in this bounty program.
>
> \[Click here for more details about the bug bounty program.\](https://github.com/QuantumSavory/.github/blob/main/BUG\_BOUNTIES.md)
>
> \
> \\Bug bounty logistic details\ (click to expand)\
>
> To claim exclusive time to work on this bounty either post a comment here or message \[skrastanov@umass.edu\](mailto:skrastanov@umass.edu) with:
>
> \- your name
> \- github username
> \- \*\*(optional)\*\* a brief list of previous pertinent projects you have engaged in
>
> Currently the project is claimed by \`no one\` until \`...\`.
>
> If you want to, you can work on this project without making a claim, however claims are encouraged to give you and other contributors peace of mind. Whoever has made a claim takes precedence when solutions are considered.
>
> You can always propose your own funded project, if you would like to contribute something of value that is not yet covered by an official bounty.
> \
---
### Author:  [@bremez](https://discourse.julialang.org/u/bremez)
#### Post date: [September 19, 2024, 3:39pm UTC](https://discourse.julialang.org/t/persistent-vertex-identities-for-steiner-tree-vertex-removal/119568/6 "2024-09-19T15:39:21Z")
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.
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [September 19, 2024, 3:46pm UTC](https://discourse.julialang.org/t/persistent-vertex-identities-for-steiner-tree-vertex-removal/119568/7 "2024-09-19T15:46:21Z")
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.
---
### Author:  [@bremez](https://discourse.julialang.org/u/bremez)
#### Post date: [September 20, 2024, 2:32pm UTC](https://discourse.julialang.org/t/persistent-vertex-identities-for-steiner-tree-vertex-removal/119568/8 "2024-09-20T14:32:39Z")
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?