<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Jun 27, 2019 at 4:08 AM Søren Fuglede Jørgensen <<a href="mailto:scipy-dev@fuglede.dk">scipy-dev@fuglede.dk</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi SciPy-Dev<br>
<br>
This question is motivated by the recent improvements to scipy.optimize.linear_sum_assignment. [0] Here, we get a much improved algorithm for solving minimum weight perfect matching in bipartite graphs (which is excellent).<br>
<br>
Now, this problem is one in a large family of combinatorial optimization problems on packing and covering, and what I'm wondering is if SciPy should be the home for a general class of efficient algorithms for solving those?<br>
<br>
Most of these can be phrased in terms of graph theory, and indeed networkx already contains implementations of many classical algorithms (and I was surprised to find that it didn't have anything matching linear_sum_assignment directly; it does have an implementation of the Blossom algorithm). So there's some overlap of scope here, but I guess that's not a problem in and by itself, but it had me wondering where the split should be?<br>
<br>
Just to phrase this in terms of (a very incomplete list of) examples (some of which have polynomial solutions, some of which don't), would there be appetite for including into scipy.optimize algorithms for solving e.g.<br>
<br>
1. other covering/packing problems (e.g. min set/vertex/edge cover, maximum matching, ...),<br>
2. maximum flow,<br>
3. shortest path,<br>
4. travelling salesman, <br></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
5. circuit minimization?<br></blockquote><div><br></div><div>Some of these are in scipy.sparse.csgraph already. <br></div><div><br></div><div>We indeed don't want to do everything that NetworkX already does, however if it's a well-known algorithm that would fit in with what we already have and focus on performance (which NetworkX does not do) then I think there's scope for more. For sparse.csgraph I think Jake implemented a set of standard algorithms that can be found in a graph algorithms introductory handbook.<br></div><div><br></div><div>It also depends to some extent on who writes the code - technical code like that is often not the easiest to maintain, so it would make the conversation and review process a lot easier of there is a person (or two people) with a commitment to maintain the code going forward.</div><div><br></div><div>Cheers,<br></div><div>Ralf</div><div><br></div><div><br></div><div><br></div></div></div>