touqir14 / maxflow Goto Github PK

First off, excellent job on making this package available. My own tests agree that it is much faster than OR-Tools or graph-tool; also very easy to use.

I have a use case where I need to compute the max flow between all pairs of nodes. It seems like the overhead of re-computing the graph every time I set a different pair (source, target) is significant. It is my understanding that the reason the graph must be loaded every time is because it is altered during the max flow computation.

So I was wondering if it would be possible to create an option where you pre-allocate space for several copies of the graph, then use each of those sequentially. This would allow the user, for example, to call solve specifying multiple targets, and have returned a list of max flow values, one for each target. E.g.:

n = 100
A = (sparse.rand(n,n, density=0.5, format='csr')*100).astype(np.uint32)

solver = maxflow.Solver() # setting how many results will be computed using the same graph
solver.load_graph(A, 'dinic', multiple_runs=n-1) #call load_graph only once, pre-specifying the number of solves

maxflow_values = solver.solve('dinic', 0, range(1,n)) # setting target to multiple values 
#(maxflow_values is a list containing n-1 values, namely, the max_flows between node 0 and all other nodes)

From inspecting your code, it seems this would at least prevent the for-loops within _load_graph_dense/_load_graph_sparse to be recomputed every time. I would love to know what your thoughts are!