networkx.algorithms.isomorphism.ISMAGS#
- class ISMAGS(graph, subgraph, node_match=None, edge_match=None, cache=None)[source]#
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
andedge_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 ingraph1
, andnode2
a node ingraph2
. Constructed from the argumentnode_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 ingraph1
, andedge2
an edge ingraph2
. Constructed from the argumentedge_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
, withn1
andn2
node property dicts. See alsocategorical_node_match()
and friends. IfNone
, 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
, withe1
ande2
edge property dicts. See alsocategorical_edge_match()
and friends. IfNone
, 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 bynode_partitions
andedge_colors
, respectively.find_isomorphisms
([symmetry])Find all subgraph isomorphisms between subgraph and graph
is_isomorphic
([symmetry])Returns True if
graph
is isomorphic tosubgraph
and False otherwise.isomorphisms_iter
([symmetry])Does the same as
find_isomorphisms()
ifgraph
andsubgraph
have the same number of nodes.largest_common_subgraph
([symmetry])Find the largest common induced subgraphs between
subgraph
andgraph
.subgraph_is_isomorphic
([symmetry])Returns True if a subgraph of
graph
is isomorphic tosubgraph
and False otherwise.subgraph_isomorphisms_iter
([symmetry])Alternative name for
find_isomorphisms()
.