VF2 Algorithm#
An implementation of VF2 algorithm for graph isomorphism testing.
The simplest interface to use this module is to call the
is_isomorphic
function.
Introduction#
The GraphMatcher and DiGraphMatcher are responsible for matching graphs or directed graphs in a predetermined manner. This usually means a check for an isomorphism, though other checks are also possible. For example, a subgraph of one graph can be checked for isomorphism to a second graph.
Matching is done via syntactic feasibility. It is also possible to check for semantic feasibility. Feasibility, then, is defined as the logical AND of the two functions.
To include a semantic check, the (Di)GraphMatcher class should be
subclassed, and the
semantic_feasibility
function should be redefined. By default, the semantic feasibility function always
returns True
. The effect of this is that semantics are not
considered in the matching of G1 and G2.
Examples#
Suppose G1 and G2 are isomorphic graphs. Verification is as follows:
>>> from networkx.algorithms import isomorphism
>>> G1 = nx.path_graph(4)
>>> G2 = nx.path_graph(4)
>>> GM = isomorphism.GraphMatcher(G1, G2)
>>> GM.is_isomorphic()
True
GM.mapping stores the isomorphism mapping from G1 to G2.
>>> GM.mapping
{0: 0, 1: 1, 2: 2, 3: 3}
Suppose G1 and G2 are isomorphic directed graphs. Verification is as follows:
>>> G1 = nx.path_graph(4, create_using=nx.DiGraph())
>>> G2 = nx.path_graph(4, create_using=nx.DiGraph())
>>> DiGM = isomorphism.DiGraphMatcher(G1, G2)
>>> DiGM.is_isomorphic()
True
DiGM.mapping stores the isomorphism mapping from G1 to G2.
>>> DiGM.mapping
{0: 0, 1: 1, 2: 2, 3: 3}
Subgraph Isomorphism#
Graph theory literature can be ambiguous about the meaning of the above statement, and we seek to clarify it now.
In the VF2 literature, a mapping M
is said to be a graphsubgraph
isomorphism iff M
is an isomorphism between G2
and a subgraph of G1
.
Thus, to say that G1
and G2
are graphsubgraph isomorphic is to say
that a subgraph of G1
is isomorphic to G2
.
Other literature uses the phrase ‘subgraph isomorphic’ as in ‘G1
does
not have a subgraph isomorphic to G2
’. Another use is as an in adverb
for isomorphic. Thus, to say that G1
and G2
are subgraph isomorphic
is to say that a subgraph of G1
is isomorphic to G2
.
Finally, the term ‘subgraph’ can have multiple meanings. In this
context, ‘subgraph’ always means a ‘nodeinduced subgraph’. Edgeinduced
subgraph isomorphisms are not directly supported, but one should be
able to perform the check by making use of
line_graph
. For
subgraphs which are not induced, the term ‘monomorphism’ is preferred
over ‘isomorphism’.
Let G = (N, E)
be a graph with a set of nodes N
and set of edges E
.
 If
G' = (N', E')
is a subgraph, then: N'
is a subset ofN
andE'
is a subset ofE
. If
G' = (N', E')
is a nodeinduced subgraph, then: N'
is a subset ofN
andE'
is the subset of edges inE
relating nodes inN'
. If
G' = (N', E')
is an edgeinduced subgraph, then: N'
is the subset of nodes inN
related by edges inE'
andE'
is a subset ofE
. If
G' = (N', E')
is a monomorphism, then: N'
is a subset ofN
andE'
is a subset of the set of edges inE
relating nodes inN'
.
Note that if G'
is a nodeinduced 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.
References#
 [1] Luigi P. Cordella, Pasquale Foggia, Carlo Sansone, Mario Vento,
“A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 13671372, Oct., 2004. http://ieeexplore.ieee.org/iel5/34/29305/01323804.pdf
 [2] L. P. Cordella, P. Foggia, C. Sansone, M. Vento, “An Improved
Algorithm for Matching Large Graphs”, 3rd IAPRTC15 Workshop on Graphbased Representations in Pattern Recognition, Cuen, pp. 149159, 2001. https://www.researchgate.net/publication/200034365_An_Improved_Algorithm_for_Matching_Large_Graphs
See Also#
Notes#
The implementation handles both directed and undirected graphs as well as multigraphs.
In general, the subgraph isomorphism problem is NPcomplete whereas the graph isomorphism problem is most likely not NPcomplete (although no polynomialtime algorithm is known to exist).
Graph Matcher#

Initialize graph matcher. 
Reinitializes the state of the algorithm. 

Returns True if G1 and G2 are isomorphic graphs. 

Returns True if a subgraph of G1 is isomorphic to G2. 

Returns True if a subgraph of G1 is monomorphic to G2. 

Generator over isomorphisms between G1 and G2. 

Generator over isomorphisms between a subgraph of G1 and G2. 

Generator over monomorphisms between a subgraph of G1 and G2. 

Iterator over candidate pairs of nodes in G1 and G2. 

Extends the isomorphism mapping. 


Returns True if mapping G1_node to G2_node is semantically feasible. 

Returns True if adding (G1_node, G2_node) is syntactically feasible. 
DiGraph Matcher#

Initialize graph matcher. 
Reinitializes the state of the algorithm. 

Returns True if G1 and G2 are isomorphic graphs. 

Returns True if a subgraph of G1 is isomorphic to G2. 

Returns True if a subgraph of G1 is monomorphic to G2. 

Generator over isomorphisms between G1 and G2. 

Generator over isomorphisms between a subgraph of G1 and G2. 

Generator over monomorphisms between a subgraph of G1 and G2. 

Iterator over candidate pairs of nodes in G1 and G2. 

Extends the isomorphism mapping. 


Returns True if mapping G1_node to G2_node is semantically feasible. 
Returns True if adding (G1_node, G2_node) is syntactically feasible. 
Match helpers#

Returns a comparison function for a categorical node attribute. 

Returns a comparison function for a categorical edge attribute. 

Returns a comparison function for a categorical edge attribute. 

Returns a comparison function for a numerical node attribute. 

Returns a comparison function for a numerical edge attribute. 

Returns a comparison function for a numerical edge attribute. 

Returns a comparison function for a generic attribute. 

Returns a comparison function for a generic attribute. 

Returns a comparison function for a generic attribute. 