Fast Python min-cut library with BSD license

Question

Is there a fast cython/python library for doing maximum flow / minimum cut computations (preferably with Boykov-Kolmogorov) that has a BSD license?

A light-weight C library would also be useful.

Related: https://stackoverflow.com/q/4008997/5085211 – fuglede Nov 11 '19 at 14:24 — fuglede, Nov 11 '19 at 14:24
Did you find a `C` implementation? – Royi Sep 27 '20 at 17:21 — Royi, Sep 27 '20 at 17:21

score 2 · Answer 1 · answered May 30 '12 at 10:23

2

There is Graph-Tool which is GPL licensed or Python-Graph which is MIT licensed, depending on what you can live with.

answered May 30 '12 at 10:23

Christian Witts

11,375
1
33
46

Thanks for your answer. Do you have any experience with Python-Graph wrt speed? – Andreas Mueller May 30 '12 at 11:17
I can't comment on the speed of Python-Graph, but I do find Graph-Tool to be fast enough for me. If you have speed issues with Python-Graph you can always look at compilers like Psyco or PyPy to execute the code faster. – Christian Witts May 30 '12 at 11:49

score 1 · Answer 2 · answered May 30 '12 at 10:00

1

How about NetworkX? Check out their flow-related algorithms.

The license is BSD

answered May 30 '12 at 10:00

Eli Bendersky

263,248
89
350
412

Thanks. NetworkX is pure Python though, and therefore painfully slow. – Andreas Mueller May 30 '12 at 10:19
1

@AndreasMueller You can run it through Psyco then to see if it's any faster. – Christian Witts May 30 '12 at 10:21
@ChristianWitts: is Psyco still alive? – Fred Foo May 31 '12 at 09:55
@larsmans It's been declared discontinued since March 2012, so it's only freshly dead. PyPy would probably be the best current choice, but it doesn't support everything yet. – Christian Witts May 31 '12 at 09:57
1

@ChristianWitts: OTOH, if NetworkX is indeed pure Python, there's little reason why it shouldn't run on PyPy, and since its data is relatively regular, I would expect nice speedups – Eli Bendersky May 31 '12 at 12:03
Eli I also thought about that but I want to use it in combination with code that uses Numpy.... could try but might be non-trivial – Andreas Mueller May 31 '12 at 16:48

score 1 · Accepted Answer · answered Nov 12 '19 at 09:15

1

As detailed in this answer which also includes a simple benchmark, SciPy -- which is licensed under BSD-3 -- includes an implementation as of 1.4.0 as scipy.sparse.csgraph.maximum_flow.

answered Nov 12 '19 at 09:15

fuglede

17,388
2
54
99

Fast Python min-cut library with BSD license

3 Answers3