Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

GraphsBase.jl vs Graphs.jl #7

Open
filchristou opened this issue Jun 29, 2023 · 7 comments
Open

GraphsBase.jl vs Graphs.jl #7

filchristou opened this issue Jun 29, 2023 · 7 comments
Labels
question Further information is requested

Comments

@filchristou
Copy link

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
Copy link
Member

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
Copy link
Member

gdalle commented Jun 29, 2023

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.

@gdalle gdalle added the question Further information is requested label Jun 29, 2023
@filchristou
Copy link
Author

[..] 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
Copy link
Member

gdalle commented Jun 29, 2023

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
Copy link
Author

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
Copy link
Member

gdalle commented Jun 29, 2023

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 JuliaGraphs/Graphs.jl#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 (JuliaGraphs/Graphs.jl#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
Copy link
Member

gdalle commented Sep 28, 2023

See also #4

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
question Further information is requested
Projects
None yet
Development

No branches or pull requests

3 participants