diff env/lib/python3.9/site-packages/networkx/algorithms/operators/tests/test_product.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/operators/tests/test_product.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,426 @@
+import pytest
+import networkx as nx
+from networkx.testing import assert_edges_equal
+
+
+def test_tensor_product_raises():
+    with pytest.raises(nx.NetworkXError):
+        P = nx.tensor_product(nx.DiGraph(), nx.Graph())
+
+
+def test_tensor_product_null():
+    null = nx.null_graph()
+    empty10 = nx.empty_graph(10)
+    K3 = nx.complete_graph(3)
+    K10 = nx.complete_graph(10)
+    P3 = nx.path_graph(3)
+    P10 = nx.path_graph(10)
+    # null graph
+    G = nx.tensor_product(null, null)
+    assert nx.is_isomorphic(G, null)
+    # null_graph X anything = null_graph and v.v.
+    G = nx.tensor_product(null, empty10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.tensor_product(null, K3)
+    assert nx.is_isomorphic(G, null)
+    G = nx.tensor_product(null, K10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.tensor_product(null, P3)
+    assert nx.is_isomorphic(G, null)
+    G = nx.tensor_product(null, P10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.tensor_product(empty10, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.tensor_product(K3, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.tensor_product(K10, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.tensor_product(P3, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.tensor_product(P10, null)
+    assert nx.is_isomorphic(G, null)
+
+
+def test_tensor_product_size():
+    P5 = nx.path_graph(5)
+    K3 = nx.complete_graph(3)
+    K5 = nx.complete_graph(5)
+
+    G = nx.tensor_product(P5, K3)
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.tensor_product(K3, K5)
+    assert nx.number_of_nodes(G) == 3 * 5
+
+
+def test_tensor_product_combinations():
+    # basic smoke test, more realistic tests would be useful
+    P5 = nx.path_graph(5)
+    K3 = nx.complete_graph(3)
+    G = nx.tensor_product(P5, K3)
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.tensor_product(P5, nx.MultiGraph(K3))
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.tensor_product(nx.MultiGraph(P5), K3)
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.tensor_product(nx.MultiGraph(P5), nx.MultiGraph(K3))
+    assert nx.number_of_nodes(G) == 5 * 3
+
+    G = nx.tensor_product(nx.DiGraph(P5), nx.DiGraph(K3))
+    assert nx.number_of_nodes(G) == 5 * 3
+
+
+def test_tensor_product_classic_result():
+    K2 = nx.complete_graph(2)
+    G = nx.petersen_graph()
+    G = nx.tensor_product(G, K2)
+    assert nx.is_isomorphic(G, nx.desargues_graph())
+
+    G = nx.cycle_graph(5)
+    G = nx.tensor_product(G, K2)
+    assert nx.is_isomorphic(G, nx.cycle_graph(10))
+
+    G = nx.tetrahedral_graph()
+    G = nx.tensor_product(G, K2)
+    assert nx.is_isomorphic(G, nx.cubical_graph())
+
+
+def test_tensor_product_random():
+    G = nx.erdos_renyi_graph(10, 2 / 10.0)
+    H = nx.erdos_renyi_graph(10, 2 / 10.0)
+    GH = nx.tensor_product(G, H)
+
+    for (u_G, u_H) in GH.nodes():
+        for (v_G, v_H) in GH.nodes():
+            if H.has_edge(u_H, v_H) and G.has_edge(u_G, v_G):
+                assert GH.has_edge((u_G, u_H), (v_G, v_H))
+            else:
+                assert not GH.has_edge((u_G, u_H), (v_G, v_H))
+
+
+def test_cartesian_product_multigraph():
+    G = nx.MultiGraph()
+    G.add_edge(1, 2, key=0)
+    G.add_edge(1, 2, key=1)
+    H = nx.MultiGraph()
+    H.add_edge(3, 4, key=0)
+    H.add_edge(3, 4, key=1)
+    GH = nx.cartesian_product(G, H)
+    assert set(GH) == {(1, 3), (2, 3), (2, 4), (1, 4)}
+    assert {(frozenset([u, v]), k) for u, v, k in GH.edges(keys=True)} == {
+        (frozenset([u, v]), k)
+        for u, v, k in [
+            ((1, 3), (2, 3), 0),
+            ((1, 3), (2, 3), 1),
+            ((1, 3), (1, 4), 0),
+            ((1, 3), (1, 4), 1),
+            ((2, 3), (2, 4), 0),
+            ((2, 3), (2, 4), 1),
+            ((2, 4), (1, 4), 0),
+            ((2, 4), (1, 4), 1),
+        ]
+    }
+
+
+def test_cartesian_product_raises():
+    with pytest.raises(nx.NetworkXError):
+        P = nx.cartesian_product(nx.DiGraph(), nx.Graph())
+
+
+def test_cartesian_product_null():
+    null = nx.null_graph()
+    empty10 = nx.empty_graph(10)
+    K3 = nx.complete_graph(3)
+    K10 = nx.complete_graph(10)
+    P3 = nx.path_graph(3)
+    P10 = nx.path_graph(10)
+    # null graph
+    G = nx.cartesian_product(null, null)
+    assert nx.is_isomorphic(G, null)
+    # null_graph X anything = null_graph and v.v.
+    G = nx.cartesian_product(null, empty10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.cartesian_product(null, K3)
+    assert nx.is_isomorphic(G, null)
+    G = nx.cartesian_product(null, K10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.cartesian_product(null, P3)
+    assert nx.is_isomorphic(G, null)
+    G = nx.cartesian_product(null, P10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.cartesian_product(empty10, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.cartesian_product(K3, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.cartesian_product(K10, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.cartesian_product(P3, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.cartesian_product(P10, null)
+    assert nx.is_isomorphic(G, null)
+
+
+def test_cartesian_product_size():
+    # order(GXH)=order(G)*order(H)
+    K5 = nx.complete_graph(5)
+    P5 = nx.path_graph(5)
+    K3 = nx.complete_graph(3)
+    G = nx.cartesian_product(P5, K3)
+    assert nx.number_of_nodes(G) == 5 * 3
+    assert nx.number_of_edges(G) == nx.number_of_edges(P5) * nx.number_of_nodes(
+        K3
+    ) + nx.number_of_edges(K3) * nx.number_of_nodes(P5)
+    G = nx.cartesian_product(K3, K5)
+    assert nx.number_of_nodes(G) == 3 * 5
+    assert nx.number_of_edges(G) == nx.number_of_edges(K5) * nx.number_of_nodes(
+        K3
+    ) + nx.number_of_edges(K3) * nx.number_of_nodes(K5)
+
+
+def test_cartesian_product_classic():
+    # test some classic product graphs
+    P2 = nx.path_graph(2)
+    P3 = nx.path_graph(3)
+    # cube = 2-path X 2-path
+    G = nx.cartesian_product(P2, P2)
+    G = nx.cartesian_product(P2, G)
+    assert nx.is_isomorphic(G, nx.cubical_graph())
+
+    # 3x3 grid
+    G = nx.cartesian_product(P3, P3)
+    assert nx.is_isomorphic(G, nx.grid_2d_graph(3, 3))
+
+
+def test_cartesian_product_random():
+    G = nx.erdos_renyi_graph(10, 2 / 10.0)
+    H = nx.erdos_renyi_graph(10, 2 / 10.0)
+    GH = nx.cartesian_product(G, H)
+
+    for (u_G, u_H) in GH.nodes():
+        for (v_G, v_H) in GH.nodes():
+            if (u_G == v_G and H.has_edge(u_H, v_H)) or (
+                u_H == v_H and G.has_edge(u_G, v_G)
+            ):
+                assert GH.has_edge((u_G, u_H), (v_G, v_H))
+            else:
+                assert not GH.has_edge((u_G, u_H), (v_G, v_H))
+
+
+def test_lexicographic_product_raises():
+    with pytest.raises(nx.NetworkXError):
+        P = nx.lexicographic_product(nx.DiGraph(), nx.Graph())
+
+
+def test_lexicographic_product_null():
+    null = nx.null_graph()
+    empty10 = nx.empty_graph(10)
+    K3 = nx.complete_graph(3)
+    K10 = nx.complete_graph(10)
+    P3 = nx.path_graph(3)
+    P10 = nx.path_graph(10)
+    # null graph
+    G = nx.lexicographic_product(null, null)
+    assert nx.is_isomorphic(G, null)
+    # null_graph X anything = null_graph and v.v.
+    G = nx.lexicographic_product(null, empty10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.lexicographic_product(null, K3)
+    assert nx.is_isomorphic(G, null)
+    G = nx.lexicographic_product(null, K10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.lexicographic_product(null, P3)
+    assert nx.is_isomorphic(G, null)
+    G = nx.lexicographic_product(null, P10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.lexicographic_product(empty10, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.lexicographic_product(K3, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.lexicographic_product(K10, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.lexicographic_product(P3, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.lexicographic_product(P10, null)
+    assert nx.is_isomorphic(G, null)
+
+
+def test_lexicographic_product_size():
+    K5 = nx.complete_graph(5)
+    P5 = nx.path_graph(5)
+    K3 = nx.complete_graph(3)
+    G = nx.lexicographic_product(P5, K3)
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.lexicographic_product(K3, K5)
+    assert nx.number_of_nodes(G) == 3 * 5
+
+
+def test_lexicographic_product_combinations():
+    P5 = nx.path_graph(5)
+    K3 = nx.complete_graph(3)
+    G = nx.lexicographic_product(P5, K3)
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.lexicographic_product(nx.MultiGraph(P5), K3)
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.lexicographic_product(P5, nx.MultiGraph(K3))
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.lexicographic_product(nx.MultiGraph(P5), nx.MultiGraph(K3))
+    assert nx.number_of_nodes(G) == 5 * 3
+
+    # No classic easily found classic results for lexicographic product
+
+
+def test_lexicographic_product_random():
+    G = nx.erdos_renyi_graph(10, 2 / 10.0)
+    H = nx.erdos_renyi_graph(10, 2 / 10.0)
+    GH = nx.lexicographic_product(G, H)
+
+    for (u_G, u_H) in GH.nodes():
+        for (v_G, v_H) in GH.nodes():
+            if G.has_edge(u_G, v_G) or (u_G == v_G and H.has_edge(u_H, v_H)):
+                assert GH.has_edge((u_G, u_H), (v_G, v_H))
+            else:
+                assert not GH.has_edge((u_G, u_H), (v_G, v_H))
+
+
+def test_strong_product_raises():
+    with pytest.raises(nx.NetworkXError):
+        P = nx.strong_product(nx.DiGraph(), nx.Graph())
+
+
+def test_strong_product_null():
+    null = nx.null_graph()
+    empty10 = nx.empty_graph(10)
+    K3 = nx.complete_graph(3)
+    K10 = nx.complete_graph(10)
+    P3 = nx.path_graph(3)
+    P10 = nx.path_graph(10)
+    # null graph
+    G = nx.strong_product(null, null)
+    assert nx.is_isomorphic(G, null)
+    # null_graph X anything = null_graph and v.v.
+    G = nx.strong_product(null, empty10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.strong_product(null, K3)
+    assert nx.is_isomorphic(G, null)
+    G = nx.strong_product(null, K10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.strong_product(null, P3)
+    assert nx.is_isomorphic(G, null)
+    G = nx.strong_product(null, P10)
+    assert nx.is_isomorphic(G, null)
+    G = nx.strong_product(empty10, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.strong_product(K3, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.strong_product(K10, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.strong_product(P3, null)
+    assert nx.is_isomorphic(G, null)
+    G = nx.strong_product(P10, null)
+    assert nx.is_isomorphic(G, null)
+
+
+def test_strong_product_size():
+    K5 = nx.complete_graph(5)
+    P5 = nx.path_graph(5)
+    K3 = nx.complete_graph(3)
+    G = nx.strong_product(P5, K3)
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.strong_product(K3, K5)
+    assert nx.number_of_nodes(G) == 3 * 5
+
+
+def test_strong_product_combinations():
+    P5 = nx.path_graph(5)
+    K3 = nx.complete_graph(3)
+    G = nx.strong_product(P5, K3)
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.strong_product(nx.MultiGraph(P5), K3)
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.strong_product(P5, nx.MultiGraph(K3))
+    assert nx.number_of_nodes(G) == 5 * 3
+    G = nx.strong_product(nx.MultiGraph(P5), nx.MultiGraph(K3))
+    assert nx.number_of_nodes(G) == 5 * 3
+
+    # No classic easily found classic results for strong product
+
+
+def test_strong_product_random():
+    G = nx.erdos_renyi_graph(10, 2 / 10.0)
+    H = nx.erdos_renyi_graph(10, 2 / 10.0)
+    GH = nx.strong_product(G, H)
+
+    for (u_G, u_H) in GH.nodes():
+        for (v_G, v_H) in GH.nodes():
+            if (
+                (u_G == v_G and H.has_edge(u_H, v_H))
+                or (u_H == v_H and G.has_edge(u_G, v_G))
+                or (G.has_edge(u_G, v_G) and H.has_edge(u_H, v_H))
+            ):
+                assert GH.has_edge((u_G, u_H), (v_G, v_H))
+            else:
+                assert not GH.has_edge((u_G, u_H), (v_G, v_H))
+
+
+def test_graph_power_raises():
+    with pytest.raises(nx.NetworkXNotImplemented):
+        nx.power(nx.MultiDiGraph(), 2)
+
+
+def test_graph_power():
+    # wikipedia example for graph power
+    G = nx.cycle_graph(7)
+    G.add_edge(6, 7)
+    G.add_edge(7, 8)
+    G.add_edge(8, 9)
+    G.add_edge(9, 2)
+    H = nx.power(G, 2)
+
+    assert_edges_equal(
+        list(H.edges()),
+        [
+            (0, 1),
+            (0, 2),
+            (0, 5),
+            (0, 6),
+            (0, 7),
+            (1, 9),
+            (1, 2),
+            (1, 3),
+            (1, 6),
+            (2, 3),
+            (2, 4),
+            (2, 8),
+            (2, 9),
+            (3, 4),
+            (3, 5),
+            (3, 9),
+            (4, 5),
+            (4, 6),
+            (5, 6),
+            (5, 7),
+            (6, 7),
+            (6, 8),
+            (7, 8),
+            (7, 9),
+            (8, 9),
+        ],
+    )
+
+
+def test_graph_power_negative():
+    with pytest.raises(ValueError):
+        nx.power(nx.Graph(), -1)
+
+
+def test_rooted_product_raises():
+    with pytest.raises(nx.NetworkXError):
+        nx.rooted_product(nx.Graph(), nx.path_graph(2), 10)
+
+
+def test_rooted_product():
+    G = nx.cycle_graph(5)
+    H = nx.Graph()
+    H.add_edges_from([("a", "b"), ("b", "c"), ("b", "d")])
+    R = nx.rooted_product(G, H, "a")
+    assert len(R) == len(G) * len(H)
+    assert R.size() == G.size() + len(G) * H.size()