Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

VF2 Algorithm

VF2 Algorithm

An implementation of VF2 algorithm for graph ismorphism testing.

The simplest interface to use this module is to call networkx.is_isomorphic().

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 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 ambiguious 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 graph-subgraph isomorphism iff M is an isomorphism between G2 and a subgraph of G1. Thus, to say that G1 and G2 are graph-subgraph 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 ‘node-induced subgraph’. Edge-induced subgraph isomorphisms are not directly supported, but one should be able to perform the check by making use of nx.line_graph(). For subgraphs which are not induced, the term ‘monomorphism’ is preferred over ‘isomorphism’. Currently, it is not possible to check for monomorphisms.

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 of N E’ is a subset of E

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’

If G’=(N’,E’) is an edge-induced subgraph, then:

N’ is the subset of nodes in N related by edges in E’ E’ is a subset of E

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. 1367-1372, 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 IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Cuen, pp. 149-159, 2001. http://amalfi.dis.unina.it/graph/db/papers/vf-algorithm.pdf

See also

syntactic_feasibliity, semantic_feasibility

Notes

The implementation handles both directed and undirected graphs as well as multigraphs. However, it does require that nodes in the graph are orderable (in addition to the general NetworkX requirement that nodes are hashable). If the nodes in your graph are not orderable, you can convert them to an orderable type (int, for example) by using the networkx.relabel() function. You can store the dictionary of old-to-new node labels to retrieve the original node labels after running the isomorphism algorithm:

>>> G = nx.Graph()
>>> node1, node2 = object(), object()
>>> G.add_nodes_from([node1, node2])
>>> mapping = {k: v for v, k in enumerate(G)}
>>> G = nx.relabel_nodes(G, mapping)

In general, the subgraph isomorphism problem is NP-complete whereas the graph isomorphism problem is most likely not NP-complete (although no polynomial-time algorithm is known to exist).

Graph Matcher

GraphMatcher.__init__(G1, G2[, node_match, …])	Initialize graph matcher.
GraphMatcher.initialize()	Reinitializes the state of the algorithm.
GraphMatcher.is_isomorphic()	Returns True if G1 and G2 are isomorphic graphs.
GraphMatcher.subgraph_is_isomorphic()	Returns True if a subgraph of G1 is isomorphic to G2.
GraphMatcher.isomorphisms_iter()	Generator over isomorphisms between G1 and G2.
GraphMatcher.subgraph_isomorphisms_iter()	Generator over isomorphisms between a subgraph of G1 and G2.
GraphMatcher.candidate_pairs_iter()	Iterator over candidate pairs of nodes in G1 and G2.
GraphMatcher.match()	Extends the isomorphism mapping.
GraphMatcher.semantic_feasibility(G1_node, …)	Returns True if mapping G1_node to G2_node is semantically feasible.
GraphMatcher.syntactic_feasibility(G1_node, …)	Returns True if adding (G1_node, G2_node) is syntactically feasible.

DiGraph Matcher

DiGraphMatcher.__init__(G1, G2[, …])	Initialize graph matcher.
DiGraphMatcher.initialize()	Reinitializes the state of the algorithm.
DiGraphMatcher.is_isomorphic()	Returns True if G1 and G2 are isomorphic graphs.
DiGraphMatcher.subgraph_is_isomorphic()	Returns True if a subgraph of G1 is isomorphic to G2.
DiGraphMatcher.isomorphisms_iter()	Generator over isomorphisms between G1 and G2.
DiGraphMatcher.subgraph_isomorphisms_iter()	Generator over isomorphisms between a subgraph of G1 and G2.
DiGraphMatcher.candidate_pairs_iter()	Iterator over candidate pairs of nodes in G1 and G2.
DiGraphMatcher.match()	Extends the isomorphism mapping.
DiGraphMatcher.semantic_feasibility(G1_node, …)	Returns True if mapping G1_node to G2_node is semantically feasible.
DiGraphMatcher.syntactic_feasibility(…)	Returns True if adding (G1_node, G2_node) is syntactically feasible.

Match helpers

categorical_node_match(attr, default)	Returns a comparison function for a categorical node attribute.
categorical_edge_match(attr, default)	Returns a comparison function for a categorical edge attribute.
categorical_multiedge_match(attr, default)	Returns a comparison function for a categorical edge attribute.
numerical_node_match(attr, default[, rtol, atol])	Returns a comparison function for a numerical node attribute.
numerical_edge_match(attr, default[, rtol, atol])	Returns a comparison function for a numerical edge attribute.
numerical_multiedge_match(attr, default[, …])	Returns a comparison function for a numerical edge attribute.
generic_node_match(attr, default, op)	Returns a comparison function for a generic attribute.
generic_edge_match(attr, default, op)	Returns a comparison function for a generic attribute.
generic_multiedge_match(attr, default, op)	Returns a comparison function for a generic attribute.