Skip to main content
`Ctrl`+`K`

# modular_product

modular_product(G, H)

  Returns the Modular product of G and H.

  The modular product of `G` and `H` is the graph \(M = G \nabla H\), consisting of the node set \(V(M) = V(G) \times V(H)\) that is the Cartesian product of the node sets of `G` and `H`. Further, M contains an edge ((u, v), (x, y)):

  - if u is adjacent to x in `G` and v is adjacent to y in `H`, or

  - if u is not adjacent to x in `G` and v is not adjacent to y in `H`.

  More formally:

      E(M) = {((u, v), (x, y)) | ((u, x) in E(G) and (v, y) in E(H)) or
                                 ((u, x) not in E(G) and (v, y) not in E(H))}

  Parameters:
    G, H: NetworkX graphs

      The graphs to take the modular product of.

  Returns:
    M: NetworkX graph

      The Modular product of `G` and `H`.

  Raises:
    NetworkXNotImplemented

      If `G` is not a simple graph.

  Notes

  The modular product is defined in [1] and was first introduced as the weak modular product.

  The modular product reduces the problem of counting isomorphic subgraphs in `G` and `H` to the problem of counting cliques in M. The subgraphs of `G` and `H` that are induced by the nodes of a clique in M are isomorphic [2] [3].

  References

  [1]

  R. Hammack, W. Imrich, and S. Klavžar, “Handbook of Product Graphs”, CRC Press, 2011.

  [2]

  H. G. Barrow and R. M. Burstall, “Subgraph isomorphism, matching relational structures and maximal cliques”, Information Processing Letters, vol. 4, issue 4, pp. 83-84, 1976, https://doi.org/10.1016/0020-0190(76)90049-1.

  [3]

  V. G. Vizing, “Reduction of the problem of isomorphism and isomorphic entrance to the task of finding the nondensity of a graph.” Proc. Third All-Union Conference on Problems of Theoretical Cybernetics. 1974.

  Examples

      >>> G = nx.cycle_graph(4)
      >>> H = nx.path_graph(2)
      >>> M = nx.modular_product(G, H)
      >>> list(M)
      [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1)]
      >>> print(M)
      Graph with 8 nodes and 8 edges