NetworkXExecutor occasionally does not identify any isomorphisms

[j6k4m8]

import networkx as nx
from dotmotif import dotmotif, NetworkXExecutor

E = NetworkXExecutor(graph=nx.complete_graph(20, nx.Graph))
motif = dotmotif().from_motif("A -> B")
E.count(motif)

The above returns 0.

[j6k4m8]

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 _mono_​morphism 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