# networkx.algorithms.isomorphism.ISMAGS¶

class ISMAGS(graph, subgraph, node_match=None, edge_match=None, cache=None)[source]

Implements the ISMAGS subgraph matching algorith.  ISMAGS stands for “Index-based Subgraph Matching Algorithm with General Symmetries”. As the name implies, it is symmetry aware and will only generate non-symmetric isomorphisms.

Notes

The implementation imposes additional conditions compared to the VF2 algorithm on the graphs provided and the comparison functions (`node_equality` and `edge_equality`):

• Node keys in both graphs must be orderable as well as hashable.

• Equality must be transitive: if A is equal to B, and B is equal to C, then A must be 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

Attributes
graph: networkx.Graph
subgraph: networkx.Graph
node_equality: collections.abc.Callable

The function called to see if two nodes should be considered equal. It’s signature looks like this: `f(graph1: networkx.Graph, node1, graph2: networkx.Graph, node2) -> bool`. `node1` is a node in `graph1`, and `node2` a node in `graph2`. Constructed from the argument `node_match`.

edge_equality: collections.abc.Callable

The function called to see if two edges should be considered equal. It’s signature looks like this: `f(graph1: networkx.Graph, edge1, graph2: networkx.Graph, edge2) -> bool`. `edge1` is an edge in `graph1`, and `edge2` an edge in `graph2`. Constructed from the argument `edge_match`.

__init__(graph, subgraph, node_match=None, edge_match=None, cache=None)[source]
Parameters
graph: networkx.Graph
subgraph: networkx.Graph
node_match: collections.abc.Callable or None

Function used to determine whether two nodes are equivalent. Its signature should look like `f(n1: dict, n2: dict) -> bool`, with `n1` and `n2` node property dicts. See also `categorical_node_match()` and friends. If `None`, all nodes are considered equal.

edge_match: collections.abc.Callable or None

Function used to determine whether two edges are equivalent. Its signature should look like `f(e1: dict, e2: dict) -> bool`, with `e1` and `e2` edge property dicts. See also `categorical_edge_match()` and friends. If `None`, all edges are considered equal.

cache: collections.abc.Mapping

A cache used for caching graph symmetries.

Methods

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