Fast max-flow min-cut library for Python

I don't know if it is faster, you'll need to check that, but have you tried networkx ? Seems like it offers the functionality you're looking for and from my experience it is a very easy to use library for handling graphs.

SciPy, as of 1.4.0, has an implementation as well in scipy.sparse.csgraph.maximum_flow that might be easier to use as part of your build chain (as the package is available through pip/conda).

It works by manipulating sparse matrices (hence scipy.sparse) representing the adjacency matrix of the graph, and as such, the underlying data structure is close to the metal, and with the algorithm itself being implemented in Cython, performance should be on par with e.g. graph-tool.

How the different implementations compare with regards to performance will always depend on the structure of the graph whose maximum flow you're interested in, but as a simple benchmark, I tried running random graphs with different sparsities through NetworkX, graph-tool, and SciPy. All of them play well with NumPy arrays, so to ensure a level playing field, let us create methods so that each of them take as inputs NumPy arrays with shape (density*1000*1000, 3) whose rows are edges, and whose columns are the two vertices incident to a given edge, as well as the capacity of the edge.

import numpy as np
from scipy.sparse import rand


def make_data(density):
    m = (rand(1000, 1000, density=density, format='coo', random_state=42)*100).astype(np.int32)
    return np.vstack([m.row, m.col, m.data]).T

data01 = make_data(0.1)
data03 = make_data(0.3)
data05 = make_data(0.5)

With this, the various frameworks can calculate the value of a maximum flow as follows:

import graph_tool.all as gt
from scipy.sparse import coo_matrix, csr_matrix
from scipy.sparse.csgraph import maximum_flow
import networkx as nx


def networkx_max_flow(data, primitive):
    m = coo_matrix((data[:, 2], (data[:, 0], data[:, 1])))
    G = nx.from_numpy_array(m.toarray(), create_using=nx.DiGraph())
    return nx.maximum_flow_value(G, 0, 999, capacity='weight', flow_func=primitive)


def graph_tool_max_flow(data, primitive):
    g = gt.Graph()
    cap = g.new_edge_property('int')
    eprops = [cap]
    g.add_edge_list(data, eprops=eprops)
    src, tgt = g.vertex(0), g.vertex(999)
    res = primitive(g, src, tgt, cap)
    res.a = cap.a - res.a
    return sum(res[e] for e in tgt.in_edges())


def scipy_max_flow(data):
    m = csr_matrix((data[:, 2], (data[:, 0], data[:, 1])))
    return maximum_flow(m, 0, 999).flow_value

And with this, examples of IPython benchmarks become

%timeit networkx_max_flow(data01, nx.algorithms.flow.shortest_augmenting_path)
%timeit graph_tool_max_flow(data03, gt.push_relabel_max_flow)
%timeit scipy_max_flow(data05)

I then see the following results:

+----------------------------------------------+----------------+----------------+---------------+
|                  Algorithm                   |  Density: 0.1  |  Density: 0.3  |  Density: 0.5 |
+----------------------------------------------+----------------+----------------+---------------+
| nx.algorithms.flow.edmonds_karp              |  1.07s         |  3.2s          |  6.39s        |
| nx.algorithms.flow.preflow_push              |  1.07s         |  3.27s         |  6.18s        |
| nx.algorithms.flow.shortest_augmenting_path  |  1.08s         |  3.25s         |  6.23s        |
| gt.edmonds_karp_max_flow                     |  274ms         |  2.84s         |  10s          |
| gt.push_relabel_max_flow                     |  71ms          |  466ms         |  1.42s        |
| gt.boykov_kolmogorov_max_flow                |  79ms          |  463ms         |  895ms        |
| scipy.sparse.csgraph.maximum_flow            |  64ms          |  234ms         |  580ms        |
+----------------------------------------------+----------------+----------------+---------------+

Again, results will depend on the graph structure, but this at least suggests that SciPy should offer you performance on par with graph-tool.

I have used graph-tool for similar tasks.

Graph-tool is an efficient python module for manipulation and statistical analysis of graphs (a.k.a. networks). They even have superb documentation about max-flow algorithms.

Currently graph-tool supports given algorithms:

• Edmonds-Karp - Calculate maximum flow on the graph with the Edmonds-Karp algorithm.
• Push relabel - Calculate maximum flow on the graph with the push-relabel algorithm.
• Boykov Kolmogorov - Calculate maximum flow on the graph with the Boykov-Kolmogorov algorithm.

Example taken from docs: find maxflow using Boykov-Kolmogorov:

>>> g = gt.load_graph("flow-example.xml.gz") #producing example is in doc
>>> cap = g.edge_properties["cap"]
>>> src, tgt = g.vertex(0), g.vertex(1)
>>> res = gt.boykov_kolmogorov_max_flow(g, src, tgt, cap)
>>> res.a = cap.a - res.a  # the actual flow
>>> max_flow = sum(res[e] for e in tgt.in_edges())
>>> print max_flow
6.92759897841
>>> pos = g.vertex_properties["pos"]
>>> gt.graph_draw(g, pos=pos, pin=True, penwidth=res, output="example-kolmogorov.png")

I executed this example with random directed graph(nodes=4000, vertices = 23964), all process took just 11seconds.

alternative libraries:

• igraph - mainly implemented in C, but has Python and R interface
• Linked topic "Python packages for graph theory"
• or other selected graph tools in Sage wiki.