GraphsExt.jl implements some things that may eventually be added to Graphs.jl. I need to use them and want to expose them before making PRs to Graphs.jl. This package is not registered in the general registry but is in a “private” registry that you can use.
The most important function is remove_vertices!. There is no efficient (better than order |V|) function in Graphs.jl for removing several vertices from the built-in implementations. This makes it impossible to work with large graphs that require frequently removing vertices. remove_vertices! is roughly independent of |V| and so solves this problem.
It returns both forward and backward vertex maps. I found both maps necessary as well as adequate for tracking vertex renumbering in external lists of vertices. See the README in the link above.
The next most interesting item is dag_longest_path which computes a longest path in a directed acyclic graph (DAG)
Hey @jlapeyre, thanks for the contribution!
Would you consider PRs to Graphs.jl soon-ish? I know we have not been very reactive on the repo, but we will do our best, and I have a little more time these days
GraphsExt.jl implements some things that may eventually be added to Graphs.jl. I need to use them and want to expose them before making PRs to Graphs.jl.
I put these in a package rather than making PRs for a few reasons.
I’m not satisfied with with the interfaces. I don’t want to spend a lot of time just now trying to get it right.
Moreover, Graphs.jl is not very active at the moment. A PR would probably be me and one other person trying to figure out the interface with no feedback from use in the wild. The most effective way to use the vertex maps is not at all obvious. I have an application that I didn’t link that works pretty well, but I imagine it’s not the end of the story.
It’s impossible to replace rem_vertices! in Graphs.jl with an efficient function that uses the same API because it returns a structure of size O(|V|). I don’t want to add another API that restricts improvement.
Edited my answer