GraphsBase.jl vs Graphs.jl

[filchristou]

What's the idea with this package ? Will it mean that most of the fundamental code in Graphs.jl will be transferred here ? If yes, what remains for Graphs.jl and how is this decided ?

[etiennedeg]

It has been pointed out that Graphs.jl was a big dependency, and some people want just a lightweight dependency with just the interface. GraphBase should hold at least the interface and as of now, some basic graph implementation. Graphs.jl will ship GraphBase.jl and keep almost all the algorithms it has now. The implementations of WeightedGraphs and MetaGraphs could join the GraphsBase.jl package, and their algorithms the Graphs.jl package. With @gdalle , we discussed the possibility of splitting interface, graph implementations, and graph algorithms in 3 separate packages, but for the moment, we go the way of interface and graph implementations in the same package.

[gdalle]

In addition, we are working with @aurorarossi on GraphsOptim.jl, which will gather graph optimization algorithms that require LP solvers. In the medium term I would like to include it as a conditional dependency of Graphs.jl since JuMP is quite heavy.

[filchristou]

[..] GraphsOptim.jl [...] I would like to include it as a conditional dependency of Graphs.jl since JuMP is quite heavy.

Why not keep it as a separate package ? As far as I know, package extensions cannot export their own functions, and are mostly used to overload what already exists. I don't see why a package like GraphsOptim.jl that introduces new functions, e.g. minimum_cost_flow, should be added as a package extension.

[gdalle]

As far as I know, package extensions cannot export their own functions, and are mostly used to overload what already exists.

That is a good point, which I hadn't considerd. However we're also thinking of changing the nomenclature to give algorithms more expressive names, so maybe there could be a shortest_path function in the main package, which the Dijkstra implementation built in, and the LP implementation in the extension?

[filchristou]

this makes more sense.. So then you would have one shortest_path function that will be dispatched into different implementations w.r.t. the arguments ? e.g.

• shortest_path(gr::AbstractGraph, s::source, t::target; method::Dijkstra)
• shortest_path(gr::AbstractGraph, s::source, t::target; method::Yan)
• shortest_path(gr::AbstractGraph, s::source, t::target; method::BellmanFord)
• shortest_path(gr::AbstractGraph, s::source, t::target; method::LP)

We should take care because they might returns different results. This means, if the compiler cannot identify the method, then we have type instabilities. And it's pretty hard to have common results because e.g. Dijkstra returns the shortest path tree, Yan can returns several paths, LP will return a single path.

This is in contrast to the current system that encourages:

• shortest_path_dijkstra()
• shortest_path_yan()
• shortest_path_bellmanford()
• shortest_path_LP()

This might look messier, but probably will incur less developer headaches.

Whatever the approach, I still kind of thing that packages like GraphsOptim.jl are awesome but shouldn't be inside the Graphs.jl codebase. For the same reason that we shouldn't try to fit all graph algorithms in Graphs.jl, but instead encourage users making modular packages that rely/extend on the interfaces. This way it's more likely to get new people involved. I haven't had the chance to look deeped but people talk about how Optimization.jl managed to make a nice umbrella of different implementation of optimization approaches. Maybe we could do (more or less) the same ?

[gdalle]

We should take care because they might returns different results. This means, if the compiler cannot identify the method, then we have type instabilities.

The syntax you suggest relies on dispatch and therefore prevents that, like the one I mentioned in https://github.com/JuliaGraphs/Graphs.jl/issues/264

And it's pretty hard to have common results because e.g. Dijkstra returns the shortest path tree, Yan can returns several paths, LP will return a single path.

I agree, and the question of coherent return types has also been raised elsewhere (https://github.com/JuliaGraphs/Graphs.jl/issues/77). I think the answer to that is to leverage the various capabilities of these algorithms and be more precise with function names:

shortest_path(Astar(), g, s, t)
shortest_path(Dijkstra(), g, s, t)

shortest_paths(Yen(), g, s, t)

shortest_path_tree(Dijkstra(), g, s, t)
shortest_path_tree(BellmanFord(), g, s, t)

I haven't had the chance to look deeped but people talk about how Optimization.jl managed to make a nice umbrella of different implementation of optimization approaches. Maybe we could do (more or less) the same ?

They do that based on package extensions since 1.9 (I guess), but the difference is that any two of their solvers solve very similar kinds of problems. Whereas for us, (MI)LP solvers solve a very different class of problems than combinatorial ones, with limited overlap. So I think you're right, and the fact that we cannot define new function names in extensions should incite us to keep GraphsOptim separate after all

[gdalle]

See also #4