touqir14 / maxflow Goto Github PK
View Code? Open in Web Editor NEWA high performance Python library for computing the maximum flow in Graphs!
License: MIT License
A high performance Python library for computing the maximum flow in Graphs!
License: MIT License
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!
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.