networkx.algorithms.isomorphism.ISMAGS¶

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

Implements the ISMAGS subgraph matching algorith. 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.

graph¶

Type: networkx.Graph

subgraph¶

Type: networkx.Graph

node_equality¶

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.

Type: collections.abc.Callable

edge_equality¶

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.

Type: collections.abc.Callable

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

__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 graph (`networkx.Graph`)
`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()`.