modular_product#
- modular_product(G, H)[source]#
Returns the Modular product of G and H.
The modular product of
G
andH
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 ofG
andH
. Further, M contains an edge ((u, v), (x, y)):if u is adjacent to x in
G
and v is adjacent to y inH
, orif u is not adjacent to x in
G
and v is not adjacent to y inH
.
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
andH
.
- 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
andH
to the problem of counting cliques in M. The subgraphs ofG
andH
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