Given a 2-D matrix of 0s and 1s, find the largest cluster of 1s.

Cluster.py

#!/usr/bin/python

import random
import dfs

def add_edge(adj, u, v):
    if u in adj:
        current = adj[u]
        adj[u] = current + [v]
    else:
        adj[u] = [v]

def adjacency_list(matrix, m, n):
    '''
    Given a graph represented as a matrix of {0, 1}, 
    construct an adjacency list
    '''

    def name(i, j):
        return str(i) + ',' + str(j)
    
    ones = set()
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 1:
                ones.add((i, j))

    adj = {}
    islands = []
    for (x, y) in ones:
        key = name(x, y)

        adjacent_cells = [ \
          (x-1, y-1),      \
          (x-1, y),        \
          (x-1, y+1),      \
          (x, y-1),        \
          (x, y+1),        \
          (x+1, y-1),      \
          (x+1, y),        \
          (x+1, y+1) ]

        is_island = True
        for (a, b) in adjacent_cells:
            if (a, b) in ones:
                is_island = True
                add_edge(adj, key, name(a, b))

        if is_island is True:
            islands.append([key])

    return (adj, islands)
        
def element_value(threshold):
    num = random.random()
    if num < threshold:
        return 1
    else:
        return 0

def main():
    # Initialize a m x n matrix
    m = 10
    n = 10
    matrix = [[element_value(0.2) for x in range(n)] for x in range(m)] 

    print 'Input matrix'
    for row in matrix:
        print row

    (adj, islands) = adjacency_list(matrix, m, n)
    clusters = dfs.dfs(adj)
    print 'Clusters ...'
    clusters = clusters + islands
    print clusters

    largest_cluster = None
    largest_cluster_sz = 0
    for cluster in clusters:
        cluster_sz = len(cluster)
        if cluster_sz > largest_cluster_sz:
            largest_cluster = cluster
            largest_cluster_sz = cluster_sz
    print 'Largest cluster ...'
    print largest_cluster


if __name__ == "__main__": 
    main()

DFS.py

#!/usr/bin/python

'''
Given a graph represented as an adjacency list, traverse the graph using DFS.
'''

# Possible states for a node during traversal.
NOT_DISCOVERED = 0
VISITED = 1

def dfs(graph):
    state = {}
    for vertex in graph:
        state[vertex] = NOT_DISCOVERED

    forests = []

    for vertex in graph:
        if state[vertex] is not VISITED: 
            forest = [vertex] + visit(vertex, graph, state)
            forests.append(forest)

    return forests

def visit(vertex, graph, state): 
    state[vertex] = VISITED
    visited = []
    adjacent = graph[vertex]
    for node in adjacent:
        if state[node] is not VISITED:
            visited.append(node)
            state[node] = VISITED
            visited = visited + visit(node, graph, state)
    return visited

def main():
    vertices = ['a', 'b', 'c', 'd', 'e']
    
    graph = {}
    graph['a']  = ['b', 'c']
    graph['b'] = ['a']
    graph['c'] = ['a']
    graph['d'] = ['e']
    graph['e'] = ['d']
    
    print dfs(graph)

if __name__ == "__main__": 
    main()