Move code from GraphFlows and GraphsMatching to GraphsOptim

[etiennedeg]

As discussed on slack, it is annoying to have GraphFlows.jl and GraphsMatching.jl as separate packages. We should see what we can bring back to Graph.jl and maybe create a package with the more complex problems that need JuMP as a dependency.

[gdalle]

Thank you for opening the issue! I agree with this proposition

[gdalle]

By the way, this could be an opportunity for standardizing package names: half of them start with Graphs and the other half with Graph (no s), with no apparent logic to me

[gdalle]

I would like to start splitting the code that requires JuMP or other outside optimizers, what do you think about the name GraphsOptim for this satellite package?

[gdalle]

I have started a first draft at https://github.com/gdalle/GraphsOptim.jl, when it is mature enough I'll transfer it to the JuliaGraphs organization (cc @matbesancon).

I feel like the network interdiction problems of GraphsExtras.jl are sufficiently specific and advanced enough to deserve their individual package, unlike flows and matchings which are (in my opinion) more mainstream. With that in mind, what kind of solver-requiring algorithms would we want to add in GraphsOptim.jl? I was thinking of Wardrop equilibria and congestion problems, but that would require a dependency on Convex.jl in addition to JuMP.jl, so maybe not reasonable?

[matbesancon]

why Convex.jl for Wardrop?

[gdalle]

Following up on this, I am wondering if GraphsOptim.jl actually deserves to exist at all. The new JuMP tutorials are very well done, and I'm not sure providing ready-made LP formulations makes much sense in this case. Thus I propose to move all the combinatorial code for flows, matchings and so on into the main library, and forget the rest. All those in favor, say aye!

[matbesancon]

GraphsMatching will still exist because it depends on the blossom implementation. Even if there are tutorials, having a ready-to-use package can be handy?

[gdalle]

My bad, I didn't know there were other nontrivial dependencies for GraphsMatching and GraphsFlows besides JuMP. In my view, most of the time when you use an LP for a flow you have a slight twist that makes any ready-made implementation of the standard problem inadequate. But there may be more trivial use cases out there than I imagine.

[etiennedeg]

I'm against throwing away these algorithms:

• This might break existing code, this is much harder to reimplement the algorithm using JuMP than just swapping GraphFlows for GraphsOptim.
• This is not trivial at all to implement a network flow problem in JuMP, even though the documentation of JuMP is well done. It requires some basic understanding of linear programming, which many people are not used to. Take someone who never heard of linear programming (but is fluent with Graphs.jl). The example given in JuMP is with a matrix implementation of a graph. To adapt this to a SimpleGraph (using accessors such as neighbors and all...), he will have a hard time, he can't just copy paste the formula's but has to understand how the constraints work.
• There are many problem in Graphs.jl that are easier to implement than a flow problem using JuMP (some of which just requires a simple BFS), but are still implemented in the library.
• These problems are not tied to JuMP, we could expect to provide a solver free implementation in the long term (for example a full julia implementation of the network simplex or the cost scaling algorithm)

[gdalle]

These are fair points. You convinced me that the GraphsOptim.jl project is worth pursuing :)

[IsaacRudich]

Responding to the question of what could be included in a GraphsOptim package: Just my two cents as a researcher (PhD candidate in Math), I currently don't use the Graphs packages even though everything I do is related to graph theory. The main reason for this is that I am trying to get cutting edge performance on various problems, and the algorithms used by the existing packages tend to rely on LPs, (flow and matching for example). LPs are a great and simple way to solve these problems at a small scale, but problem instances don't have to get that big before algorithms optimized for the task at hand really starts to make a huge difference.

So I think it would make a lot of sense for a GraphsOptim package to include stuff like: Edmonds-Karp and/or Dinic's for max flow Network Simplex for min flow Edmond's or Flow-Based method for max matchings Lovasz and Plummer for max stables Some of the basic graph coloring/clique finding methods: DSATUR, Recursive-Large-First Some basic information gathering like finding max/min weight rooted trees (arborescences)

I had sort of planned on wrapping a lot of this stuff together in a package over the next couple years. So if there is interest in adding any of the stuff on this list, I would be happy to take on a significant roll in helping to implement it. This is particularly true of Network Simplex which I am working on right now as I am using it for a graph coloring algorithm I am working on. It also has the added bonus of being useful for a pretty large domain of problems. Network Simplex is mostly just a version of Simplex specifically optimized for graphs.

[gdalle]

Thanks for your input! For me, the purpose of GraphsOptim.jl would be to gather algorithms with heavy dependencies, typically those relying on LPs. As for lightweight algorithms (eg Edmonds Karp & Co), I would rather put them in the main Graphs.jl package since for the most part they only requires the abstract interface we put forward. After all, the main package already includes custom algorithms for several other problems. What saddens me with the current state of GraphsFlows.jl and GraphsMatching.jl is that they contain a mixture of lightweight routines and LP-based formulations, and I see no reason to 1) keep the former away from the main package 2) separate the latter between flows, matchings and possibly other related stuff.

[etiennedeg]

I also think we should bring the standard flow algorithms to Graphs.jl. For the moment, we could keep the ones that use LP solvers on GraphOptim, and bring them to Graphs.jl when we have a pure Julia implementation. I think algorithms which would fit well in GraphOptim would be solvers for NP-hard problems, which would rely on external solvers or/and well tuned backtracking/CP algorithms.

Makes me remember I also started implementing a network simplex a while ago, but let it aside as I was caught on some other things, I should try to come back at it.

[IsaacRudich]

It definitely makes sense to me to make dependency free versions off the algorithms that can live in Graphs.jl, which is also definitely something I'd be interested in helping with.

And I agree that it makes sense to have solvers for NP-Hard problems live in a different package since you'd probably want to have access to LPs for solving sub-problems anyway.

[gdalle]

OK, so that sounds like a roadmap! Should we move GraphsOptim.jl from my profile into the JuliaGraphs organization so that everyone can help make it ready?

[gdalle]

Bumping this because of the issue above: should we move the repo inside the organization so that people can start contributing?