CODEWITHSUNDEEP
pythonnumpynetworkx
Woden
Woden

Reputation: 1386

How to find the largest connected area of a graph or matrix in Python?

I have struggled with this for a few days, and in the Python there is no way to do "int [][]" for a matrix in JAVA. My first thought is to use DFS method to exhaust the path. In the program, I set a path for the recursion. However, there is no way to always have a path, it means I have to iterate all the other nodes in the graph provided. I am new to programming, the code might be WET.

My idea is:

  1. If the current vertex equals to 1, use DFS to exhaust the path and count it if there's a path.
  2. If the current vertex equals to 0, find the next node and repeat the first step.

Here is my code(incomplete)

def dfs_explore(graph, current_vertex, visited_x= None, visited_y = None):
if visited_x is None:
    visited_x = []
if visited_x is None:
    visited_y = []

stack_x = []
stack_y = []

rows = len(graph)
cols = len(graph[0]) if rows else 0

if not (visited_x and visted_y):
    for x in range(cols):
        for y in range(rows):
            if graph[x][y] != 0:
                stack_x.append(x) # the column neighbours
                stack_y.append(y)
                visited.append(x)
                visited.append(y)
                path = dfs_explore(graph, graph[x][y], visited_x, visited_y)
                if path:
                    return path
                else not path:
                    stack_x.pop()
                    stack_y.pop()

Upvotes: 2

Views: 514

Answers (1)

Joe
Joe

Reputation: 7131

If you just want to convert the Java code from the example one possibility is to use Numpy:

import numpy as np

dim_x = 5
dim_y = 4

#initialize with zeros
visited = np.zeros((dim_y, dim_x))

visited[3][3] = 1

print(visited)

Another option is to use a simple nested list ("2d list"):

dim_x = 5
dim_y = 4

#initialize with zeros
visited = [[0 for _x in range(dim_x)] for _y in range(dim_y)]

visited[3][3] = 1

print(visited)

You could take a look at NetworkX. There are functions to seem to do what you need, e.g. connected_component_subgraphs (Example 1, Example 2)

You might need a function to calculate the convex hull of the nodes, there are several available, but I am not sure if there is one in NetworkX.

Upvotes: 1

Related Questions