Numpy Cluster From Connected Graph

What is the best way to cluster connected graph ? ex1 : [[ 1 1 1 1 0 0] [ 1 1 1 1 0 0] [ 1 1 1 1 0 0] [ 1 1 1 1 0 0] [ 0 0 0 0 1 1] [ 0 0 0 0 1 1]] result : ==> [[0,1,2,3]

Solution 1:

In some of the examples, say ex2, you've given a digraph, or a directed graph such that A != A.T. In this case a more reasonable definition can be found by considering strongly connected components. In this case the splitting is [0,1,3],[4,5],[2]. networkx can help you find these:

import numpy as np
import networkx as nx

A = np.array([[0,1,0,1,0,0],
              [1,1,0,1,0,0],
              [0,1,0,1,0,0],
              [1,0,0,0,0,0],
              [0,0,1,0,1,1],
              [0,0,0,0,1,1]])

G = nx.from_numpy_matrix(A, create_using=nx.DiGraph()) 
for subg in nx.strongly_connected_component_subgraphs(G):
    print subg.nodes()