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)	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: to check whether two graphs are isomorphic. vf2pp_isomorphism: to obtain the node mapping between two graphs, in case they are isomorphic. vf2pp_all_isomorphisms: to generate all possible mappings between two graphs, if isomorphic.

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.

The optimal node ordering is obtained after taking into consideration both the degree but also the label rarity of each node. This way we place the nodes that are more likely to match, first in the order, thus examining the most promising branches in the beginning. The rules also consider node labels, making it easier to prune unfruitful branches early in the process.

Examples#

Suppose G1 and G2 are Isomorphic Graphs. Verification is as follows:

Without node labels:

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

With node labels:

>>> G1 = nx.path_graph(4)
>>> G2 = nx.path_graph(4)
>>> mapped = {1: 1, 2: 2, 3: 3, 0: 0}
>>> nx.set_node_attributes(G1, dict(zip(G1, ["blue", "red", "green", "yellow"])), "label")
>>> nx.set_node_attributes(G2, dict(zip([mapped[u] for u in G1], ["blue", "red", "green", "yellow"])), "label")
>>> nx.vf2pp_is_isomorphic(G1, G2, node_label="label")
True
>>> nx.vf2pp_isomorphism(G1, G2, node_label="label")
{1: 1, 2: 2, 0: 0, 3: 3}

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`(G1, G2[, node_label, ...])	Examines whether G1 and G2 are isomorphic.
`vf2pp_all_isomorphisms`(G1, G2[, node_label, ...])	Yields all the possible mappings between G1 and G2.
`vf2pp_isomorphism`(G1, G2[, node_label, ...])	Return an isomorphic mapping between `G1` and `G2` 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)	Given two rooted trees `t1` and `t2`, with roots `root1` and `root2` respectively this routine will determine if they are isomorphic.
`tree_isomorphism`(t1, t2)	Given two undirected (or free) trees `t1` and `t2`, this routine will determine if they are isomorphic.