networkx.algorithms.isomorphism.ISMAGS

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

Implements the ISMAGS subgraph matching algorithm. [1] 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)

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

analyze_symmetry(graph, node_partitions, ...)	Find a minimal set of permutations and corresponding co-sets that describe the symmetry of graph, given the node and edge equalities given by node_partitions and edge_colors, respectively.
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().