在 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”）。这是我的代码：

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

当 wrap 设置为 False 时，它会给出我期望的答案：

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

但是，当 wrap = True 时，它找不到任何子图。

Subgraphs found
Number of subgraphs: 0

有谁知道为什么会这样？

Answer 1

我的解释是，当您使用 wrap=True 时它找不到子图，因为缺少开始和结束节点 - 它们未指定。也就是说，当你包裹格子时，它的行为有点像一个球体，当你在它的表面上行走时，没有物理起点或终点。

我的建议是像您所说的那样更改 size，或者尽可能坚持使用 wrap=False。

在 Python 中使用 networkx 识别子图

Recognizing subgraphs with networkx in Python

networkx

python-2.7