diff env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/tests/test_ismags.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/isomorphism/tests/test_ismags.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,327 @@
+"""
+    Tests for ISMAGS isomorphism algorithm.
+"""
+
+import pytest
+import networkx as nx
+from networkx.algorithms import isomorphism as iso
+
+
+def _matches_to_sets(matches):
+    """
+    Helper function to facilitate comparing collections of dictionaries in
+    which order does not matter.
+    """
+    return set(map(lambda m: frozenset(m.items()), matches))
+
+
+class TestSelfIsomorphism:
+    data = [
+        (
+            [
+                (0, dict(name="a")),
+                (1, dict(name="a")),
+                (2, dict(name="b")),
+                (3, dict(name="b")),
+                (4, dict(name="a")),
+                (5, dict(name="a")),
+            ],
+            [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)],
+        ),
+        (range(1, 5), [(1, 2), (2, 4), (4, 3), (3, 1)]),
+        (
+            [],
+            [
+                (0, 1),
+                (1, 2),
+                (2, 3),
+                (3, 4),
+                (4, 5),
+                (5, 0),
+                (0, 6),
+                (6, 7),
+                (2, 8),
+                (8, 9),
+                (4, 10),
+                (10, 11),
+            ],
+        ),
+        ([], [(0, 1), (1, 2), (1, 4), (2, 3), (3, 5), (3, 6)]),
+    ]
+
+    def test_self_isomorphism(self):
+        """
+        For some small, symmetric graphs, make sure that 1) they are isomorphic
+        to themselves, and 2) that only the identity mapping is found.
+        """
+        for node_data, edge_data in self.data:
+            graph = nx.Graph()
+            graph.add_nodes_from(node_data)
+            graph.add_edges_from(edge_data)
+
+            ismags = iso.ISMAGS(
+                graph, graph, node_match=iso.categorical_node_match("name", None)
+            )
+            assert ismags.is_isomorphic()
+            assert ismags.subgraph_is_isomorphic()
+            assert list(ismags.subgraph_isomorphisms_iter(symmetry=True)) == [
+                {n: n for n in graph.nodes}
+            ]
+
+    def test_edgecase_self_isomorphism(self):
+        """
+        This edgecase is one of the cases in which it is hard to find all
+        symmetry elements.
+        """
+        graph = nx.Graph()
+        nx.add_path(graph, range(5))
+        graph.add_edges_from([(2, 5), (5, 6)])
+
+        ismags = iso.ISMAGS(graph, graph)
+        ismags_answer = list(ismags.find_isomorphisms(True))
+        assert ismags_answer == [{n: n for n in graph.nodes}]
+
+        graph = nx.relabel_nodes(graph, {0: 0, 1: 1, 2: 2, 3: 3, 4: 6, 5: 4, 6: 5})
+        ismags = iso.ISMAGS(graph, graph)
+        ismags_answer = list(ismags.find_isomorphisms(True))
+        assert ismags_answer == [{n: n for n in graph.nodes}]
+
+    @pytest.mark.skip()
+    def test_directed_self_isomorphism(self):
+        """
+        For some small, directed, symmetric graphs, make sure that 1) they are
+        isomorphic to themselves, and 2) that only the identity mapping is
+        found.
+        """
+        for node_data, edge_data in self.data:
+            graph = nx.Graph()
+            graph.add_nodes_from(node_data)
+            graph.add_edges_from(edge_data)
+
+            ismags = iso.ISMAGS(
+                graph, graph, node_match=iso.categorical_node_match("name", None)
+            )
+            assert ismags.is_isomorphic()
+            assert ismags.subgraph_is_isomorphic()
+            assert list(ismags.subgraph_isomorphisms_iter(symmetry=True)) == [
+                {n: n for n in graph.nodes}
+            ]
+
+
+class TestSubgraphIsomorphism:
+    def test_isomorphism(self):
+        g1 = nx.Graph()
+        nx.add_cycle(g1, range(4))
+
+        g2 = nx.Graph()
+        nx.add_cycle(g2, range(4))
+        g2.add_edges_from([(n, m) for n, m in zip(g2, range(4, 8))])
+        ismags = iso.ISMAGS(g2, g1)
+        assert list(ismags.subgraph_isomorphisms_iter(symmetry=True)) == [
+            {n: n for n in g1.nodes}
+        ]
+
+    def test_isomorphism2(self):
+        g1 = nx.Graph()
+        nx.add_path(g1, range(3))
+
+        g2 = g1.copy()
+        g2.add_edge(1, 3)
+
+        ismags = iso.ISMAGS(g2, g1)
+        matches = ismags.subgraph_isomorphisms_iter(symmetry=True)
+        expected_symmetric = [
+            {0: 0, 1: 1, 2: 2},
+            {0: 0, 1: 1, 3: 2},
+            {2: 0, 1: 1, 3: 2},
+        ]
+        assert _matches_to_sets(matches) == _matches_to_sets(expected_symmetric)
+
+        matches = ismags.subgraph_isomorphisms_iter(symmetry=False)
+        expected_asymmetric = [
+            {0: 2, 1: 1, 2: 0},
+            {0: 2, 1: 1, 3: 0},
+            {2: 2, 1: 1, 3: 0},
+        ]
+        assert _matches_to_sets(matches) == _matches_to_sets(
+            expected_symmetric + expected_asymmetric
+        )
+
+    def test_labeled_nodes(self):
+        g1 = nx.Graph()
+        nx.add_cycle(g1, range(3))
+        g1.nodes[1]["attr"] = True
+
+        g2 = g1.copy()
+        g2.add_edge(1, 3)
+        ismags = iso.ISMAGS(g2, g1, node_match=lambda x, y: x == y)
+        matches = ismags.subgraph_isomorphisms_iter(symmetry=True)
+        expected_symmetric = [{0: 0, 1: 1, 2: 2}]
+        assert _matches_to_sets(matches) == _matches_to_sets(expected_symmetric)
+
+        matches = ismags.subgraph_isomorphisms_iter(symmetry=False)
+        expected_asymmetric = [{0: 2, 1: 1, 2: 0}]
+        assert _matches_to_sets(matches) == _matches_to_sets(
+            expected_symmetric + expected_asymmetric
+        )
+
+    def test_labeled_edges(self):
+        g1 = nx.Graph()
+        nx.add_cycle(g1, range(3))
+        g1.edges[1, 2]["attr"] = True
+
+        g2 = g1.copy()
+        g2.add_edge(1, 3)
+        ismags = iso.ISMAGS(g2, g1, edge_match=lambda x, y: x == y)
+        matches = ismags.subgraph_isomorphisms_iter(symmetry=True)
+        expected_symmetric = [{0: 0, 1: 1, 2: 2}]
+        assert _matches_to_sets(matches) == _matches_to_sets(expected_symmetric)
+
+        matches = ismags.subgraph_isomorphisms_iter(symmetry=False)
+        expected_asymmetric = [{1: 2, 0: 0, 2: 1}]
+        assert _matches_to_sets(matches) == _matches_to_sets(
+            expected_symmetric + expected_asymmetric
+        )
+
+
+class TestWikipediaExample:
+    # Nodes 'a', 'b', 'c' and 'd' form a column.
+    # Nodes 'g', 'h', 'i' and 'j' form a column.
+    g1edges = [
+        ["a", "g"],
+        ["a", "h"],
+        ["a", "i"],
+        ["b", "g"],
+        ["b", "h"],
+        ["b", "j"],
+        ["c", "g"],
+        ["c", "i"],
+        ["c", "j"],
+        ["d", "h"],
+        ["d", "i"],
+        ["d", "j"],
+    ]
+
+    # Nodes 1,2,3,4 form the clockwise corners of a large square.
+    # Nodes 5,6,7,8 form the clockwise corners of a small square
+    g2edges = [
+        [1, 2],
+        [2, 3],
+        [3, 4],
+        [4, 1],
+        [5, 6],
+        [6, 7],
+        [7, 8],
+        [8, 5],
+        [1, 5],
+        [2, 6],
+        [3, 7],
+        [4, 8],
+    ]
+
+    def test_graph(self):
+        g1 = nx.Graph()
+        g2 = nx.Graph()
+        g1.add_edges_from(self.g1edges)
+        g2.add_edges_from(self.g2edges)
+        gm = iso.ISMAGS(g1, g2)
+        assert gm.is_isomorphic()
+
+
+class TestLargestCommonSubgraph:
+    def test_mcis(self):
+        # Example graphs from DOI: 10.1002/spe.588
+        graph1 = nx.Graph()
+        graph1.add_edges_from([(1, 2), (2, 3), (2, 4), (3, 4), (4, 5)])
+        graph1.nodes[1]["color"] = 0
+
+        graph2 = nx.Graph()
+        graph2.add_edges_from(
+            [(1, 2), (2, 3), (2, 4), (3, 4), (3, 5), (5, 6), (5, 7), (6, 7)]
+        )
+        graph2.nodes[1]["color"] = 1
+        graph2.nodes[6]["color"] = 2
+        graph2.nodes[7]["color"] = 2
+
+        ismags = iso.ISMAGS(
+            graph1, graph2, node_match=iso.categorical_node_match("color", None)
+        )
+        assert list(ismags.subgraph_isomorphisms_iter(True)) == []
+        assert list(ismags.subgraph_isomorphisms_iter(False)) == []
+        found_mcis = _matches_to_sets(ismags.largest_common_subgraph())
+        expected = _matches_to_sets(
+            [{2: 2, 3: 4, 4: 3, 5: 5}, {2: 4, 3: 2, 4: 3, 5: 5}]
+        )
+        assert expected == found_mcis
+
+        ismags = iso.ISMAGS(
+            graph2, graph1, node_match=iso.categorical_node_match("color", None)
+        )
+        assert list(ismags.subgraph_isomorphisms_iter(True)) == []
+        assert list(ismags.subgraph_isomorphisms_iter(False)) == []
+        found_mcis = _matches_to_sets(ismags.largest_common_subgraph())
+        # Same answer, but reversed.
+        expected = _matches_to_sets(
+            [{2: 2, 3: 4, 4: 3, 5: 5}, {4: 2, 2: 3, 3: 4, 5: 5}]
+        )
+        assert expected == found_mcis
+
+    def test_symmetry_mcis(self):
+        graph1 = nx.Graph()
+        nx.add_path(graph1, range(4))
+
+        graph2 = nx.Graph()
+        nx.add_path(graph2, range(3))
+        graph2.add_edge(1, 3)
+
+        # Only the symmetry of graph2 is taken into account here.
+        ismags1 = iso.ISMAGS(
+            graph1, graph2, node_match=iso.categorical_node_match("color", None)
+        )
+        assert list(ismags1.subgraph_isomorphisms_iter(True)) == []
+        found_mcis = _matches_to_sets(ismags1.largest_common_subgraph())
+        expected = _matches_to_sets([{0: 0, 1: 1, 2: 2}, {1: 0, 3: 2, 2: 1}])
+        assert expected == found_mcis
+
+        # Only the symmetry of graph1 is taken into account here.
+        ismags2 = iso.ISMAGS(
+            graph2, graph1, node_match=iso.categorical_node_match("color", None)
+        )
+        assert list(ismags2.subgraph_isomorphisms_iter(True)) == []
+        found_mcis = _matches_to_sets(ismags2.largest_common_subgraph())
+        expected = _matches_to_sets(
+            [
+                {3: 2, 0: 0, 1: 1},
+                {2: 0, 0: 2, 1: 1},
+                {3: 0, 0: 2, 1: 1},
+                {3: 0, 1: 1, 2: 2},
+                {0: 0, 1: 1, 2: 2},
+                {2: 0, 3: 2, 1: 1},
+            ]
+        )
+
+        assert expected == found_mcis
+
+        found_mcis1 = _matches_to_sets(ismags1.largest_common_subgraph(False))
+        found_mcis2 = ismags2.largest_common_subgraph(False)
+        found_mcis2 = [{v: k for k, v in d.items()} for d in found_mcis2]
+        found_mcis2 = _matches_to_sets(found_mcis2)
+
+        expected = _matches_to_sets(
+            [
+                {3: 2, 1: 3, 2: 1},
+                {2: 0, 0: 2, 1: 1},
+                {1: 2, 3: 3, 2: 1},
+                {3: 0, 1: 3, 2: 1},
+                {0: 2, 2: 3, 1: 1},
+                {3: 0, 1: 2, 2: 1},
+                {2: 0, 0: 3, 1: 1},
+                {0: 0, 2: 3, 1: 1},
+                {1: 0, 3: 3, 2: 1},
+                {1: 0, 3: 2, 2: 1},
+                {0: 3, 1: 1, 2: 2},
+                {0: 0, 1: 1, 2: 2},
+            ]
+        )
+        assert expected == found_mcis1
+        assert expected == found_mcis2