Speed-up 3D graph creation
nirmalsnair opened this issue · 2 comments
My data is a 3D grid of size 500x500x100.
In examples/layout_example3D.py
, creating a 3D graph using create_graph(width=500, height=500, depth=100)
takes about 18 minutes. Is there any way to reduce this runtime?
PS: Running maxflow()
on this graph takes only 1 second.
Hi @nsn88,
I cannot reproduce the times you are getting. I run the code (removing the call to plot_graph_3d
):
import numpy as np
import maxflow
def create_graph(width=6, height=5, depth=2):
g = maxflow.Graph[float]()
nodeids = g.add_grid_nodes((depth, height, width))
structure = np.array(
# ...as in layout_example3D.py...
)
g.add_grid_edges(nodeids, structure=structure)
# Source node connected to leftmost non-terminal nodes.
g.add_grid_tedges(nodeids[:, :, 0], np.inf, 0)
# Sink node connected to rightmost non-terminal nodes.
g.add_grid_tedges(nodeids[:, :, -1], 0, np.inf)
return nodeids, g
if __name__ == '__main__':
nodeids, g = create_graph(500, 500, 100)
g.maxflow()
I profiled the run:
% python -m cProfile -s cumulative layout_example3D.py > profile.txt
% head -10 profile.txt
559069 function calls (548302 primitive calls) in 1321.025 seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
914/1 0.004 0.000 1321.026 1321.026 {built-in method builtins.exec}
1 0.000 0.000 1321.025 1321.025 layout_example3D.py:4(<module>)
1 1290.334 1290.334 1290.334 1290.334 {method 'maxflow' of 'maxflow._maxflow.GraphFloat' objects}
1 0.000 0.000 30.222 30.222 layout_example3D.py:12(create_graph)
1 29.741 29.741 29.741 29.741 {method 'add_grid_edges' of 'maxflow._maxflow.GraphFloat' objects}
The call to create_graph
took 30 seconds (29.74 of them for add_grid_edges
), while the call to maxflow
took around 20 minutes. I cannot understand how maxflow
is taking just one second for you. Are you by any chance timing maxflow
by running it a second time? A second call to maxflow
is always much faster as it reuses the information from the first run.
Sorry about the runtimes, I wasn't timing it properly.
The call to create_graph took 30 seconds (29.74 of them for add_grid_edges), while the call to maxflow took around 20 minutes.
Running your code gives me similar timings (~30 seconds for create_graph
and 1043 seconds for maxflow
).
I cannot understand how maxflow is taking just one second for you. Are you by any chance timing maxflow by running it a second time?
You guessed it right, I was timing maxflow
by running it a second time. My bad.