Core dumped during 3D implementation of 'max area of islands' algorithm

Question

I am trying to use an algorithm for the problem "Max area of island" in a 3D problem, so it would be more like max volume of island. I was using total volumes of 200x200x200 voxels as input, but I am having trouble because it does not work when there are very big 'islands' in the volume I input ('core dumped' in the Ubunut terminal). Here is the code with the modifications I did to apply it to my 3D problem:

class Solution3D:

    def dfs3D(self, grid, r, c, l):
        grid[r][c][l] = 0
        num = 1
        lst = [(r-1, c, l), (r+1, c, l), (r, c-1, l), (r, c+1, l), (r, c, l-1), (r, c, l+1)]
        for row, col, leh in lst:
            if row >= 0 and col >= 0 and leh >= 0\
            and row < len(grid) and col < len(grid[0]) and leh < len(grid[0][0])\
            and grid[row][col][leh] == 1:
                num += self.dfs3D(grid, row, col, leh)
        return num


    def maxAreaOfIsland3D(self, grid):
        area_islands = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                for l in range(len(grid[0][0])):
                    if grid[r][c][l] == 1:
                        area_islands = max(area_islands, self.dfs3D(grid, r, c, l))
        return area_islands

Is this implementation too inefficient? How could I make it less memory hungry so that I can use it with big islands?

Thank you very much!

user_4601890 · Answer

Got something. Takes around one minute and 6GB of RAM

First I find edges using sklearn.image.grid_to_graph, this is quite fast
Next I build networkx graph - this is bottleneck for both computation time and RAM usage
Finally, I find all connected subgraphs in this graph and retu

import numpy as np
import networkx as nx
import sklearn.feature_extraction.image

grid_size = 4   # manual check -> for seed 0: 38 nodes, largest subgraph has 37 connected nodes, correct
grid_size = 200


random_grid = np.random.RandomState(seed=0).randint(0, 2, size=(grid_size, grid_size, grid_size))
G = nx.Graph()
print('finding edges...')
graph = sklearn.feature_extraction.image.grid_to_graph(grid_size, grid_size, grid_size, mask=random_grid)
print('buidling graph...')
G.add_edges_from(np.vstack([graph.col, graph.row]).T)
print('finding subgraphs...')
subgraphs = nx.connected_components(G)
sorted_subgraphs = sorted(subgraphs, key=len, reverse=True)
G0 = G.subgraph(sorted_subgraphs[0])
print('Largest subgraph size: ', len(G0))

Largest subgraph size:  3909288

Core dumped during 3D implementation of 'max area of islands' algorithm

1 Answers