Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

# ISMAGS Algorithm¶

Provides a Python implementation of the ISMAGS algorithm. [1]

It is capable of finding (subgraph) isomorphisms between two graphs, taking the symmetry of the subgraph into account. In most cases the VF2 algorithm is faster (at least on small graphs) than this implementation, but in some cases there is an exponential number of isomorphisms that are symmetrically equivalent. In that case, the ISMAGS algorithm will provide only one solution per symmetry group.

```>>> petersen = nx.petersen_graph()
>>> ismags = nx.isomorphism.ISMAGS(petersen, petersen)
>>> isomorphisms = list(ismags.isomorphisms_iter(symmetry=False))
>>> len(isomorphisms)
120
>>> isomorphisms = list(ismags.isomorphisms_iter(symmetry=True))
>>> answer = [{0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9}]
True
```

In addition, this implementation also provides an interface to find the largest common induced subgraph [2] between any two graphs, again taking symmetry into account. Given `graph` and `subgraph` the algorithm will remove nodes from the `subgraph` until `subgraph` is isomorphic to a subgraph of `graph`. Since only the symmetry of `subgraph` is taken into account it is worth thinking about how you provide your graphs:

```>>> graph1 = nx.path_graph(4)
>>> graph2 = nx.star_graph(3)
>>> ismags = nx.isomorphism.ISMAGS(graph1, graph2)
>>> ismags.is_isomorphic()
False
>>> largest_common_subgraph = list(ismags.largest_common_subgraph())
>>> answer = [{1: 0, 0: 1, 2: 2}, {2: 0, 1: 1, 3: 2}]
True
>>> ismags2 = nx.isomorphism.ISMAGS(graph2, graph1)
>>> largest_common_subgraph = list(ismags2.largest_common_subgraph())
...     {1: 0, 0: 1, 2: 2},
...     {1: 0, 0: 1, 3: 2},
...     {2: 0, 0: 1, 1: 2},
...     {2: 0, 0: 1, 3: 2},
...     {3: 0, 0: 1, 1: 2},
...     {3: 0, 0: 1, 2: 2},
... ]
True
```

However, when not taking symmetry into account, it doesn’t matter:

```>>> largest_common_subgraph = list(ismags.largest_common_subgraph(symmetry=False))
...     {1: 0, 0: 1, 2: 2},
...     {1: 0, 2: 1, 0: 2},
...     {2: 0, 1: 1, 3: 2},
...     {2: 0, 3: 1, 1: 2},
...     {1: 0, 0: 1, 2: 3},
...     {1: 0, 2: 1, 0: 3},
...     {2: 0, 1: 1, 3: 3},
...     {2: 0, 3: 1, 1: 3},
...     {1: 0, 0: 2, 2: 3},
...     {1: 0, 2: 2, 0: 3},
...     {2: 0, 1: 2, 3: 3},
...     {2: 0, 3: 2, 1: 3},
... ]
True
>>> largest_common_subgraph = list(ismags2.largest_common_subgraph(symmetry=False))
...     {1: 0, 0: 1, 2: 2},
...     {1: 0, 0: 1, 3: 2},
...     {2: 0, 0: 1, 1: 2},
...     {2: 0, 0: 1, 3: 2},
...     {3: 0, 0: 1, 1: 2},
...     {3: 0, 0: 1, 2: 2},
...     {1: 1, 0: 2, 2: 3},
...     {1: 1, 0: 2, 3: 3},
...     {2: 1, 0: 2, 1: 3},
...     {2: 1, 0: 2, 3: 3},
...     {3: 1, 0: 2, 1: 3},
...     {3: 1, 0: 2, 2: 3},
... ]
True
```

## Notes¶

• The current implementation works for undirected graphs only. The algorithm in general should work for directed graphs as well though.

• Node keys for both provided graphs need to be fully orderable as well as hashable.

• Node and edge equality is assumed to be transitive: if A is equal to B, and B is equal to C, then A is equal to C.

## References¶

1

M. Houbraken, S. Demeyer, T. Michoel, P. Audenaert, D. Colle, M. Pickavet, “The Index-Based Subgraph Matching Algorithm with General Symmetries (ISMAGS): Exploiting Symmetry for Faster Subgraph Enumeration”, PLoS One 9(5): e97896, 2014. https://doi.org/10.1371/journal.pone.0097896

2

https://en.wikipedia.org/wiki/Maximum_common_induced_subgraph

## ISMAGS object¶

 `ISMAGS`(graph, subgraph[, node_match, …]) Implements the ISMAGS subgraph matching algorith. `ISMAGS.analyze_symmetry`(graph, …) Find a minimal set of permutations and corresponding co-sets that describe the symmetry of `subgraph`. `ISMAGS.is_isomorphic`([symmetry]) Returns True if `graph` is isomorphic to `subgraph` and False otherwise. `ISMAGS.subgraph_is_isomorphic`([symmetry]) Returns True if a subgraph of `graph` is isomorphic to `subgraph` and False otherwise. `ISMAGS.isomorphisms_iter`([symmetry]) Does the same as `find_isomorphisms()` if `graph` and `subgraph` have the same number of nodes. `ISMAGS.subgraph_isomorphisms_iter`([symmetry]) Alternative name for `find_isomorphisms()`. `ISMAGS.largest_common_subgraph`([symmetry]) Find the largest common induced subgraphs between `subgraph` and `graph`.