Pythonでnetworkxでサブグラフを認識

Question

私は3x3の正方形の格子を持ち、各ノードはその垂直な隣に接続されています。それは反復格子であるため、一方の外側のノードは他方の側の外側のノードに接続される。例えば、this diagramにおいて、ノード '0,0'は、 '0,2'及び '2,0'（並びに '0,1'及び '1,0'）に接続されている。

NetworkXを使用してhorizontal subgraphs（たとえば '0,0'、 '1,0'、 '2、0'）を識別したいと思います。ラップ=真

Subgraphs found 
0 {'0, 0': 'A', '1, 0': 'B', '2, 0': 'C'} 
1 {'0, 1': 'A', '1, 1': 'B', '2, 1': 'C'} 
2 {'1, 2': 'B', '0, 2': 'A', '2, 2': 'C'} 
3 {'1, 2': 'B', '0, 2': 'C', '2, 2': 'A'} 
4 {'0, 0': 'C', '1, 0': 'B', '2, 0': 'A'} 
5 {'0, 1': 'C', '1, 1': 'B', '2, 1': 'A'} 
Number of subgraphs: 6 

しかし、それはどの部分グラフを見つけることができません。

ラップがFalseに設定されている

import networkx as nx 
import networkx.algorithms.isomorphism as iso 
import matplotlib.pyplot as plt 
import numpy as np 


wrap = True #If True, outer nodes are connected to nodes on opposite end 
size = 3 
pos = {} 

big_graph = nx.Graph()  
#Create nodes 
for i in xrange(size): 
    for j in xrange(size): 
     current_node = '{}, {}'.format(i, j) 
     big_graph.add_node(current_node, i = i, j = j) 
     pos[current_node] = np.array([i, j]) 

#Create edges 
for i in xrange(size): 
    for j in xrange(size): 
     current_node = '{}, {}'.format(i, j) 
     #Add edge to connect node above 
     if i != 0: 
      big_graph.add_edge(current_node, '{}, {}'.format(i-1, j), direction = 'hor') 
     elif wrap: 
      big_graph.add_edge(current_node, '{}, {}'.format(size-1, j), direction = 'hor') 

     #Add edge to connect node below 
     if i != (size-1): 
      big_graph.add_edge(current_node, '{}, {}'.format(i+1, j), direction = 'hor') 
     elif wrap: 
      big_graph.add_edge(current_node, '{}, {}'.format(0, j), direction = 'hor') 

     #Add edge to connect node above 
     if j != 0: 
      big_graph.add_edge(current_node, '{}, {}'.format(i, j-1), direction = 'vert') 
     elif wrap: 
      big_graph.add_edge(current_node, '{}, {}'.format(i, size-1), direction = 'vert') 

     #Add edge to connect node below 
     if j != (size-1): 
      big_graph.add_edge(current_node, '{}, {}'.format(i, j+1), direction = 'vert') 
     elif wrap: 
      big_graph.add_edge(current_node, '{}, {}'.format(i, 0), direction = 'vert') 

#Print Node information 
print 'Nodes:' 
print 'n Node i j' 
for i, node in enumerate(sorted(big_graph.nodes_iter())): 
    print '{:2d} {} {} {}'.format(i, node, nx.get_node_attributes(big_graph, 'i')[node], nx.get_node_attributes(big_graph, 'j')[node]) 
print '-'*10 

#Print Edge information 
print 'Edges:' 
print 'n Nodes     Direction' 
for i, edge in enumerate(sorted(big_graph.edges_iter())): 
    print '{:2d} {}  {}'.format(i, edge, nx.get_edge_attributes(big_graph, 'direction')[edge]) 
print '-'*10 


#Subgraph to recognize 
small_graph = nx.Graph() 
small_graph.add_nodes_from(['A', 'B', 'C']) 
small_graph.add_edge('A', 'B', direction = 'hor') 
small_graph.add_edge('B', 'C', direction = 'hor') 


#Print edge information 
print 'Small graph edges' 
for i, edge in enumerate(sorted(small_graph.edges_iter())): 
    print '{} {} {}'.format(i, edge, nx.get_edge_attributes(small_graph, 'direction')[edge]) 
    #print '{}'.format(edge, nx.get_edge_attributes(small_graph)) 
print '-'*10 

#Find subgraphs 
GM = iso.GraphMatcher(big_graph, small_graph, edge_match=iso.categorical_edge_match('direction', '')) 
subgraph_list = [] 
print 'Subgraphs found' 
for i, subgraph in enumerate(GM.subgraph_isomorphisms_iter()): 
    print '{}\t{}'.format(i, subgraph) 
    subgraph_list.append(subgraph) 
print 'Number of subgraphs: {}'.format(len(subgraph_list)) 


#Draw the graph 
pos=nx.spring_layout(big_graph, pos = pos) 
nx.draw(big_graph, pos = pos, node_size = 700) 
nx.draw_networkx_labels(big_graph, pos = pos) 
plt.show() 

、それは私が期待する答えを与える：ここに私のコードです。

Subgraphs found 
Number of subgraphs: 0 

これはなぜ起こるのですか？

Answer 1

wrap=Trueを使用すると、開始ノードと終了ノードが見つからないため、サブグラフが見つからないことが判明しています。それらは指定されていません。つまり、ラティスをラップすると球のように振る舞い、表面を歩くと物理的な始点や終点はありません。

私の提案は、あなたが言ったようにsizeを変更するか、可能であればwrap=Falseに固執することです。