Isomorphism#

is_isomorphic(G1, G2[, node_match, edge_match])

Returns True if the graphs G1 and G2 are isomorphic and False otherwise.

could_be_isomorphic(G1, G2, *[, properties])

Returns False if graphs are definitely not isomorphic.

fast_could_be_isomorphic(G1, G2)

Returns False if graphs are definitely not isomorphic.

faster_could_be_isomorphic(G1, G2)

Returns False if graphs are definitely not isomorphic.

VF2++#

VF2++ Algorithm#

An implementation of the VF2++ algorithm [1] for Graph Isomorphism testing.

The simplest interface to use this module is to call:

vf2pp_is_isomorphic: check whether two graphs are isomorphic. vf2pp_isomorphism: obtain the node isomorphism mapping between two graphs, if they are isomorphic. vf2pp_all_isomorphisms: generate all possible isomorphism mappings between two graphs, if isomorphic.

vf2pp_subgraph_is_isomorphic: check whether a specified graph is isomorphic to an induced subgraph of the other graph. vf2pp_subgraph_isomorphism: obtain the node isomorphism mapping between a specified graph and any induced subgraph of the other graph, if possible. vf2pp_all_subgraph_isomorphisms: generate all possible isomorphism mappings between the specified induced subgraph and the graph.

vf2pp_is_monomorphic: check whether two graphs are monomorphic. That is, the node and edge sets of one are subsets of the other’s node and edge sets. vf2pp_monomorphism: obtain the node monomorphism mapping between a specified graph and any subgraph of the other graph, if possible. vf2pp_all_monomorphisms: generate all possible monomorphism mappings between the specified subgraph and the graph.

Introduction#

The VF2++ algorithm, follows a similar logic to that of VF2, while also introducing new easy-to-check cutting rules and determining the optimal access order of nodes. It is also implemented in a non-recursive manner, which saves both time and space, when compared to its previous counterpart.

An improved node ordering is obtained after taking into consideration both the degree and the label rarity of each node. This way we consider the nodes that eliminate the most branches of the possible mapping search tree, so we can cut out unfruitful branches early in the process.

Warning: The VF2++ paper uses the symbols G1 and G2 for the two graphs of interest just as the VF2 paper does. But for subgraph functions the first graph is smaller in VF2++ while the second is smaller for VF2 and for ISMAGS. This implementation, VF2pp, matches the VF2 and ISMAGS notation with the second input being no larger than the first. To avoid confusion with the papers we name the graphs FG and SG for full graph and smaller graph. For VF2pp, SG corresponds to the paper’s G1 while FG corresponds to G2. This does not matter for the isomorphism functions (where the graphs have the same size).

Examples#

Suppose SG and FG are Isomorphic Graphs. Verification is as follows:

Without node labels:

>>> import networkx as nx
>>> SG = nx.path_graph(4)
>>> FG = nx.path_graph(4)
>>> nx.vf2pp_is_isomorphic(FG, SG, node_label=None)
True
>>> map = nx.vf2pp_isomorphism(FG, SG, node_label=None)
>>> map == {1: 1, 2: 2, 0: 0, 3: 3}
True

With node labels:

>>> nx.set_node_attributes(SG, dict(zip(SG, ["blue", "red", "cyan", "pink"])), "label")
>>> nx.set_node_attributes(FG, dict(zip(FG, ["blue", "red", "cyan", "pink"])), "label")
>>> nx.vf2pp_is_isomorphic(FG, SG, node_label="label")
True
>>> map = nx.vf2pp_isomorphism(FG, SG, node_label="label")
>>> map == {1: 1, 2: 2, 0: 0, 3: 3}
True

For subgraph isomorphism we look for induced subgraphs of FG that are isomorphic to SG. The process is similar to graph isomorphism with a different function:

>>> SG = nx.path_graph(3)
>>> FG = nx.path_graph(4)
>>> nx.vf2pp_subgraph_is_isomorphic(FG, SG, node_label=None)
True
>>> map = nx.vf2pp_subgraph_isomorphism(FG, SG, node_label=None)
>>> map == {1: 1, 2: 2, 0: 0}
True

With node labels:

>>> nx.set_node_attributes(SG, dict(zip(SG, ["blue", "red", "cyan"])), "label")
>>> nx.set_node_attributes(FG, dict(zip(FG, ["blue", "red", "cyan", "pink"])), "label")
>>> nx.vf2pp_subgraph_is_isomorphic(FG, SG, node_label="label")
True
>>> map = nx.vf2pp_subgraph_isomorphism(FG, SG, node_label="label")
>>> map == {1: 1, 2: 2, 0: 0}
True

For subgraph monomorphism we look for possibly non-induced subgraphs of FG that are isomorphic to SG. That means we only need a subset of nodes and edges of the first that map to nodes and edges of the second. But not all edges in the second graph need to be mapped to, even if that edge involves two nodes that are mapped to.

A classic example of this is a path graph mapping to a subgraph of a cycle graph with the same number of nodes. The missing edge in the path graph means that no subgraph isomorphism exists. But a monomorphism exists because not all induced edges need to be mapped to.

>>> SG = nx.path_graph(4)
>>> FG = nx.cycle_graph(4)
>>> nx.vf2pp_is_monomorphic(FG, SG, node_label=None)
True
>>> map = nx.vf2pp_monomorphism(FG, SG, node_label=None)
>>> map == {1: 0, 2: 1, 0: 3, 3: 2}
True

With node labels:

>>> nx.set_node_attributes(SG, dict(zip(SG, ["blue", "red", "cyan", "pink"])), "label")
>>> nx.set_node_attributes(FG, dict(zip(FG, ["blue", "red", "cyan", "pink"])), "label")
>>> nx.vf2pp_is_monomorphic(FG, SG, node_label="label")
True
>>> map = nx.vf2pp_monomorphism(FG, SG, node_label="label")
>>> map == {1: 1, 2: 2, 0: 0, 3: 3}
True

References#

[1]

Jüttner, Alpár & Madarasi, Péter. (2018). “VF2++—An improved subgraph isomorphism algorithm”. Discrete Applied Mathematics. 242. https://doi.org/10.1016/j.dam.2018.02.018

vf2pp_is_isomorphic(FG, SG[, node_label, ...])

Examines whether SG and FG are isomorphic.

vf2pp_all_isomorphisms(FG, SG[, node_label, ...])

Yields all the possible mappings between SG and FG.

vf2pp_isomorphism(FG, SG[, node_label, ...])

Return an isomorphic mapping between SG and FG if it exists.

Tree Isomorphism#

An algorithm for finding if two undirected trees are isomorphic, and if so returns an isomorphism between the two sets of nodes.

This algorithm uses a routine to tell if two rooted trees (trees with a specified root node) are isomorphic, which may be independently useful.

This implements an algorithm from: The Design and Analysis of Computer Algorithms by Aho, Hopcroft, and Ullman Addison-Wesley Publishing 1974 Example 3.2 pp. 84-86.

A more understandable version of this algorithm is described in: Homework Assignment 5 McGill University SOCS 308-250B, Winter 2002 by Matthew Suderman http://crypto.cs.mcgill.ca/~crepeau/CS250/2004/HW5+.pdf

rooted_tree_isomorphism(t1, root1, t2, root2)

Return an isomorphic mapping between rooted trees t1 and t2 with roots root1 and root2, respectively.

tree_isomorphism(t1, t2)

Return an isomorphic mapping between two trees t1 and t2.

Advanced Interfaces#