Recognizing subgraphs with networkx in Python

Question

I have a 3x3 square lattice where each node is connected to its perpendicular neighbors. Since it is a repeating lattice, outer nodes on one side are connected to outer nodes on the other side. For example, in this diagram, the node '0, 0' is connected to '0, 2' and '2, 0' (as well as '0, 1' and '1, 0').

I would like to identify horizontal subgraphs (e.g. '0, 0', '1, 0', '2, 0') using NetworkX. Here is my code:

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

When wrap is set to False, it gives the answer I would expect:

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

However, it can't find any subgraphs when wrap = True.

Subgraphs found
Number of subgraphs: 0

Does anyone know why this happens?

Answer 1

My interpretation is that it can't find subgraphs when you use wrap=True because the start and end node are missing - they are unspecified. Which is to say, when you wrap the lattice, it kind of behaves like a sphere, and as you walk on its surface, there's no physical start or endpoint.

My suggestion is to change size, as you said you did, or stick with wrap=False if possible.