I have a large graph in which I want to find a subgraph isomorphism using the built-in VF2 algorithm in NetworkX. Both the 'haystack' as well as 'needle' graphs are directed. Take the following trivial example:
from networkx.algorithms.isomorphism import DiGraphMatcher
G1 = nx.complete_graph(20, nx.DiGraph)
G2 = nx.DiGraph()
G2.add_edge(1, 2)
list(DiGraphMatcher(G1, G2).subgraph_isomorphisms_iter())
The final line returns an empty list [].
My understanding is that this should return all edges in the graph, and indeed, if I substitute GraphMatcher for DiGraphMatcher, I get a list of all edges.
Is there something wrong with DiGraphMatcher, or perhaps something wrong with my understanding of what DiGraphMatcher should be doing?
Versions:
Example undirected graph code (replaces all DiGraph with Graph, otherwise the same):
from networkx.algorithms.isomorphism import GraphMatcher
G1 = nx.complete_graph(20, nx.Graph)
G2 = nx.Graph()
G2.add_edge(1, 2)
list(GraphMatcher(G1, G2).subgraph_isomorphisms_iter())
Answering my own question after many hours of sorrow. I was hoping this was going to be an interesting technical question. Turns out it's just a run-of-the-mill nomenclature question!
NetworkX defines a subgraph isomorphism as the following:
If G'=(N',E') is a node-induced subgraph, then:
- N' is a subset of N
- E' is the subset of edges in E relating nodes in N'
(Taken from networkx inline code comments.)
It defines a monomorphism as the following:
If G'=(N',E') is a monomorphism, then:
- N' is a subset of N
- E' is a subset of the set of edges in E relating nodes in N'
And further, notes:
Note that if G' is a node-induced subgraph of G, then it is always a subgraph monomorphism of G, but the opposite is not always true, as a monomorphism can have fewer edges.
In other words, because there are other edges involved in this graph than are described by the G2 graph, the DiGraphMatcher considers the set of edges E' to be not equal to the subset of edges in E relating nodes in N'.
Instead, the edges in E' are a subset of the set of edges in E relating nodes in N', and so networkx calls this a monomorphism instead.
To better illustrate this point, consider the following:
from networkx.algorithms.isomorphism import DiGraphMatcher
G1 = nx.DiGraph()
G1.add_edge(1, 2)
G1.add_edge(2, 1)
G2 = nx.DiGraph()
G2.add_edge(1, 2)
print(list(DiGraphMatcher(G1, G2).subgraph_isomorphisms_iter()))
print(list(DiGraphMatcher(G1, G2).subgraph_monomorphisms_iter()))
This will print the following:
[{1: 1, 2: 2}, {2: 1, 1: 2}] # subgraph MONOmorphism
[] # subgraph ISOmorphism