Skip to main content
`Ctrl`+`K`

# 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.

  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`.

  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

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