連通圖的Numpy集羣

Question

集羣連通圖的最佳方式是什麼？

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]] 

結果：

==> [[0,1,2,3],[4,5]] 

EX2

[[ 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]] 

結果：

==> [[0,1,3],[2,4,5]] 

EX3

[[ 0 1 0 0 0 0] 
[ 1 1 0 0 0 0] 
[ 0 0 1 1 0 0] 
[ 0 0 0 1 0 0] 
[ 0 0 0 0 1 1] 
[ 0 0 0 0 1 1]] 

結果：

==> [[0,1],[2,3],[4,5]] 

感謝

Answer 1

中的一些例子，說ex2，你給一個有向圖或有向圖，使得A != A.T。在這種情況下，通過考慮strongly connected components可以找到更合理的定義。在這種情況下，拆分是[0,1,3],[4,5],[2]。 networkx可以幫你找到這些：

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()