Speed-up 3D graph creation

[nirmalsnair]

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.

[pmneila]

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.

[nirmalsnair]

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.