search

matbesancon / VertexSafeGraphs.jl

Wrapper on top of LightGraphs for preserving vertex numbering
MIT License
14 stars 1 forks source link

Convert VSafeGraph back to AbstractGraph #13

Closed yanyuan-wang closed 1 year ago

yanyuan-wang commented 4 years ago

Hi, as most of the functions for accessing the properties of a graph in LightGraph require that the graph should be a AbstractGraph, so could you please give me some suggestions on how to convert VSafeGraph to AbstractGraph? Thanks!

matbesancon commented 4 years ago

Hi, yes that's why VSafeGraph is a sub-type of AbstractGraph:

struct VSafeGraph{T, G<:LG.AbstractGraph{T}} <: LG.AbstractGraph{T}
yanyuan-wang commented 4 years ago

Hi, I tried with functions like betweenness_centrality using VSafeGraph, but unfortunately it doesn't work. image

matbesancon commented 4 years ago

You are right. The reason seems to be a bug inLightGraphs, constraining vertices to be a vector. In the meantime, you can do something like: betweenness_centrality(g, collect(vertices(g)))

matbesancon commented 4 years ago

will be fixed by https://github.com/JuliaGraphs/LightGraphs.jl/pull/1459 Thanks for reporting this bug

yanyuan-wang commented 4 years ago

Thanks for your reply! But if I remove or add some vertices, even betweenness_centrality(g, collect(vertices(g))) cannot work. image

matbesancon commented 4 years ago

you're right, I see the problem now. VSafeGraph does not have contiguous vertices, which means some algorithms fail. I wrote about it in this blog post: https://matbesancon.github.io/post/2019-05-30-vertex-safe-removal/ and will talk about it Friday at JuliaCon. The right thing to do is to add to the signature of dijkstra_shortest_path that it requires a HasContigousVertices graph, just like some algorithms specify they need a IsDirected

matbesancon commented 4 years ago

the long-term solution will be to add a method on disjkstra_shortest_path for non-contiguous vertices