search

sbromberger / LightGraphs.jl

An optimized graphs package for the Julia programming language
Other
673 stars 185 forks source link

Multigraphs Support? #1482

Closed jarbus closed 3 years ago

jarbus commented 4 years ago

I'm working with Finite-State Automata, namely trying to implement CSSR in Julia, and was wondering if there is any straightforward multigraph functionality inside the JuliaGraphs ecosystem.

etiennedeg commented 4 years ago

After a quick search, I found : Multigraphs.jl I never tested it though.

But I think that for the moment, there is nothing in the julia graph ecosystem.

jarbus commented 4 years ago

I found that as well, and am currently playing around with it. However, it does not appear to be as compatible with the JuliaGraphs codebase as one might hope. Are there any plans to extend support to multigraphs?

Namely, features like strongly_connected_components() are not implemented in the Multigraphs library

jpfairbanks commented 4 years ago

I'm currently working on a substantially different approach that includes multigraphs as a special case over on Catlab.jl. A Catlab.Graphs.Graph is a directed multigraph. Catlab supports arbitrary vertex and edge metadata like in Metagraphs.jl but using a very different mathematical approach. Getting the datastructures for multigraphs working is one thing, but most of the algorithms implemented in LG are not"multigraph-safe" meaning that the code isn't designed to have multiple parallel edges and you would find corner cases in most of the algorithms that aren't handled by the LG implementations. Catlab doesn't magically fix that problem, so you would still have to address those problems in the algorithms.

etiennedeg commented 4 years ago

There are methods in JuliaGraphs for strong connectivity. The only requirements are AbstractGraph and IsDirected, which are both verified by DiMultigraph, so I think the methods can be called (Haven't tested it though). It might be preferable to before check the algorithm is valid for multigraphs, which was not necessarily in the mind of the coder (but can probably be). It could be useful to add a IsSimpleGraph Trait to point out algorithms not designed for multigraphs.

sbromberger commented 3 years ago

I'm going to close this out as it doesn't represent an issue that can be fixed with a patch (trying to do some end-of-year tidying), but please feel free to continue the discussion.