Last active
March 24, 2016 04:35
-
-
Save tsujeeth/cfc3b4f6e92698911239 to your computer and use it in GitHub Desktop.
Given a 2-D matrix of 0s and 1s, find the largest cluster of 1s.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment