Purpose of the project

Graph and subgraph isomorphism problems frequently arise in practical computational tasks. These may involve identifying isomorphic graph pairs or determining a complete set of possible mappings from one graph to another. For more information, see Wikipedia.

To solve such tasks in Python, a popular NetworkX library implements GraphMatcher class:

import networkx as nx
from networkx.algorithms import isomorphism

# Create some simple graph
G = nx.cycle_graph(4)

# The GraphMatcher object implements graph isomorphism algorithm
GM = isomorphism.GraphMatcher(G, G)

# Iterate over all possible G automorphisms (isomorphisms onto itself)
for isom in GM.isomorphisms_iter():
    # Print each mapping as {'old node': 'new node'} dict
    print(repr(isom))

# Result is 4*2=8 square symmetries:
# {0: 0, 1: 1, 2: 2, 3: 3}
# {0: 0, 3: 1, 2: 2, 1: 3}
# {1: 0, 0: 1, 3: 2, 2: 3}
# {1: 0, 2: 1, 3: 2, 0: 3}
# {2: 0, 1: 1, 0: 2, 3: 3}
# {2: 0, 3: 1, 0: 2, 1: 3}
# {3: 0, 0: 1, 1: 2, 2: 3}
# {3: 0, 2: 1, 1: 2, 0: 3}

Unfortunately, current graph isomorphism algorithms suffer from scalability issues with larger graphs. Moreover, NetworkX is implemented entirely in Python giving it a slowdown of at least x10.

To solve this problem, there exists a VF3 algorithm for graph and subgraph isomorphism calculation, which extremely efficient in time and memory. Unlike NetworkX, VF3lib (the implementation of VF3) is made completely in C++, which is itself a huge boost. However, the original VF3lib is inconvenient to work with from larger projects, since it requires file-based input and returns results through the command line.

The VF3Py library makes transition from NetworkX’s GraphMatcher to a more efficient VF3 as easy a possible. All graphs are still constructed in NetworkX, but the calls to GraphMatcher are seamlessly replaced with calls to VF3Py:

import networkx as nx
import vf3py

# Create some simple graph
G = nx.cycle_graph(4)

# The GraphMatcher object implements graph isomorphism algorithm
automorphisms = vf3py.get_automorphisms(G)

# Iterate over all possible G automorphisms (isomorphisms onto itself)
for isom in automorphisms:
    print(repr(isom))

# This results in the same 8 square symmetries ('old label' -> 'new label'):
# {0: 0, 1: 1, 2: 2, 3: 3}
# {0: 0, 1: 3, 2: 2, 3: 1}
# {0: 1, 1: 0, 2: 3, 3: 2}
# {0: 1, 1: 2, 2: 3, 3: 0}
# {0: 2, 1: 1, 2: 0, 3: 3}
# {0: 2, 1: 3, 2: 0, 3: 1}
# {0: 3, 1: 0, 2: 1, 3: 2}
# {0: 3, 1: 2, 2: 1, 3: 0}