Count the isolated sub-graphs starting from the adjacency matrix

adjacency_matrix_clusters.py

def generate_graph(z):
    """
    Generates a dictionary {vertex: set(links)} from the matrix
    """
    graph = {}
    for key, value in enumerate(range(0, len(z))):
        z[value] = list(z[value])
        graph[value] = set()
        for k, v in enumerate(z[value]):
            if int(z[value][k]) == 1:
                graph[value].add(k)
    return graph


def count_clusters(graph):
    """
    Counts the number of independent sub-graphs
    """
    clusters = 0
    while graph != {}:
        clusters += 1
        for edge in graph[next(iter(graph))]:
            if edge in graph:
                for vertex in depth_first_search(graph, edge):
                    del graph[vertex]
    return clusters


def depth_first_search(graph, vertex, visited=None):
    """
    Searches a graph by vising recursively all vertices
    """
    if visited is None:
        visited = set()
    visited.add(vertex)
    for nextVertex in graph[vertex] - visited:
        depth_first_search(graph, nextVertex, visited)
    return visited


m = ['11000',
     '11000',
     '00110',
     '00110',
     '00001']
graph = generate_graph(m)
clusters = count_clusters(graph)
print clusters  # 3