Skip to main content
`Ctrl`+`K`

# 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.

## Advanced Interfaces

- VF2 Algorithm
  - Introduction
  - Examples
  - Subgraph Isomorphism
  - References
  - See Also
  - Notes
  - Graph Matcher
  - DiGraph Matcher
  - Match helpers
- ISMAGS Algorithm
  - Notes
  - References
- ISMAGS object
  - networkx.algorithms.isomorphism.ISMAGS