diff options
Diffstat (limited to '.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests')
14 files changed, 6267 insertions, 0 deletions
diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/__init__.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/__init__.py new file mode 100644 index 00000000..e69de29b --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/__init__.py diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/iso_r01_s80.A99 b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/iso_r01_s80.A99 new file mode 100644 index 00000000..dac54f00 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/iso_r01_s80.A99 Binary files differdiff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/iso_r01_s80.B99 b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/iso_r01_s80.B99 new file mode 100644 index 00000000..6c6af680 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/iso_r01_s80.B99 Binary files differdiff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/si2_b06_m200.A99 b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/si2_b06_m200.A99 new file mode 100644 index 00000000..60c3a3ce --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/si2_b06_m200.A99 Binary files differdiff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/si2_b06_m200.B99 b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/si2_b06_m200.B99 new file mode 100644 index 00000000..02368720 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/si2_b06_m200.B99 Binary files differdiff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_ismags.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_ismags.py new file mode 100644 index 00000000..bc4070ac --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_ismags.py @@ -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 {frozenset(m.items()) for m in matches} + + +class TestSelfIsomorphism: + data = [ + ( + [ + (0, {"name": "a"}), + (1, {"name": "a"}), + (2, {"name": "b"}), + (3, {"name": "b"}), + (4, {"name": "a"}), + (5, {"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}] + + 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(list(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 diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_isomorphism.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_isomorphism.py new file mode 100644 index 00000000..548af808 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_isomorphism.py @@ -0,0 +1,48 @@ +import pytest + +import networkx as nx +from networkx.algorithms import isomorphism as iso + + +class TestIsomorph: + @classmethod + def setup_class(cls): + cls.G1 = nx.Graph() + cls.G2 = nx.Graph() + cls.G3 = nx.Graph() + cls.G4 = nx.Graph() + cls.G5 = nx.Graph() + cls.G6 = nx.Graph() + cls.G1.add_edges_from([[1, 2], [1, 3], [1, 5], [2, 3]]) + cls.G2.add_edges_from([[10, 20], [20, 30], [10, 30], [10, 50]]) + cls.G3.add_edges_from([[1, 2], [1, 3], [1, 5], [2, 5]]) + cls.G4.add_edges_from([[1, 2], [1, 3], [1, 5], [2, 4]]) + cls.G5.add_edges_from([[1, 2], [1, 3]]) + cls.G6.add_edges_from([[10, 20], [20, 30], [10, 30], [10, 50], [20, 50]]) + + def test_could_be_isomorphic(self): + assert iso.could_be_isomorphic(self.G1, self.G2) + assert iso.could_be_isomorphic(self.G1, self.G3) + assert not iso.could_be_isomorphic(self.G1, self.G4) + assert iso.could_be_isomorphic(self.G3, self.G2) + assert not iso.could_be_isomorphic(self.G1, self.G6) + + def test_fast_could_be_isomorphic(self): + assert iso.fast_could_be_isomorphic(self.G3, self.G2) + assert not iso.fast_could_be_isomorphic(self.G3, self.G5) + assert not iso.fast_could_be_isomorphic(self.G1, self.G6) + + def test_faster_could_be_isomorphic(self): + assert iso.faster_could_be_isomorphic(self.G3, self.G2) + assert not iso.faster_could_be_isomorphic(self.G3, self.G5) + assert not iso.faster_could_be_isomorphic(self.G1, self.G6) + + def test_is_isomorphic(self): + assert iso.is_isomorphic(self.G1, self.G2) + assert not iso.is_isomorphic(self.G1, self.G4) + assert iso.is_isomorphic(self.G1.to_directed(), self.G2.to_directed()) + assert not iso.is_isomorphic(self.G1.to_directed(), self.G4.to_directed()) + with pytest.raises( + nx.NetworkXError, match="Graphs G1 and G2 are not of the same type." + ): + iso.is_isomorphic(self.G1.to_directed(), self.G1) diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py new file mode 100644 index 00000000..413dfaf3 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py @@ -0,0 +1,410 @@ +""" +Tests for VF2 isomorphism algorithm. +""" + +import importlib.resources +import os +import random +import struct + +import networkx as nx +from networkx.algorithms import isomorphism as iso + + +class TestWikipediaExample: + # Source: https://en.wikipedia.org/wiki/Graph_isomorphism + + # 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.GraphMatcher(g1, g2) + assert gm.is_isomorphic() + # Just testing some cases + assert gm.subgraph_is_monomorphic() + + mapping = sorted(gm.mapping.items()) + + # this mapping is only one of the possibilities + # so this test needs to be reconsidered + # isomap = [('a', 1), ('b', 6), ('c', 3), ('d', 8), + # ('g', 2), ('h', 5), ('i', 4), ('j', 7)] + # assert_equal(mapping, isomap) + + def test_subgraph(self): + g1 = nx.Graph() + g2 = nx.Graph() + g1.add_edges_from(self.g1edges) + g2.add_edges_from(self.g2edges) + g3 = g2.subgraph([1, 2, 3, 4]) + gm = iso.GraphMatcher(g1, g3) + assert gm.subgraph_is_isomorphic() + + def test_subgraph_mono(self): + g1 = nx.Graph() + g2 = nx.Graph() + g1.add_edges_from(self.g1edges) + g2.add_edges_from([[1, 2], [2, 3], [3, 4]]) + gm = iso.GraphMatcher(g1, g2) + assert gm.subgraph_is_monomorphic() + + +class TestVF2GraphDB: + # https://web.archive.org/web/20090303210205/http://amalfi.dis.unina.it/graph/db/ + + @staticmethod + def create_graph(filename): + """Creates a Graph instance from the filename.""" + + # The file is assumed to be in the format from the VF2 graph database. + # Each file is composed of 16-bit numbers (unsigned short int). + # So we will want to read 2 bytes at a time. + + # We can read the number as follows: + # number = struct.unpack('<H', file.read(2)) + # This says, expect the data in little-endian encoding + # as an unsigned short int and unpack 2 bytes from the file. + + fh = open(filename, mode="rb") + + # Grab the number of nodes. + # Node numeration is 0-based, so the first node has index 0. + nodes = struct.unpack("<H", fh.read(2))[0] + + graph = nx.Graph() + for from_node in range(nodes): + # Get the number of edges. + edges = struct.unpack("<H", fh.read(2))[0] + for edge in range(edges): + # Get the terminal node. + to_node = struct.unpack("<H", fh.read(2))[0] + graph.add_edge(from_node, to_node) + + fh.close() + return graph + + def test_graph(self): + head = importlib.resources.files("networkx.algorithms.isomorphism.tests") + g1 = self.create_graph(head / "iso_r01_s80.A99") + g2 = self.create_graph(head / "iso_r01_s80.B99") + gm = iso.GraphMatcher(g1, g2) + assert gm.is_isomorphic() + + def test_subgraph(self): + # A is the subgraph + # B is the full graph + head = importlib.resources.files("networkx.algorithms.isomorphism.tests") + subgraph = self.create_graph(head / "si2_b06_m200.A99") + graph = self.create_graph(head / "si2_b06_m200.B99") + gm = iso.GraphMatcher(graph, subgraph) + assert gm.subgraph_is_isomorphic() + # Just testing some cases + assert gm.subgraph_is_monomorphic() + + # There isn't a similar test implemented for subgraph monomorphism, + # feel free to create one. + + +class TestAtlas: + @classmethod + def setup_class(cls): + global atlas + from networkx.generators import atlas + + cls.GAG = atlas.graph_atlas_g() + + def test_graph_atlas(self): + # Atlas = nx.graph_atlas_g()[0:208] # 208, 6 nodes or less + Atlas = self.GAG[0:100] + alphabet = list(range(26)) + for graph in Atlas: + nlist = list(graph) + labels = alphabet[: len(nlist)] + for s in range(10): + random.shuffle(labels) + d = dict(zip(nlist, labels)) + relabel = nx.relabel_nodes(graph, d) + gm = iso.GraphMatcher(graph, relabel) + assert gm.is_isomorphic() + + +def test_multiedge(): + # Simple test for multigraphs + # Need something much more rigorous + edges = [ + (0, 1), + (1, 2), + (2, 3), + (3, 4), + (4, 5), + (5, 6), + (6, 7), + (7, 8), + (8, 9), + (9, 10), + (10, 11), + (10, 11), + (11, 12), + (11, 12), + (12, 13), + (12, 13), + (13, 14), + (13, 14), + (14, 15), + (14, 15), + (15, 16), + (15, 16), + (16, 17), + (16, 17), + (17, 18), + (17, 18), + (18, 19), + (18, 19), + (19, 0), + (19, 0), + ] + nodes = list(range(20)) + + for g1 in [nx.MultiGraph(), nx.MultiDiGraph()]: + g1.add_edges_from(edges) + for _ in range(10): + new_nodes = list(nodes) + random.shuffle(new_nodes) + d = dict(zip(nodes, new_nodes)) + g2 = nx.relabel_nodes(g1, d) + if not g1.is_directed(): + gm = iso.GraphMatcher(g1, g2) + else: + gm = iso.DiGraphMatcher(g1, g2) + assert gm.is_isomorphic() + # Testing if monomorphism works in multigraphs + assert gm.subgraph_is_monomorphic() + + +def test_selfloop(): + # Simple test for graphs with selfloops + edges = [ + (0, 1), + (0, 2), + (1, 2), + (1, 3), + (2, 2), + (2, 4), + (3, 1), + (3, 2), + (4, 2), + (4, 5), + (5, 4), + ] + nodes = list(range(6)) + + for g1 in [nx.Graph(), nx.DiGraph()]: + g1.add_edges_from(edges) + for _ in range(100): + new_nodes = list(nodes) + random.shuffle(new_nodes) + d = dict(zip(nodes, new_nodes)) + g2 = nx.relabel_nodes(g1, d) + if not g1.is_directed(): + gm = iso.GraphMatcher(g1, g2) + else: + gm = iso.DiGraphMatcher(g1, g2) + assert gm.is_isomorphic() + + +def test_selfloop_mono(): + # Simple test for graphs with selfloops + edges0 = [ + (0, 1), + (0, 2), + (1, 2), + (1, 3), + (2, 4), + (3, 1), + (3, 2), + (4, 2), + (4, 5), + (5, 4), + ] + edges = edges0 + [(2, 2)] + nodes = list(range(6)) + + for g1 in [nx.Graph(), nx.DiGraph()]: + g1.add_edges_from(edges) + for _ in range(100): + new_nodes = list(nodes) + random.shuffle(new_nodes) + d = dict(zip(nodes, new_nodes)) + g2 = nx.relabel_nodes(g1, d) + g2.remove_edges_from(nx.selfloop_edges(g2)) + if not g1.is_directed(): + gm = iso.GraphMatcher(g2, g1) + else: + gm = iso.DiGraphMatcher(g2, g1) + assert not gm.subgraph_is_monomorphic() + + +def test_isomorphism_iter1(): + # As described in: + # http://groups.google.com/group/networkx-discuss/browse_thread/thread/2ff65c67f5e3b99f/d674544ebea359bb?fwc=1 + g1 = nx.DiGraph() + g2 = nx.DiGraph() + g3 = nx.DiGraph() + g1.add_edge("A", "B") + g1.add_edge("B", "C") + g2.add_edge("Y", "Z") + g3.add_edge("Z", "Y") + gm12 = iso.DiGraphMatcher(g1, g2) + gm13 = iso.DiGraphMatcher(g1, g3) + x = list(gm12.subgraph_isomorphisms_iter()) + y = list(gm13.subgraph_isomorphisms_iter()) + assert {"A": "Y", "B": "Z"} in x + assert {"B": "Y", "C": "Z"} in x + assert {"A": "Z", "B": "Y"} in y + assert {"B": "Z", "C": "Y"} in y + assert len(x) == len(y) + assert len(x) == 2 + + +def test_monomorphism_iter1(): + g1 = nx.DiGraph() + g2 = nx.DiGraph() + g1.add_edge("A", "B") + g1.add_edge("B", "C") + g1.add_edge("C", "A") + g2.add_edge("X", "Y") + g2.add_edge("Y", "Z") + gm12 = iso.DiGraphMatcher(g1, g2) + x = list(gm12.subgraph_monomorphisms_iter()) + assert {"A": "X", "B": "Y", "C": "Z"} in x + assert {"A": "Y", "B": "Z", "C": "X"} in x + assert {"A": "Z", "B": "X", "C": "Y"} in x + assert len(x) == 3 + gm21 = iso.DiGraphMatcher(g2, g1) + # Check if StopIteration exception returns False + assert not gm21.subgraph_is_monomorphic() + + +def test_isomorphism_iter2(): + # Path + for L in range(2, 10): + g1 = nx.path_graph(L) + gm = iso.GraphMatcher(g1, g1) + s = len(list(gm.isomorphisms_iter())) + assert s == 2 + # Cycle + for L in range(3, 10): + g1 = nx.cycle_graph(L) + gm = iso.GraphMatcher(g1, g1) + s = len(list(gm.isomorphisms_iter())) + assert s == 2 * L + + +def test_multiple(): + # Verify that we can use the graph matcher multiple times + edges = [("A", "B"), ("B", "A"), ("B", "C")] + for g1, g2 in [(nx.Graph(), nx.Graph()), (nx.DiGraph(), nx.DiGraph())]: + g1.add_edges_from(edges) + g2.add_edges_from(edges) + g3 = nx.subgraph(g2, ["A", "B"]) + if not g1.is_directed(): + gmA = iso.GraphMatcher(g1, g2) + gmB = iso.GraphMatcher(g1, g3) + else: + gmA = iso.DiGraphMatcher(g1, g2) + gmB = iso.DiGraphMatcher(g1, g3) + assert gmA.is_isomorphic() + g2.remove_node("C") + if not g1.is_directed(): + gmA = iso.GraphMatcher(g1, g2) + else: + gmA = iso.DiGraphMatcher(g1, g2) + assert gmA.subgraph_is_isomorphic() + assert gmB.subgraph_is_isomorphic() + assert gmA.subgraph_is_monomorphic() + assert gmB.subgraph_is_monomorphic() + + +# for m in [gmB.mapping, gmB.mapping]: +# assert_true(m['A'] == 'A') +# assert_true(m['B'] == 'B') +# assert_true('C' not in m) + + +def test_noncomparable_nodes(): + node1 = object() + node2 = object() + node3 = object() + + # Graph + G = nx.path_graph([node1, node2, node3]) + gm = iso.GraphMatcher(G, G) + assert gm.is_isomorphic() + # Just testing some cases + assert gm.subgraph_is_monomorphic() + + # DiGraph + G = nx.path_graph([node1, node2, node3], create_using=nx.DiGraph) + H = nx.path_graph([node3, node2, node1], create_using=nx.DiGraph) + dgm = iso.DiGraphMatcher(G, H) + assert dgm.is_isomorphic() + # Just testing some cases + assert gm.subgraph_is_monomorphic() + + +def test_monomorphism_edge_match(): + G = nx.DiGraph() + G.add_node(1) + G.add_node(2) + G.add_edge(1, 2, label="A") + G.add_edge(2, 1, label="B") + G.add_edge(2, 2, label="C") + + SG = nx.DiGraph() + SG.add_node(5) + SG.add_node(6) + SG.add_edge(5, 6, label="A") + + gm = iso.DiGraphMatcher(G, SG, edge_match=iso.categorical_edge_match("label", None)) + assert gm.subgraph_is_monomorphic() + + +def test_isomorphvf2pp_multidigraphs(): + g = nx.MultiDiGraph({0: [1, 1, 2, 2, 3], 1: [2, 3, 3], 2: [3]}) + h = nx.MultiDiGraph({0: [1, 1, 2, 2, 3], 1: [2, 3, 3], 3: [2]}) + assert not (nx.vf2pp_is_isomorphic(g, h)) diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_match_helpers.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_match_helpers.py new file mode 100644 index 00000000..4d70347f --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_match_helpers.py @@ -0,0 +1,64 @@ +from operator import eq + +import networkx as nx +from networkx.algorithms import isomorphism as iso + + +def test_categorical_node_match(): + nm = iso.categorical_node_match(["x", "y", "z"], [None] * 3) + assert nm({"x": 1, "y": 2, "z": 3}, {"x": 1, "y": 2, "z": 3}) + assert not nm({"x": 1, "y": 2, "z": 2}, {"x": 1, "y": 2, "z": 1}) + + +class TestGenericMultiEdgeMatch: + def setup_method(self): + self.G1 = nx.MultiDiGraph() + self.G2 = nx.MultiDiGraph() + self.G3 = nx.MultiDiGraph() + self.G4 = nx.MultiDiGraph() + attr_dict1 = {"id": "edge1", "minFlow": 0, "maxFlow": 10} + attr_dict2 = {"id": "edge2", "minFlow": -3, "maxFlow": 7} + attr_dict3 = {"id": "edge3", "minFlow": 13, "maxFlow": 117} + attr_dict4 = {"id": "edge4", "minFlow": 13, "maxFlow": 117} + attr_dict5 = {"id": "edge5", "minFlow": 8, "maxFlow": 12} + attr_dict6 = {"id": "edge6", "minFlow": 8, "maxFlow": 12} + for attr_dict in [ + attr_dict1, + attr_dict2, + attr_dict3, + attr_dict4, + attr_dict5, + attr_dict6, + ]: + self.G1.add_edge(1, 2, **attr_dict) + for attr_dict in [ + attr_dict5, + attr_dict3, + attr_dict6, + attr_dict1, + attr_dict4, + attr_dict2, + ]: + self.G2.add_edge(2, 3, **attr_dict) + for attr_dict in [attr_dict3, attr_dict5]: + self.G3.add_edge(3, 4, **attr_dict) + for attr_dict in [attr_dict6, attr_dict4]: + self.G4.add_edge(4, 5, **attr_dict) + + def test_generic_multiedge_match(self): + full_match = iso.generic_multiedge_match( + ["id", "flowMin", "flowMax"], [None] * 3, [eq] * 3 + ) + flow_match = iso.generic_multiedge_match( + ["flowMin", "flowMax"], [None] * 2, [eq] * 2 + ) + min_flow_match = iso.generic_multiedge_match("flowMin", None, eq) + id_match = iso.generic_multiedge_match("id", None, eq) + assert flow_match(self.G1[1][2], self.G2[2][3]) + assert min_flow_match(self.G1[1][2], self.G2[2][3]) + assert id_match(self.G1[1][2], self.G2[2][3]) + assert full_match(self.G1[1][2], self.G2[2][3]) + assert flow_match(self.G3[3][4], self.G4[4][5]) + assert min_flow_match(self.G3[3][4], self.G4[4][5]) + assert not id_match(self.G3[3][4], self.G4[4][5]) + assert not full_match(self.G3[3][4], self.G4[4][5]) diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_temporalisomorphvf2.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_temporalisomorphvf2.py new file mode 100644 index 00000000..1fe70a42 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_temporalisomorphvf2.py @@ -0,0 +1,212 @@ +""" +Tests for the temporal aspect of the Temporal VF2 isomorphism algorithm. +""" + +from datetime import date, datetime, timedelta + +import networkx as nx +from networkx.algorithms import isomorphism as iso + + +def provide_g1_edgelist(): + return [(0, 1), (0, 2), (1, 2), (2, 4), (1, 3), (3, 4), (4, 5)] + + +def put_same_time(G, att_name): + for e in G.edges(data=True): + e[2][att_name] = date(2015, 1, 1) + return G + + +def put_same_datetime(G, att_name): + for e in G.edges(data=True): + e[2][att_name] = datetime(2015, 1, 1) + return G + + +def put_sequence_time(G, att_name): + current_date = date(2015, 1, 1) + for e in G.edges(data=True): + current_date += timedelta(days=1) + e[2][att_name] = current_date + return G + + +def put_time_config_0(G, att_name): + G[0][1][att_name] = date(2015, 1, 2) + G[0][2][att_name] = date(2015, 1, 2) + G[1][2][att_name] = date(2015, 1, 3) + G[1][3][att_name] = date(2015, 1, 1) + G[2][4][att_name] = date(2015, 1, 1) + G[3][4][att_name] = date(2015, 1, 3) + G[4][5][att_name] = date(2015, 1, 3) + return G + + +def put_time_config_1(G, att_name): + G[0][1][att_name] = date(2015, 1, 2) + G[0][2][att_name] = date(2015, 1, 1) + G[1][2][att_name] = date(2015, 1, 3) + G[1][3][att_name] = date(2015, 1, 1) + G[2][4][att_name] = date(2015, 1, 2) + G[3][4][att_name] = date(2015, 1, 4) + G[4][5][att_name] = date(2015, 1, 3) + return G + + +def put_time_config_2(G, att_name): + G[0][1][att_name] = date(2015, 1, 1) + G[0][2][att_name] = date(2015, 1, 1) + G[1][2][att_name] = date(2015, 1, 3) + G[1][3][att_name] = date(2015, 1, 2) + G[2][4][att_name] = date(2015, 1, 2) + G[3][4][att_name] = date(2015, 1, 3) + G[4][5][att_name] = date(2015, 1, 2) + return G + + +class TestTimeRespectingGraphMatcher: + """ + A test class for the undirected temporal graph matcher. + """ + + def provide_g1_topology(self): + G1 = nx.Graph() + G1.add_edges_from(provide_g1_edgelist()) + return G1 + + def provide_g2_path_3edges(self): + G2 = nx.Graph() + G2.add_edges_from([(0, 1), (1, 2), (2, 3)]) + return G2 + + def test_timdelta_zero_timeRespecting_returnsTrue(self): + G1 = self.provide_g1_topology() + temporal_name = "date" + G1 = put_same_time(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta() + gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d) + assert gm.subgraph_is_isomorphic() + + def test_timdelta_zero_datetime_timeRespecting_returnsTrue(self): + G1 = self.provide_g1_topology() + temporal_name = "date" + G1 = put_same_datetime(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta() + gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d) + assert gm.subgraph_is_isomorphic() + + def test_attNameStrange_timdelta_zero_timeRespecting_returnsTrue(self): + G1 = self.provide_g1_topology() + temporal_name = "strange_name" + G1 = put_same_time(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta() + gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d) + assert gm.subgraph_is_isomorphic() + + def test_notTimeRespecting_returnsFalse(self): + G1 = self.provide_g1_topology() + temporal_name = "date" + G1 = put_sequence_time(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta() + gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d) + assert not gm.subgraph_is_isomorphic() + + def test_timdelta_one_config0_returns_no_embeddings(self): + G1 = self.provide_g1_topology() + temporal_name = "date" + G1 = put_time_config_0(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta(days=1) + gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d) + count_match = len(list(gm.subgraph_isomorphisms_iter())) + assert count_match == 0 + + def test_timdelta_one_config1_returns_four_embedding(self): + G1 = self.provide_g1_topology() + temporal_name = "date" + G1 = put_time_config_1(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta(days=1) + gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d) + count_match = len(list(gm.subgraph_isomorphisms_iter())) + assert count_match == 4 + + def test_timdelta_one_config2_returns_ten_embeddings(self): + G1 = self.provide_g1_topology() + temporal_name = "date" + G1 = put_time_config_2(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta(days=1) + gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d) + L = list(gm.subgraph_isomorphisms_iter()) + count_match = len(list(gm.subgraph_isomorphisms_iter())) + assert count_match == 10 + + +class TestDiTimeRespectingGraphMatcher: + """ + A test class for the directed time-respecting graph matcher. + """ + + def provide_g1_topology(self): + G1 = nx.DiGraph() + G1.add_edges_from(provide_g1_edgelist()) + return G1 + + def provide_g2_path_3edges(self): + G2 = nx.DiGraph() + G2.add_edges_from([(0, 1), (1, 2), (2, 3)]) + return G2 + + def test_timdelta_zero_same_dates_returns_true(self): + G1 = self.provide_g1_topology() + temporal_name = "date" + G1 = put_same_time(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta() + gm = iso.TimeRespectingDiGraphMatcher(G1, G2, temporal_name, d) + assert gm.subgraph_is_isomorphic() + + def test_attNameStrange_timdelta_zero_same_dates_returns_true(self): + G1 = self.provide_g1_topology() + temporal_name = "strange" + G1 = put_same_time(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta() + gm = iso.TimeRespectingDiGraphMatcher(G1, G2, temporal_name, d) + assert gm.subgraph_is_isomorphic() + + def test_timdelta_one_config0_returns_no_embeddings(self): + G1 = self.provide_g1_topology() + temporal_name = "date" + G1 = put_time_config_0(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta(days=1) + gm = iso.TimeRespectingDiGraphMatcher(G1, G2, temporal_name, d) + count_match = len(list(gm.subgraph_isomorphisms_iter())) + assert count_match == 0 + + def test_timdelta_one_config1_returns_one_embedding(self): + G1 = self.provide_g1_topology() + temporal_name = "date" + G1 = put_time_config_1(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta(days=1) + gm = iso.TimeRespectingDiGraphMatcher(G1, G2, temporal_name, d) + count_match = len(list(gm.subgraph_isomorphisms_iter())) + assert count_match == 1 + + def test_timdelta_one_config2_returns_two_embeddings(self): + G1 = self.provide_g1_topology() + temporal_name = "date" + G1 = put_time_config_2(G1, temporal_name) + G2 = self.provide_g2_path_3edges() + d = timedelta(days=1) + gm = iso.TimeRespectingDiGraphMatcher(G1, G2, temporal_name, d) + count_match = len(list(gm.subgraph_isomorphisms_iter())) + assert count_match == 2 diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_tree_isomorphism.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_tree_isomorphism.py new file mode 100644 index 00000000..fa1ab9bb --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_tree_isomorphism.py @@ -0,0 +1,292 @@ +import random +import time + +import pytest + +import networkx as nx +from networkx.algorithms.isomorphism.tree_isomorphism import ( + rooted_tree_isomorphism, + tree_isomorphism, +) +from networkx.classes.function import is_directed + + +@pytest.mark.parametrize("graph_constructor", (nx.DiGraph, nx.MultiGraph)) +def test_tree_isomorphism_raises_on_directed_and_multigraphs(graph_constructor): + t1 = graph_constructor([(0, 1)]) + t2 = graph_constructor([(1, 2)]) + with pytest.raises(nx.NetworkXNotImplemented): + nx.isomorphism.tree_isomorphism(t1, t2) + + +# have this work for graph +# given two trees (either the directed or undirected) +# transform t2 according to the isomorphism +# and confirm it is identical to t1 +# randomize the order of the edges when constructing +def check_isomorphism(t1, t2, isomorphism): + # get the name of t1, given the name in t2 + mapping = {v2: v1 for (v1, v2) in isomorphism} + + # these should be the same + d1 = is_directed(t1) + d2 = is_directed(t2) + assert d1 == d2 + + edges_1 = [] + for u, v in t1.edges(): + if d1: + edges_1.append((u, v)) + else: + # if not directed, then need to + # put the edge in a consistent direction + if u < v: + edges_1.append((u, v)) + else: + edges_1.append((v, u)) + + edges_2 = [] + for u, v in t2.edges(): + # translate to names for t1 + u = mapping[u] + v = mapping[v] + if d2: + edges_2.append((u, v)) + else: + if u < v: + edges_2.append((u, v)) + else: + edges_2.append((v, u)) + + return sorted(edges_1) == sorted(edges_2) + + +def test_hardcoded(): + print("hardcoded test") + + # define a test problem + edges_1 = [ + ("a", "b"), + ("a", "c"), + ("a", "d"), + ("b", "e"), + ("b", "f"), + ("e", "j"), + ("e", "k"), + ("c", "g"), + ("c", "h"), + ("g", "m"), + ("d", "i"), + ("f", "l"), + ] + + edges_2 = [ + ("v", "y"), + ("v", "z"), + ("u", "x"), + ("q", "u"), + ("q", "v"), + ("p", "t"), + ("n", "p"), + ("n", "q"), + ("n", "o"), + ("o", "r"), + ("o", "s"), + ("s", "w"), + ] + + # there are two possible correct isomorphisms + # it currently returns isomorphism1 + # but the second is also correct + isomorphism1 = [ + ("a", "n"), + ("b", "q"), + ("c", "o"), + ("d", "p"), + ("e", "v"), + ("f", "u"), + ("g", "s"), + ("h", "r"), + ("i", "t"), + ("j", "y"), + ("k", "z"), + ("l", "x"), + ("m", "w"), + ] + + # could swap y and z + isomorphism2 = [ + ("a", "n"), + ("b", "q"), + ("c", "o"), + ("d", "p"), + ("e", "v"), + ("f", "u"), + ("g", "s"), + ("h", "r"), + ("i", "t"), + ("j", "z"), + ("k", "y"), + ("l", "x"), + ("m", "w"), + ] + + t1 = nx.Graph() + t1.add_edges_from(edges_1) + root1 = "a" + + t2 = nx.Graph() + t2.add_edges_from(edges_2) + root2 = "n" + + isomorphism = sorted(rooted_tree_isomorphism(t1, root1, t2, root2)) + + # is correct by hand + assert isomorphism in (isomorphism1, isomorphism2) + + # check algorithmically + assert check_isomorphism(t1, t2, isomorphism) + + # try again as digraph + t1 = nx.DiGraph() + t1.add_edges_from(edges_1) + root1 = "a" + + t2 = nx.DiGraph() + t2.add_edges_from(edges_2) + root2 = "n" + + isomorphism = sorted(rooted_tree_isomorphism(t1, root1, t2, root2)) + + # is correct by hand + assert isomorphism in (isomorphism1, isomorphism2) + + # check algorithmically + assert check_isomorphism(t1, t2, isomorphism) + + +# randomly swap a tuple (a,b) +def random_swap(t): + (a, b) = t + if random.randint(0, 1) == 1: + return (a, b) + else: + return (b, a) + + +# given a tree t1, create a new tree t2 +# that is isomorphic to t1, with a known isomorphism +# and test that our algorithm found the right one +def positive_single_tree(t1): + assert nx.is_tree(t1) + + nodes1 = list(t1.nodes()) + # get a random permutation of this + nodes2 = nodes1.copy() + random.shuffle(nodes2) + + # this is one isomorphism, however they may be multiple + # so we don't necessarily get this one back + someisomorphism = list(zip(nodes1, nodes2)) + + # map from old to new + map1to2 = dict(someisomorphism) + + # get the edges with the transformed names + edges2 = [random_swap((map1to2[u], map1to2[v])) for (u, v) in t1.edges()] + # randomly permute, to ensure we're not relying on edge order somehow + random.shuffle(edges2) + + # so t2 is isomorphic to t1 + t2 = nx.Graph() + t2.add_edges_from(edges2) + + # lets call our code to see if t1 and t2 are isomorphic + isomorphism = tree_isomorphism(t1, t2) + + # make sure we got a correct solution + # although not necessarily someisomorphism + assert len(isomorphism) > 0 + assert check_isomorphism(t1, t2, isomorphism) + + +# run positive_single_tree over all the +# non-isomorphic trees for k from 4 to maxk +# k = 4 is the first level that has more than 1 non-isomorphic tree +# k = 13 takes about 2.86 seconds to run on my laptop +# larger values run slow down significantly +# as the number of trees grows rapidly +def test_positive(maxk=14): + print("positive test") + + for k in range(2, maxk + 1): + start_time = time.time() + trial = 0 + for t in nx.nonisomorphic_trees(k): + positive_single_tree(t) + trial += 1 + print(k, trial, time.time() - start_time) + + +# test the trivial case of a single node in each tree +# note that nonisomorphic_trees doesn't work for k = 1 +def test_trivial(): + print("trivial test") + + # back to an undirected graph + t1 = nx.Graph() + t1.add_node("a") + root1 = "a" + + t2 = nx.Graph() + t2.add_node("n") + root2 = "n" + + isomorphism = rooted_tree_isomorphism(t1, root1, t2, root2) + + assert isomorphism == [("a", "n")] + + assert check_isomorphism(t1, t2, isomorphism) + + +# test another trivial case where the two graphs have +# different numbers of nodes +def test_trivial_2(): + print("trivial test 2") + + edges_1 = [("a", "b"), ("a", "c")] + + edges_2 = [("v", "y")] + + t1 = nx.Graph() + t1.add_edges_from(edges_1) + + t2 = nx.Graph() + t2.add_edges_from(edges_2) + + isomorphism = tree_isomorphism(t1, t2) + + # they cannot be isomorphic, + # since they have different numbers of nodes + assert isomorphism == [] + + +# the function nonisomorphic_trees generates all the non-isomorphic +# trees of a given size. Take each pair of these and verify that +# they are not isomorphic +# k = 4 is the first level that has more than 1 non-isomorphic tree +# k = 11 takes about 4.76 seconds to run on my laptop +# larger values run slow down significantly +# as the number of trees grows rapidly +def test_negative(maxk=11): + print("negative test") + + for k in range(4, maxk + 1): + test_trees = list(nx.nonisomorphic_trees(k)) + start_time = time.time() + trial = 0 + for i in range(len(test_trees) - 1): + for j in range(i + 1, len(test_trees)): + trial += 1 + assert tree_isomorphism(test_trees[i], test_trees[j]) == [] + print(k, trial, time.time() - start_time) diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_vf2pp.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_vf2pp.py new file mode 100644 index 00000000..5f3fb901 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_vf2pp.py @@ -0,0 +1,1608 @@ +import itertools as it + +import pytest + +import networkx as nx +from networkx import vf2pp_is_isomorphic, vf2pp_isomorphism + +labels_same = ["blue"] + +labels_many = [ + "white", + "red", + "blue", + "green", + "orange", + "black", + "purple", + "yellow", + "brown", + "cyan", + "solarized", + "pink", + "none", +] + + +class TestPreCheck: + def test_first_graph_empty(self): + G1 = nx.Graph() + G2 = nx.Graph([(0, 1), (1, 2)]) + assert not vf2pp_is_isomorphic(G1, G2) + + def test_second_graph_empty(self): + G1 = nx.Graph([(0, 1), (1, 2)]) + G2 = nx.Graph() + assert not vf2pp_is_isomorphic(G1, G2) + + def test_different_order1(self): + G1 = nx.path_graph(5) + G2 = nx.path_graph(6) + assert not vf2pp_is_isomorphic(G1, G2) + + def test_different_order2(self): + G1 = nx.barbell_graph(100, 20) + G2 = nx.barbell_graph(101, 20) + assert not vf2pp_is_isomorphic(G1, G2) + + def test_different_order3(self): + G1 = nx.complete_graph(7) + G2 = nx.complete_graph(8) + assert not vf2pp_is_isomorphic(G1, G2) + + def test_different_degree_sequences1(self): + G1 = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3), (0, 4)]) + G2 = nx.Graph([(0, 1), (0, 2), (1, 2), (1, 3), (0, 4), (2, 5)]) + assert not vf2pp_is_isomorphic(G1, G2) + + G2.remove_node(3) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(["a"]))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle("a"))), "label") + + assert vf2pp_is_isomorphic(G1, G2) + + def test_different_degree_sequences2(self): + G1 = nx.Graph( + [ + (0, 1), + (1, 2), + (0, 2), + (2, 3), + (3, 4), + (4, 5), + (5, 6), + (6, 3), + (4, 7), + (7, 8), + (8, 3), + ] + ) + G2 = G1.copy() + G2.add_edge(8, 0) + assert not vf2pp_is_isomorphic(G1, G2) + + G1.add_edge(6, 1) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(["a"]))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle("a"))), "label") + + assert vf2pp_is_isomorphic(G1, G2) + + def test_different_degree_sequences3(self): + G1 = nx.Graph([(0, 1), (0, 2), (1, 2), (2, 3), (2, 4), (3, 4), (2, 5), (2, 6)]) + G2 = nx.Graph( + [(0, 1), (0, 6), (0, 2), (1, 2), (2, 3), (2, 4), (3, 4), (2, 5), (2, 6)] + ) + assert not vf2pp_is_isomorphic(G1, G2) + + G1.add_edge(3, 5) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(["a"]))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle("a"))), "label") + + assert vf2pp_is_isomorphic(G1, G2) + + def test_label_distribution(self): + G1 = nx.Graph([(0, 1), (0, 2), (1, 2), (2, 3), (2, 4), (3, 4), (2, 5), (2, 6)]) + G2 = nx.Graph([(0, 1), (0, 2), (1, 2), (2, 3), (2, 4), (3, 4), (2, 5), (2, 6)]) + + colors1 = ["blue", "blue", "blue", "yellow", "black", "purple", "purple"] + colors2 = ["blue", "blue", "yellow", "yellow", "black", "purple", "purple"] + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(colors1[::-1]))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(colors2[::-1]))), "label") + + assert not vf2pp_is_isomorphic(G1, G2, node_label="label") + G2.nodes[3]["label"] = "blue" + assert vf2pp_is_isomorphic(G1, G2, node_label="label") + + +class TestAllGraphTypesEdgeCases: + @pytest.mark.parametrize("graph_type", (nx.Graph, nx.MultiGraph, nx.DiGraph)) + def test_both_graphs_empty(self, graph_type): + G = graph_type() + H = graph_type() + assert vf2pp_isomorphism(G, H) is None + + G.add_node(0) + + assert vf2pp_isomorphism(G, H) is None + assert vf2pp_isomorphism(H, G) is None + + H.add_node(0) + assert vf2pp_isomorphism(G, H) == {0: 0} + + @pytest.mark.parametrize("graph_type", (nx.Graph, nx.MultiGraph, nx.DiGraph)) + def test_first_graph_empty(self, graph_type): + G = graph_type() + H = graph_type([(0, 1)]) + assert vf2pp_isomorphism(G, H) is None + + @pytest.mark.parametrize("graph_type", (nx.Graph, nx.MultiGraph, nx.DiGraph)) + def test_second_graph_empty(self, graph_type): + G = graph_type([(0, 1)]) + H = graph_type() + assert vf2pp_isomorphism(G, H) is None + + +class TestGraphISOVF2pp: + def test_custom_graph1_same_labels(self): + G1 = nx.Graph() + + mapped = {1: "A", 2: "B", 3: "C", 4: "D", 5: "Z", 6: "E"} + edges1 = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 6), (3, 4), (5, 1), (5, 2)] + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Add edge making G1 symmetrical + G1.add_edge(3, 7) + G1.nodes[7]["label"] = "blue" + assert vf2pp_isomorphism(G1, G2, node_label="label") is None + + # Make G2 isomorphic to G1 + G2.add_edges_from([(mapped[3], "X"), (mapped[6], mapped[5])]) + G1.add_edge(4, 7) + G2.nodes["X"]["label"] = "blue" + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Re-structure maintaining isomorphism + G1.remove_edges_from([(1, 4), (1, 3)]) + G2.remove_edges_from([(mapped[1], mapped[5]), (mapped[1], mapped[2])]) + assert vf2pp_isomorphism(G1, G2, node_label="label") + + def test_custom_graph1_different_labels(self): + G1 = nx.Graph() + + mapped = {1: "A", 2: "B", 3: "C", 4: "D", 5: "Z", 6: "E"} + edges1 = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 6), (3, 4), (5, 1), (5, 2)] + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip([mapped[n] for n in G1], it.cycle(labels_many))), + "label", + ) + assert vf2pp_isomorphism(G1, G2, node_label="label") == mapped + + def test_custom_graph2_same_labels(self): + G1 = nx.Graph() + + mapped = {1: "A", 2: "C", 3: "D", 4: "E", 5: "G", 7: "B", 6: "F"} + edges1 = [(1, 2), (1, 5), (5, 6), (2, 3), (2, 4), (3, 4), (4, 5), (2, 7)] + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Obtain two isomorphic subgraphs from the graph + G2.remove_edge(mapped[1], mapped[2]) + G2.add_edge(mapped[1], mapped[4]) + H1 = nx.Graph(G1.subgraph([2, 3, 4, 7])) + H2 = nx.Graph(G2.subgraph([mapped[1], mapped[4], mapped[5], mapped[6]])) + assert vf2pp_isomorphism(H1, H2, node_label="label") + + # Add edges maintaining isomorphism + H1.add_edges_from([(3, 7), (4, 7)]) + H2.add_edges_from([(mapped[1], mapped[6]), (mapped[4], mapped[6])]) + assert vf2pp_isomorphism(H1, H2, node_label="label") + + def test_custom_graph2_different_labels(self): + G1 = nx.Graph() + + mapped = {1: "A", 2: "C", 3: "D", 4: "E", 5: "G", 7: "B", 6: "F"} + edges1 = [(1, 2), (1, 5), (5, 6), (2, 3), (2, 4), (3, 4), (4, 5), (2, 7)] + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip([mapped[n] for n in G1], it.cycle(labels_many))), + "label", + ) + + # Adding new nodes + G1.add_node(0) + G2.add_node("Z") + G1.nodes[0]["label"] = G1.nodes[1]["label"] + G2.nodes["Z"]["label"] = G1.nodes[1]["label"] + mapped.update({0: "Z"}) + + assert vf2pp_isomorphism(G1, G2, node_label="label") == mapped + + # Change the color of one of the nodes + G2.nodes["Z"]["label"] = G1.nodes[2]["label"] + assert vf2pp_isomorphism(G1, G2, node_label="label") is None + + # Add an extra edge + G1.nodes[0]["label"] = "blue" + G2.nodes["Z"]["label"] = "blue" + G1.add_edge(0, 1) + + assert vf2pp_isomorphism(G1, G2, node_label="label") is None + + # Add extra edge to both + G2.add_edge("Z", "A") + assert vf2pp_isomorphism(G1, G2, node_label="label") == mapped + + def test_custom_graph3_same_labels(self): + G1 = nx.Graph() + + mapped = {1: 9, 2: 8, 3: 7, 4: 6, 5: 3, 8: 5, 9: 4, 7: 1, 6: 2} + edges1 = [ + (1, 2), + (1, 3), + (2, 3), + (3, 4), + (4, 5), + (4, 7), + (4, 9), + (5, 8), + (8, 9), + (5, 6), + (6, 7), + (5, 2), + ] + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Connect nodes maintaining symmetry + G1.add_edges_from([(6, 9), (7, 8)]) + G2.add_edges_from([(mapped[6], mapped[8]), (mapped[7], mapped[9])]) + assert vf2pp_isomorphism(G1, G2, node_label="label") is None + + # Make isomorphic + G1.add_edges_from([(6, 8), (7, 9)]) + G2.add_edges_from([(mapped[6], mapped[9]), (mapped[7], mapped[8])]) + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Connect more nodes + G1.add_edges_from([(2, 7), (3, 6)]) + G2.add_edges_from([(mapped[2], mapped[7]), (mapped[3], mapped[6])]) + G1.add_node(10) + G2.add_node("Z") + G1.nodes[10]["label"] = "blue" + G2.nodes["Z"]["label"] = "blue" + + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Connect the newly added node, to opposite sides of the graph + G1.add_edges_from([(10, 1), (10, 5), (10, 8)]) + G2.add_edges_from([("Z", mapped[1]), ("Z", mapped[4]), ("Z", mapped[9])]) + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Get two subgraphs that are not isomorphic but are easy to make + H1 = nx.Graph(G1.subgraph([2, 3, 4, 5, 6, 7, 10])) + H2 = nx.Graph( + G2.subgraph( + [mapped[4], mapped[5], mapped[6], mapped[7], mapped[8], mapped[9], "Z"] + ) + ) + assert vf2pp_isomorphism(H1, H2, node_label="label") is None + + # Restructure both to make them isomorphic + H1.add_edges_from([(10, 2), (10, 6), (3, 6), (2, 7), (2, 6), (3, 7)]) + H2.add_edges_from( + [("Z", mapped[7]), (mapped[6], mapped[9]), (mapped[7], mapped[8])] + ) + assert vf2pp_isomorphism(H1, H2, node_label="label") + + # Add edges with opposite direction in each Graph + H1.add_edge(3, 5) + H2.add_edge(mapped[5], mapped[7]) + assert vf2pp_isomorphism(H1, H2, node_label="label") is None + + def test_custom_graph3_different_labels(self): + G1 = nx.Graph() + + mapped = {1: 9, 2: 8, 3: 7, 4: 6, 5: 3, 8: 5, 9: 4, 7: 1, 6: 2} + edges1 = [ + (1, 2), + (1, 3), + (2, 3), + (3, 4), + (4, 5), + (4, 7), + (4, 9), + (5, 8), + (8, 9), + (5, 6), + (6, 7), + (5, 2), + ] + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip([mapped[n] for n in G1], it.cycle(labels_many))), + "label", + ) + assert vf2pp_isomorphism(G1, G2, node_label="label") == mapped + + # Add extra edge to G1 + G1.add_edge(1, 7) + assert vf2pp_isomorphism(G1, G2, node_label="label") is None + + # Compensate in G2 + G2.add_edge(9, 1) + assert vf2pp_isomorphism(G1, G2, node_label="label") == mapped + + # Add extra node + G1.add_node("A") + G2.add_node("K") + G1.nodes["A"]["label"] = "green" + G2.nodes["K"]["label"] = "green" + mapped.update({"A": "K"}) + + assert vf2pp_isomorphism(G1, G2, node_label="label") == mapped + + # Connect A to one side of G1 and K to the opposite + G1.add_edge("A", 6) + G2.add_edge("K", 5) + assert vf2pp_isomorphism(G1, G2, node_label="label") is None + + # Make the graphs symmetrical + G1.add_edge(1, 5) + G1.add_edge(2, 9) + G2.add_edge(9, 3) + G2.add_edge(8, 4) + assert vf2pp_isomorphism(G1, G2, node_label="label") is None + + # Assign same colors so the two opposite sides are identical + for node in G1.nodes(): + color = "red" + G1.nodes[node]["label"] = color + G2.nodes[mapped[node]]["label"] = color + + assert vf2pp_isomorphism(G1, G2, node_label="label") + + def test_custom_graph4_different_labels(self): + G1 = nx.Graph() + edges1 = [ + (1, 2), + (2, 3), + (3, 8), + (3, 4), + (4, 5), + (4, 6), + (3, 6), + (8, 7), + (8, 9), + (5, 9), + (10, 11), + (11, 12), + (12, 13), + (11, 13), + ] + + mapped = { + 1: "n", + 2: "m", + 3: "l", + 4: "j", + 5: "k", + 6: "i", + 7: "g", + 8: "h", + 9: "f", + 10: "b", + 11: "a", + 12: "d", + 13: "e", + } + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip([mapped[n] for n in G1], it.cycle(labels_many))), + "label", + ) + assert vf2pp_isomorphism(G1, G2, node_label="label") == mapped + + def test_custom_graph4_same_labels(self): + G1 = nx.Graph() + edges1 = [ + (1, 2), + (2, 3), + (3, 8), + (3, 4), + (4, 5), + (4, 6), + (3, 6), + (8, 7), + (8, 9), + (5, 9), + (10, 11), + (11, 12), + (12, 13), + (11, 13), + ] + + mapped = { + 1: "n", + 2: "m", + 3: "l", + 4: "j", + 5: "k", + 6: "i", + 7: "g", + 8: "h", + 9: "f", + 10: "b", + 11: "a", + 12: "d", + 13: "e", + } + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Add nodes of different label + G1.add_node(0) + G2.add_node("z") + G1.nodes[0]["label"] = "green" + G2.nodes["z"]["label"] = "blue" + + assert vf2pp_isomorphism(G1, G2, node_label="label") is None + + # Make the labels identical + G2.nodes["z"]["label"] = "green" + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Change the structure of the graphs, keeping them isomorphic + G1.add_edge(2, 5) + G2.remove_edge("i", "l") + G2.add_edge("g", "l") + G2.add_edge("m", "f") + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Change the structure of the disconnected sub-graph, keeping it isomorphic + G1.remove_node(13) + G2.remove_node("d") + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Connect the newly added node to the disconnected graph, which now is just a path of size 3 + G1.add_edge(0, 10) + G2.add_edge("e", "z") + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Connect the two disconnected sub-graphs, forming a single graph + G1.add_edge(11, 3) + G1.add_edge(0, 8) + G2.add_edge("a", "l") + G2.add_edge("z", "j") + assert vf2pp_isomorphism(G1, G2, node_label="label") + + def test_custom_graph5_same_labels(self): + G1 = nx.Graph() + edges1 = [ + (1, 5), + (1, 2), + (1, 4), + (2, 3), + (2, 6), + (3, 4), + (3, 7), + (4, 8), + (5, 8), + (5, 6), + (6, 7), + (7, 8), + ] + mapped = {1: "a", 2: "h", 3: "d", 4: "i", 5: "g", 6: "b", 7: "j", 8: "c"} + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Add different edges in each graph, maintaining symmetry + G1.add_edges_from([(3, 6), (2, 7), (2, 5), (1, 3), (4, 7), (6, 8)]) + G2.add_edges_from( + [ + (mapped[6], mapped[3]), + (mapped[2], mapped[7]), + (mapped[1], mapped[6]), + (mapped[5], mapped[7]), + (mapped[3], mapped[8]), + (mapped[2], mapped[4]), + ] + ) + assert vf2pp_isomorphism(G1, G2, node_label="label") + + # Obtain two different but isomorphic subgraphs from G1 and G2 + H1 = nx.Graph(G1.subgraph([1, 5, 8, 6, 7, 3])) + H2 = nx.Graph( + G2.subgraph( + [mapped[1], mapped[4], mapped[8], mapped[7], mapped[3], mapped[5]] + ) + ) + assert vf2pp_isomorphism(H1, H2, node_label="label") + + # Delete corresponding node from the two graphs + H1.remove_node(8) + H2.remove_node(mapped[7]) + assert vf2pp_isomorphism(H1, H2, node_label="label") + + # Re-orient, maintaining isomorphism + H1.add_edge(1, 6) + H1.remove_edge(3, 6) + assert vf2pp_isomorphism(H1, H2, node_label="label") + + def test_custom_graph5_different_labels(self): + G1 = nx.Graph() + edges1 = [ + (1, 5), + (1, 2), + (1, 4), + (2, 3), + (2, 6), + (3, 4), + (3, 7), + (4, 8), + (5, 8), + (5, 6), + (6, 7), + (7, 8), + ] + mapped = {1: "a", 2: "h", 3: "d", 4: "i", 5: "g", 6: "b", 7: "j", 8: "c"} + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + + colors = ["red", "blue", "grey", "none", "brown", "solarized", "yellow", "pink"] + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip([mapped[n] for n in G1], it.cycle(labels_many))), + "label", + ) + assert vf2pp_isomorphism(G1, G2, node_label="label") == mapped + + # Assign different colors to matching nodes + c = 0 + for node in G1.nodes(): + color1 = colors[c] + color2 = colors[(c + 3) % len(colors)] + G1.nodes[node]["label"] = color1 + G2.nodes[mapped[node]]["label"] = color2 + c += 1 + + assert vf2pp_isomorphism(G1, G2, node_label="label") is None + + # Get symmetrical sub-graphs of G1,G2 and compare them + H1 = G1.subgraph([1, 5]) + H2 = G2.subgraph(["i", "c"]) + c = 0 + for node1, node2 in zip(H1.nodes(), H2.nodes()): + H1.nodes[node1]["label"] = "red" + H2.nodes[node2]["label"] = "red" + c += 1 + + assert vf2pp_isomorphism(H1, H2, node_label="label") + + def test_disconnected_graph_all_same_labels(self): + G1 = nx.Graph() + G1.add_nodes_from(list(range(10))) + + mapped = {0: 9, 1: 8, 2: 7, 3: 6, 4: 5, 5: 4, 6: 3, 7: 2, 8: 1, 9: 0} + G2 = nx.relabel_nodes(G1, mapped) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + assert vf2pp_isomorphism(G1, G2, node_label="label") + + def test_disconnected_graph_all_different_labels(self): + G1 = nx.Graph() + G1.add_nodes_from(list(range(10))) + + mapped = {0: 9, 1: 8, 2: 7, 3: 6, 4: 5, 5: 4, 6: 3, 7: 2, 8: 1, 9: 0} + G2 = nx.relabel_nodes(G1, mapped) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip([mapped[n] for n in G1], it.cycle(labels_many))), + "label", + ) + assert vf2pp_isomorphism(G1, G2, node_label="label") == mapped + + def test_disconnected_graph_some_same_labels(self): + G1 = nx.Graph() + G1.add_nodes_from(list(range(10))) + + mapped = {0: 9, 1: 8, 2: 7, 3: 6, 4: 5, 5: 4, 6: 3, 7: 2, 8: 1, 9: 0} + G2 = nx.relabel_nodes(G1, mapped) + + colors = [ + "white", + "white", + "white", + "purple", + "purple", + "red", + "red", + "pink", + "pink", + "pink", + ] + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(colors))), "label") + nx.set_node_attributes( + G2, dict(zip([mapped[n] for n in G1], it.cycle(colors))), "label" + ) + + assert vf2pp_isomorphism(G1, G2, node_label="label") + + +class TestMultiGraphISOVF2pp: + def test_custom_multigraph1_same_labels(self): + G1 = nx.MultiGraph() + + mapped = {1: "A", 2: "B", 3: "C", 4: "D", 5: "Z", 6: "E"} + edges1 = [ + (1, 2), + (1, 3), + (1, 4), + (1, 4), + (1, 4), + (2, 3), + (2, 6), + (2, 6), + (3, 4), + (3, 4), + (5, 1), + (5, 1), + (5, 2), + (5, 2), + ] + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Transfer the 2-clique to the right side of G1 + G1.remove_edges_from([(2, 6), (2, 6)]) + G1.add_edges_from([(3, 6), (3, 6)]) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Delete an edges, making them symmetrical, so the position of the 2-clique doesn't matter + G2.remove_edge(mapped[1], mapped[4]) + G1.remove_edge(1, 4) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Add self-loops + G1.add_edges_from([(5, 5), (5, 5), (1, 1)]) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Compensate in G2 + G2.add_edges_from( + [(mapped[1], mapped[1]), (mapped[4], mapped[4]), (mapped[4], mapped[4])] + ) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + def test_custom_multigraph1_different_labels(self): + G1 = nx.MultiGraph() + + mapped = {1: "A", 2: "B", 3: "C", 4: "D", 5: "Z", 6: "E"} + edges1 = [ + (1, 2), + (1, 3), + (1, 4), + (1, 4), + (1, 4), + (2, 3), + (2, 6), + (2, 6), + (3, 4), + (3, 4), + (5, 1), + (5, 1), + (5, 2), + (5, 2), + ] + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip([mapped[n] for n in G1], it.cycle(labels_many))), + "label", + ) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + assert m == mapped + + # Re-structure G1, maintaining the degree sequence + G1.remove_edge(1, 4) + G1.add_edge(1, 5) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Restructure G2, making it isomorphic to G1 + G2.remove_edge("A", "D") + G2.add_edge("A", "Z") + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + assert m == mapped + + # Add edge from node to itself + G1.add_edges_from([(6, 6), (6, 6), (6, 6)]) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Same for G2 + G2.add_edges_from([("E", "E"), ("E", "E"), ("E", "E")]) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + assert m == mapped + + def test_custom_multigraph2_same_labels(self): + G1 = nx.MultiGraph() + + mapped = {1: "A", 2: "C", 3: "D", 4: "E", 5: "G", 7: "B", 6: "F"} + edges1 = [ + (1, 2), + (1, 2), + (1, 5), + (1, 5), + (1, 5), + (5, 6), + (2, 3), + (2, 3), + (2, 4), + (3, 4), + (3, 4), + (4, 5), + (4, 5), + (4, 5), + (2, 7), + (2, 7), + (2, 7), + ] + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Obtain two non-isomorphic subgraphs from the graph + G2.remove_edges_from([(mapped[1], mapped[2]), (mapped[1], mapped[2])]) + G2.add_edge(mapped[1], mapped[4]) + H1 = nx.MultiGraph(G1.subgraph([2, 3, 4, 7])) + H2 = nx.MultiGraph(G2.subgraph([mapped[1], mapped[4], mapped[5], mapped[6]])) + + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert not m + + # Make them isomorphic + H1.remove_edge(3, 4) + H1.add_edges_from([(2, 3), (2, 4), (2, 4)]) + H2.add_edges_from([(mapped[5], mapped[6]), (mapped[5], mapped[6])]) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + # Remove triangle edge + H1.remove_edges_from([(2, 3), (2, 3), (2, 3)]) + H2.remove_edges_from([(mapped[5], mapped[4])] * 3) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + # Change the edge orientation such that H1 is rotated H2 + H1.remove_edges_from([(2, 7), (2, 7)]) + H1.add_edges_from([(3, 4), (3, 4)]) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + # Add extra edges maintaining degree sequence, but in a non-symmetrical manner + H2.add_edge(mapped[5], mapped[1]) + H1.add_edge(3, 4) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert not m + + def test_custom_multigraph2_different_labels(self): + G1 = nx.MultiGraph() + + mapped = {1: "A", 2: "C", 3: "D", 4: "E", 5: "G", 7: "B", 6: "F"} + edges1 = [ + (1, 2), + (1, 2), + (1, 5), + (1, 5), + (1, 5), + (5, 6), + (2, 3), + (2, 3), + (2, 4), + (3, 4), + (3, 4), + (4, 5), + (4, 5), + (4, 5), + (2, 7), + (2, 7), + (2, 7), + ] + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip([mapped[n] for n in G1], it.cycle(labels_many))), + "label", + ) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + assert m == mapped + + # Re-structure G1 + G1.remove_edge(2, 7) + G1.add_edge(5, 6) + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Same for G2 + G2.remove_edge("B", "C") + G2.add_edge("G", "F") + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + assert m == mapped + + # Delete node from G1 and G2, keeping them isomorphic + G1.remove_node(3) + G2.remove_node("D") + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Change G1 edges + G1.remove_edge(1, 2) + G1.remove_edge(2, 7) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Make G2 identical to G1, but with different edge orientation and different labels + G2.add_edges_from([("A", "C"), ("C", "E"), ("C", "E")]) + G2.remove_edges_from( + [("A", "G"), ("A", "G"), ("F", "G"), ("E", "G"), ("E", "G")] + ) + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Make all labels the same, so G1 and G2 are also isomorphic + for n1, n2 in zip(G1.nodes(), G2.nodes()): + G1.nodes[n1]["label"] = "blue" + G2.nodes[n2]["label"] = "blue" + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + def test_custom_multigraph3_same_labels(self): + G1 = nx.MultiGraph() + + mapped = {1: 9, 2: 8, 3: 7, 4: 6, 5: 3, 8: 5, 9: 4, 7: 1, 6: 2} + edges1 = [ + (1, 2), + (1, 3), + (1, 3), + (2, 3), + (2, 3), + (3, 4), + (4, 5), + (4, 7), + (4, 9), + (4, 9), + (4, 9), + (5, 8), + (5, 8), + (8, 9), + (8, 9), + (5, 6), + (6, 7), + (6, 7), + (6, 7), + (5, 2), + ] + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Connect nodes maintaining symmetry + G1.add_edges_from([(6, 9), (7, 8), (5, 8), (4, 9), (4, 9)]) + G2.add_edges_from( + [ + (mapped[6], mapped[8]), + (mapped[7], mapped[9]), + (mapped[5], mapped[8]), + (mapped[4], mapped[9]), + (mapped[4], mapped[9]), + ] + ) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Make isomorphic + G1.add_edges_from([(6, 8), (6, 8), (7, 9), (7, 9), (7, 9)]) + G2.add_edges_from( + [ + (mapped[6], mapped[8]), + (mapped[6], mapped[9]), + (mapped[7], mapped[8]), + (mapped[7], mapped[9]), + (mapped[7], mapped[9]), + ] + ) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Connect more nodes + G1.add_edges_from([(2, 7), (2, 7), (3, 6), (3, 6)]) + G2.add_edges_from( + [ + (mapped[2], mapped[7]), + (mapped[2], mapped[7]), + (mapped[3], mapped[6]), + (mapped[3], mapped[6]), + ] + ) + G1.add_node(10) + G2.add_node("Z") + G1.nodes[10]["label"] = "blue" + G2.nodes["Z"]["label"] = "blue" + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Connect the newly added node, to opposite sides of the graph + G1.add_edges_from([(10, 1), (10, 5), (10, 8), (10, 10), (10, 10)]) + G2.add_edges_from( + [ + ("Z", mapped[1]), + ("Z", mapped[4]), + ("Z", mapped[9]), + ("Z", "Z"), + ("Z", "Z"), + ] + ) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # We connected the new node to opposite sides, so G1 must be symmetrical to G2. Re-structure them to be so + G1.remove_edges_from([(1, 3), (4, 9), (4, 9), (7, 9)]) + G2.remove_edges_from( + [ + (mapped[1], mapped[3]), + (mapped[4], mapped[9]), + (mapped[4], mapped[9]), + (mapped[7], mapped[9]), + ] + ) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Get two subgraphs that are not isomorphic but are easy to make + H1 = nx.Graph(G1.subgraph([2, 3, 4, 5, 6, 7, 10])) + H2 = nx.Graph( + G2.subgraph( + [mapped[4], mapped[5], mapped[6], mapped[7], mapped[8], mapped[9], "Z"] + ) + ) + + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert not m + + # Restructure both to make them isomorphic + H1.add_edges_from([(10, 2), (10, 6), (3, 6), (2, 7), (2, 6), (3, 7)]) + H2.add_edges_from( + [("Z", mapped[7]), (mapped[6], mapped[9]), (mapped[7], mapped[8])] + ) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + # Remove one self-loop in H2 + H2.remove_edge("Z", "Z") + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert not m + + # Compensate in H1 + H1.remove_edge(10, 10) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + def test_custom_multigraph3_different_labels(self): + G1 = nx.MultiGraph() + + mapped = {1: 9, 2: 8, 3: 7, 4: 6, 5: 3, 8: 5, 9: 4, 7: 1, 6: 2} + edges1 = [ + (1, 2), + (1, 3), + (1, 3), + (2, 3), + (2, 3), + (3, 4), + (4, 5), + (4, 7), + (4, 9), + (4, 9), + (4, 9), + (5, 8), + (5, 8), + (8, 9), + (8, 9), + (5, 6), + (6, 7), + (6, 7), + (6, 7), + (5, 2), + ] + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip([mapped[n] for n in G1], it.cycle(labels_many))), + "label", + ) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + assert m == mapped + + # Delete edge maintaining isomorphism + G1.remove_edge(4, 9) + G2.remove_edge(4, 6) + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + assert m == mapped + + # Change edge orientation such that G1 mirrors G2 + G1.add_edges_from([(4, 9), (1, 2), (1, 2)]) + G1.remove_edges_from([(1, 3), (1, 3)]) + G2.add_edges_from([(3, 5), (7, 9)]) + G2.remove_edge(8, 9) + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Make all labels the same, so G1 and G2 are also isomorphic + for n1, n2 in zip(G1.nodes(), G2.nodes()): + G1.nodes[n1]["label"] = "blue" + G2.nodes[n2]["label"] = "blue" + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + G1.add_node(10) + G2.add_node("Z") + G1.nodes[10]["label"] = "green" + G2.nodes["Z"]["label"] = "green" + + # Add different number of edges between the new nodes and themselves + G1.add_edges_from([(10, 10), (10, 10)]) + G2.add_edges_from([("Z", "Z")]) + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Make the number of self-edges equal + G1.remove_edge(10, 10) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Connect the new node to the graph + G1.add_edges_from([(10, 3), (10, 4)]) + G2.add_edges_from([("Z", 8), ("Z", 3)]) + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Remove central node + G1.remove_node(4) + G2.remove_node(3) + G1.add_edges_from([(5, 6), (5, 6), (5, 7)]) + G2.add_edges_from([(1, 6), (1, 6), (6, 2)]) + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + def test_custom_multigraph4_same_labels(self): + G1 = nx.MultiGraph() + edges1 = [ + (1, 2), + (1, 2), + (2, 2), + (2, 3), + (3, 8), + (3, 8), + (3, 4), + (4, 5), + (4, 5), + (4, 5), + (4, 6), + (3, 6), + (3, 6), + (6, 6), + (8, 7), + (7, 7), + (8, 9), + (9, 9), + (8, 9), + (8, 9), + (5, 9), + (10, 11), + (11, 12), + (12, 13), + (11, 13), + (10, 10), + (10, 11), + (11, 13), + ] + + mapped = { + 1: "n", + 2: "m", + 3: "l", + 4: "j", + 5: "k", + 6: "i", + 7: "g", + 8: "h", + 9: "f", + 10: "b", + 11: "a", + 12: "d", + 13: "e", + } + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Add extra but corresponding edges to both graphs + G1.add_edges_from([(2, 2), (2, 3), (2, 8), (3, 4)]) + G2.add_edges_from([("m", "m"), ("m", "l"), ("m", "h"), ("l", "j")]) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Obtain subgraphs + H1 = nx.MultiGraph(G1.subgraph([2, 3, 4, 6, 10, 11, 12, 13])) + H2 = nx.MultiGraph( + G2.subgraph( + [ + mapped[2], + mapped[3], + mapped[8], + mapped[9], + mapped[10], + mapped[11], + mapped[12], + mapped[13], + ] + ) + ) + + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert not m + + # Make them isomorphic + H2.remove_edges_from( + [(mapped[3], mapped[2]), (mapped[9], mapped[8]), (mapped[2], mapped[2])] + ) + H2.add_edges_from([(mapped[9], mapped[9]), (mapped[2], mapped[8])]) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + # Re-structure the disconnected sub-graph + H1.remove_node(12) + H2.remove_node(mapped[12]) + H1.add_edge(13, 13) + H2.add_edge(mapped[13], mapped[13]) + + # Connect the two disconnected components, forming a single graph + H1.add_edges_from([(3, 13), (6, 11)]) + H2.add_edges_from([(mapped[8], mapped[10]), (mapped[2], mapped[11])]) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + # Change orientation of self-loops in one graph, maintaining the degree sequence + H1.remove_edges_from([(2, 2), (3, 6)]) + H1.add_edges_from([(6, 6), (2, 3)]) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert not m + + def test_custom_multigraph4_different_labels(self): + G1 = nx.MultiGraph() + edges1 = [ + (1, 2), + (1, 2), + (2, 2), + (2, 3), + (3, 8), + (3, 8), + (3, 4), + (4, 5), + (4, 5), + (4, 5), + (4, 6), + (3, 6), + (3, 6), + (6, 6), + (8, 7), + (7, 7), + (8, 9), + (9, 9), + (8, 9), + (8, 9), + (5, 9), + (10, 11), + (11, 12), + (12, 13), + (11, 13), + ] + + mapped = { + 1: "n", + 2: "m", + 3: "l", + 4: "j", + 5: "k", + 6: "i", + 7: "g", + 8: "h", + 9: "f", + 10: "b", + 11: "a", + 12: "d", + 13: "e", + } + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip([mapped[n] for n in G1], it.cycle(labels_many))), + "label", + ) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m == mapped + + # Add extra but corresponding edges to both graphs + G1.add_edges_from([(2, 2), (2, 3), (2, 8), (3, 4)]) + G2.add_edges_from([("m", "m"), ("m", "l"), ("m", "h"), ("l", "j")]) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m == mapped + + # Obtain isomorphic subgraphs + H1 = nx.MultiGraph(G1.subgraph([2, 3, 4, 6])) + H2 = nx.MultiGraph(G2.subgraph(["m", "l", "j", "i"])) + + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + # Delete the 3-clique, keeping only the path-graph. Also, H1 mirrors H2 + H1.remove_node(4) + H2.remove_node("j") + H1.remove_edges_from([(2, 2), (2, 3), (6, 6)]) + H2.remove_edges_from([("l", "i"), ("m", "m"), ("m", "m")]) + + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert not m + + # Assign the same labels so that mirroring means isomorphic + for n1, n2 in zip(H1.nodes(), H2.nodes()): + H1.nodes[n1]["label"] = "red" + H2.nodes[n2]["label"] = "red" + + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + # Leave only one node with self-loop + H1.remove_nodes_from([3, 6]) + H2.remove_nodes_from(["m", "l"]) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + # Remove one self-loop from H1 + H1.remove_edge(2, 2) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert not m + + # Same for H2 + H2.remove_edge("i", "i") + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + # Compose H1 with the disconnected sub-graph of G1. Same for H2 + S1 = nx.compose(H1, nx.MultiGraph(G1.subgraph([10, 11, 12, 13]))) + S2 = nx.compose(H2, nx.MultiGraph(G2.subgraph(["a", "b", "d", "e"]))) + + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + # Connect the two components + S1.add_edges_from([(13, 13), (13, 13), (2, 13)]) + S2.add_edges_from([("a", "a"), ("a", "a"), ("i", "e")]) + m = vf2pp_isomorphism(H1, H2, node_label="label") + assert m + + def test_custom_multigraph5_same_labels(self): + G1 = nx.MultiGraph() + + edges1 = [ + (1, 5), + (1, 2), + (1, 4), + (2, 3), + (2, 6), + (3, 4), + (3, 7), + (4, 8), + (5, 8), + (5, 6), + (6, 7), + (7, 8), + ] + mapped = {1: "a", 2: "h", 3: "d", 4: "i", 5: "g", 6: "b", 7: "j", 8: "c"} + + G1.add_edges_from(edges1) + G2 = nx.relabel_nodes(G1, mapped) + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Add multiple edges and self-loops, maintaining isomorphism + G1.add_edges_from( + [(1, 2), (1, 2), (3, 7), (8, 8), (8, 8), (7, 8), (2, 3), (5, 6)] + ) + G2.add_edges_from( + [ + ("a", "h"), + ("a", "h"), + ("d", "j"), + ("c", "c"), + ("c", "c"), + ("j", "c"), + ("d", "h"), + ("g", "b"), + ] + ) + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Make G2 to be the rotated G1 + G2.remove_edges_from( + [ + ("a", "h"), + ("a", "h"), + ("d", "j"), + ("c", "c"), + ("c", "c"), + ("j", "c"), + ("d", "h"), + ("g", "b"), + ] + ) + G2.add_edges_from( + [ + ("d", "i"), + ("a", "h"), + ("g", "b"), + ("g", "b"), + ("i", "i"), + ("i", "i"), + ("b", "j"), + ("d", "j"), + ] + ) + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + def test_disconnected_multigraph_all_same_labels(self): + G1 = nx.MultiGraph() + G1.add_nodes_from(list(range(10))) + G1.add_edges_from([(i, i) for i in range(10)]) + + mapped = {0: 9, 1: 8, 2: 7, 3: 6, 4: 5, 5: 4, 6: 3, 7: 2, 8: 1, 9: 0} + G2 = nx.relabel_nodes(G1, mapped) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_same))), "label") + nx.set_node_attributes(G2, dict(zip(G2, it.cycle(labels_same))), "label") + + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Add self-loops to non-mapped nodes. Should be the same, as the graph is disconnected. + G1.add_edges_from([(i, i) for i in range(5, 8)] * 3) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Compensate in G2 + G2.add_edges_from([(i, i) for i in range(3)] * 3) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + # Add one more self-loop in G2 + G2.add_edges_from([(0, 0), (1, 1), (1, 1)]) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Compensate in G1 + G1.add_edges_from([(5, 5), (7, 7), (7, 7)]) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + def test_disconnected_multigraph_all_different_labels(self): + G1 = nx.MultiGraph() + G1.add_nodes_from(list(range(10))) + G1.add_edges_from([(i, i) for i in range(10)]) + + mapped = {0: 9, 1: 8, 2: 7, 3: 6, 4: 5, 5: 4, 6: 3, 7: 2, 8: 1, 9: 0} + G2 = nx.relabel_nodes(G1, mapped) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip([mapped[n] for n in G1], it.cycle(labels_many))), + "label", + ) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + assert m == mapped + + # Add self-loops to non-mapped nodes. Now it is not the same, as there are different labels + G1.add_edges_from([(i, i) for i in range(5, 8)] * 3) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Add self-loops to non mapped nodes in G2 as well + G2.add_edges_from([(mapped[i], mapped[i]) for i in range(3)] * 7) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Add self-loops to mapped nodes in G2 + G2.add_edges_from([(mapped[i], mapped[i]) for i in range(5, 8)] * 3) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert not m + + # Add self-loops to G1 so that they are even in both graphs + G1.add_edges_from([(i, i) for i in range(3)] * 7) + m = vf2pp_isomorphism(G1, G2, node_label="label") + assert m + + +class TestDiGraphISOVF2pp: + def test_wikipedia_graph(self): + edges1 = [ + (1, 5), + (1, 2), + (1, 4), + (3, 2), + (6, 2), + (3, 4), + (7, 3), + (4, 8), + (5, 8), + (6, 5), + (6, 7), + (7, 8), + ] + mapped = {1: "a", 2: "h", 3: "d", 4: "i", 5: "g", 6: "b", 7: "j", 8: "c"} + + G1 = nx.DiGraph(edges1) + G2 = nx.relabel_nodes(G1, mapped) + + assert vf2pp_isomorphism(G1, G2) == mapped + + # Change the direction of an edge + G1.remove_edge(1, 5) + G1.add_edge(5, 1) + assert vf2pp_isomorphism(G1, G2) is None + + def test_non_isomorphic_same_degree_sequence(self): + r""" + G1 G2 + x--------------x x--------------x + | \ | | \ | + | x-------x | | x-------x | + | | | | | | | | + | x-------x | | x-------x | + | / | | \ | + x--------------x x--------------x + """ + edges1 = [ + (1, 5), + (1, 2), + (4, 1), + (3, 2), + (3, 4), + (4, 8), + (5, 8), + (6, 5), + (6, 7), + (7, 8), + ] + edges2 = [ + (1, 5), + (1, 2), + (4, 1), + (3, 2), + (4, 3), + (5, 8), + (6, 5), + (6, 7), + (3, 7), + (8, 7), + ] + + G1 = nx.DiGraph(edges1) + G2 = nx.DiGraph(edges2) + assert vf2pp_isomorphism(G1, G2) is None diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_vf2pp_helpers.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_vf2pp_helpers.py new file mode 100644 index 00000000..0e29b1be --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_vf2pp_helpers.py @@ -0,0 +1,3106 @@ +import itertools as it + +import pytest + +import networkx as nx +from networkx import vf2pp_is_isomorphic, vf2pp_isomorphism +from networkx.algorithms.isomorphism.vf2pp import ( + _consistent_PT, + _cut_PT, + _feasibility, + _find_candidates, + _find_candidates_Di, + _GraphParameters, + _initialize_parameters, + _matching_order, + _restore_Tinout, + _restore_Tinout_Di, + _StateParameters, + _update_Tinout, +) + +labels_same = ["blue"] + +labels_many = [ + "white", + "red", + "blue", + "green", + "orange", + "black", + "purple", + "yellow", + "brown", + "cyan", + "solarized", + "pink", + "none", +] + + +class TestNodeOrdering: + def test_empty_graph(self): + G1 = nx.Graph() + G2 = nx.Graph() + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + assert len(set(_matching_order(gparams))) == 0 + + def test_single_node(self): + G1 = nx.Graph() + G2 = nx.Graph() + G1.add_node(1) + G2.add_node(1) + + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels_many))), "label") + nx.set_node_attributes( + G2, + dict(zip(G2, it.cycle(labels_many))), + "label", + ) + l1, l2 = ( + nx.get_node_attributes(G1, "label"), + nx.get_node_attributes(G2, "label"), + ) + + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups(dict(G2.degree())), + ) + m = _matching_order(gparams) + assert m == [1] + + def test_matching_order(self): + labels = [ + "blue", + "blue", + "red", + "red", + "red", + "red", + "green", + "green", + "green", + "yellow", + "purple", + "purple", + "blue", + "blue", + ] + G1 = nx.Graph( + [ + (0, 1), + (0, 2), + (1, 2), + (2, 5), + (2, 4), + (1, 3), + (1, 4), + (3, 6), + (4, 6), + (6, 7), + (7, 8), + (9, 10), + (9, 11), + (11, 12), + (11, 13), + (12, 13), + (10, 13), + ] + ) + G2 = G1.copy() + nx.set_node_attributes(G1, dict(zip(G1, it.cycle(labels))), "label") + nx.set_node_attributes( + G2, + dict(zip(G2, it.cycle(labels))), + "label", + ) + l1, l2 = ( + nx.get_node_attributes(G1, "label"), + nx.get_node_attributes(G2, "label"), + ) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups(dict(G2.degree())), + ) + + expected = [9, 11, 10, 13, 12, 1, 2, 4, 0, 3, 6, 5, 7, 8] + assert _matching_order(gparams) == expected + + def test_matching_order_all_branches(self): + G1 = nx.Graph( + [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 4), (3, 4)] + ) + G1.add_node(5) + G2 = G1.copy() + + G1.nodes[0]["label"] = "black" + G1.nodes[1]["label"] = "blue" + G1.nodes[2]["label"] = "blue" + G1.nodes[3]["label"] = "red" + G1.nodes[4]["label"] = "red" + G1.nodes[5]["label"] = "blue" + + G2.nodes[0]["label"] = "black" + G2.nodes[1]["label"] = "blue" + G2.nodes[2]["label"] = "blue" + G2.nodes[3]["label"] = "red" + G2.nodes[4]["label"] = "red" + G2.nodes[5]["label"] = "blue" + + l1, l2 = ( + nx.get_node_attributes(G1, "label"), + nx.get_node_attributes(G2, "label"), + ) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups(dict(G2.degree())), + ) + + expected = [0, 4, 1, 3, 2, 5] + assert _matching_order(gparams) == expected + + +class TestGraphCandidateSelection: + G1_edges = [ + (1, 2), + (1, 4), + (1, 5), + (2, 3), + (2, 4), + (3, 4), + (4, 5), + (1, 6), + (6, 7), + (6, 8), + (8, 9), + (7, 9), + ] + mapped = { + 0: "x", + 1: "a", + 2: "b", + 3: "c", + 4: "d", + 5: "e", + 6: "f", + 7: "g", + 8: "h", + 9: "i", + } + + def test_no_covered_neighbors_no_labels(self): + G1 = nx.Graph() + G1.add_edges_from(self.G1_edges) + G1.add_node(0) + G2 = nx.relabel_nodes(G1, self.mapped) + + G1_degree = dict(G1.degree) + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups(dict(G2.degree())), + ) + + m = {9: self.mapped[9], 1: self.mapped[1]} + m_rev = {self.mapped[9]: 9, self.mapped[1]: 1} + + T1 = {7, 8, 2, 4, 5} + T1_tilde = {0, 3, 6} + T2 = {"g", "h", "b", "d", "e"} + T2_tilde = {"x", "c", "f"} + + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) + + u = 3 + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + u = 0 + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + m.pop(9) + m_rev.pop(self.mapped[9]) + + T1 = {2, 4, 5, 6} + T1_tilde = {0, 3, 7, 8, 9} + T2 = {"g", "h", "b", "d", "e", "f"} + T2_tilde = {"x", "c", "g", "h", "i"} + + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) + + u = 7 + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == { + self.mapped[u], + self.mapped[8], + self.mapped[3], + self.mapped[9], + } + + def test_no_covered_neighbors_with_labels(self): + G1 = nx.Graph() + G1.add_edges_from(self.G1_edges) + G1.add_node(0) + G2 = nx.relabel_nodes(G1, self.mapped) + + G1_degree = dict(G1.degree) + nx.set_node_attributes( + G1, + dict(zip(G1, it.cycle(labels_many))), + "label", + ) + nx.set_node_attributes( + G2, + dict( + zip( + [self.mapped[n] for n in G1], + it.cycle(labels_many), + ) + ), + "label", + ) + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups(dict(G2.degree())), + ) + + m = {9: self.mapped[9], 1: self.mapped[1]} + m_rev = {self.mapped[9]: 9, self.mapped[1]: 1} + + T1 = {7, 8, 2, 4, 5, 6} + T1_tilde = {0, 3} + T2 = {"g", "h", "b", "d", "e", "f"} + T2_tilde = {"x", "c"} + + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) + + u = 3 + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + u = 0 + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + # Change label of disconnected node + G1.nodes[u]["label"] = "blue" + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups(dict(G2.degree())), + ) + + # No candidate + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == set() + + m.pop(9) + m_rev.pop(self.mapped[9]) + + T1 = {2, 4, 5, 6} + T1_tilde = {0, 3, 7, 8, 9} + T2 = {"b", "d", "e", "f"} + T2_tilde = {"x", "c", "g", "h", "i"} + + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) + + u = 7 + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + G1.nodes[8]["label"] = G1.nodes[7]["label"] + G2.nodes[self.mapped[8]]["label"] = G1.nodes[7]["label"] + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups(dict(G2.degree())), + ) + + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u], self.mapped[8]} + + def test_covered_neighbors_no_labels(self): + G1 = nx.Graph() + G1.add_edges_from(self.G1_edges) + G1.add_node(0) + G2 = nx.relabel_nodes(G1, self.mapped) + + G1_degree = dict(G1.degree) + l1 = dict(G1.nodes(data=None, default=-1)) + l2 = dict(G2.nodes(data=None, default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups(dict(G2.degree())), + ) + + m = {9: self.mapped[9], 1: self.mapped[1]} + m_rev = {self.mapped[9]: 9, self.mapped[1]: 1} + + T1 = {7, 8, 2, 4, 5, 6} + T1_tilde = {0, 3} + T2 = {"g", "h", "b", "d", "e", "f"} + T2_tilde = {"x", "c"} + + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) + + u = 5 + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + u = 6 + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u], self.mapped[2]} + + def test_covered_neighbors_with_labels(self): + G1 = nx.Graph() + G1.add_edges_from(self.G1_edges) + G1.add_node(0) + G2 = nx.relabel_nodes(G1, self.mapped) + + G1_degree = dict(G1.degree) + nx.set_node_attributes( + G1, + dict(zip(G1, it.cycle(labels_many))), + "label", + ) + nx.set_node_attributes( + G2, + dict( + zip( + [self.mapped[n] for n in G1], + it.cycle(labels_many), + ) + ), + "label", + ) + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups(dict(G2.degree())), + ) + + m = {9: self.mapped[9], 1: self.mapped[1]} + m_rev = {self.mapped[9]: 9, self.mapped[1]: 1} + + T1 = {7, 8, 2, 4, 5, 6} + T1_tilde = {0, 3} + T2 = {"g", "h", "b", "d", "e", "f"} + T2_tilde = {"x", "c"} + + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) + + u = 5 + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + u = 6 + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + # Assign to 2, the same label as 6 + G1.nodes[2]["label"] = G1.nodes[u]["label"] + G2.nodes[self.mapped[2]]["label"] = G1.nodes[u]["label"] + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups(dict(G2.degree())), + ) + + candidates = _find_candidates(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u], self.mapped[2]} + + +class TestDiGraphCandidateSelection: + G1_edges = [ + (1, 2), + (1, 4), + (5, 1), + (2, 3), + (4, 2), + (3, 4), + (4, 5), + (1, 6), + (6, 7), + (6, 8), + (8, 9), + (7, 9), + ] + mapped = { + 0: "x", + 1: "a", + 2: "b", + 3: "c", + 4: "d", + 5: "e", + 6: "f", + 7: "g", + 8: "h", + 9: "i", + } + + def test_no_covered_neighbors_no_labels(self): + G1 = nx.DiGraph() + G1.add_edges_from(self.G1_edges) + G1.add_node(0) + G2 = nx.relabel_nodes(G1, self.mapped) + + G1_degree = { + n: (in_degree, out_degree) + for (n, in_degree), (_, out_degree) in zip(G1.in_degree, G1.out_degree) + } + + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups( + { + node: (in_degree, out_degree) + for (node, in_degree), (_, out_degree) in zip( + G2.in_degree(), G2.out_degree() + ) + } + ), + ) + + m = {9: self.mapped[9], 1: self.mapped[1]} + m_rev = {self.mapped[9]: 9, self.mapped[1]: 1} + + T1_out = {2, 4, 6} + T1_in = {5, 7, 8} + T1_tilde = {0, 3} + T2_out = {"b", "d", "f"} + T2_in = {"e", "g", "h"} + T2_tilde = {"x", "c"} + + sparams = _StateParameters( + m, m_rev, T1_out, T1_in, T1_tilde, None, T2_out, T2_in, T2_tilde, None + ) + + u = 3 + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + u = 0 + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + m.pop(9) + m_rev.pop(self.mapped[9]) + + T1_out = {2, 4, 6} + T1_in = {5} + T1_tilde = {0, 3, 7, 8, 9} + T2_out = {"b", "d", "f"} + T2_in = {"e"} + T2_tilde = {"x", "c", "g", "h", "i"} + + sparams = _StateParameters( + m, m_rev, T1_out, T1_in, T1_tilde, None, T2_out, T2_in, T2_tilde, None + ) + + u = 7 + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u], self.mapped[8], self.mapped[3]} + + def test_no_covered_neighbors_with_labels(self): + G1 = nx.DiGraph() + G1.add_edges_from(self.G1_edges) + G1.add_node(0) + G2 = nx.relabel_nodes(G1, self.mapped) + + G1_degree = { + n: (in_degree, out_degree) + for (n, in_degree), (_, out_degree) in zip(G1.in_degree, G1.out_degree) + } + nx.set_node_attributes( + G1, + dict(zip(G1, it.cycle(labels_many))), + "label", + ) + nx.set_node_attributes( + G2, + dict( + zip( + [self.mapped[n] for n in G1], + it.cycle(labels_many), + ) + ), + "label", + ) + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups( + { + node: (in_degree, out_degree) + for (node, in_degree), (_, out_degree) in zip( + G2.in_degree(), G2.out_degree() + ) + } + ), + ) + + m = {9: self.mapped[9], 1: self.mapped[1]} + m_rev = {self.mapped[9]: 9, self.mapped[1]: 1} + + T1_out = {2, 4, 6} + T1_in = {5, 7, 8} + T1_tilde = {0, 3} + T2_out = {"b", "d", "f"} + T2_in = {"e", "g", "h"} + T2_tilde = {"x", "c"} + + sparams = _StateParameters( + m, m_rev, T1_out, T1_in, T1_tilde, None, T2_out, T2_in, T2_tilde, None + ) + + u = 3 + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + u = 0 + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + # Change label of disconnected node + G1.nodes[u]["label"] = "blue" + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups( + { + node: (in_degree, out_degree) + for (node, in_degree), (_, out_degree) in zip( + G2.in_degree(), G2.out_degree() + ) + } + ), + ) + + # No candidate + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == set() + + m.pop(9) + m_rev.pop(self.mapped[9]) + + T1_out = {2, 4, 6} + T1_in = {5} + T1_tilde = {0, 3, 7, 8, 9} + T2_out = {"b", "d", "f"} + T2_in = {"e"} + T2_tilde = {"x", "c", "g", "h", "i"} + + sparams = _StateParameters( + m, m_rev, T1_out, T1_in, T1_tilde, None, T2_out, T2_in, T2_tilde, None + ) + + u = 7 + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + G1.nodes[8]["label"] = G1.nodes[7]["label"] + G2.nodes[self.mapped[8]]["label"] = G1.nodes[7]["label"] + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups( + { + node: (in_degree, out_degree) + for (node, in_degree), (_, out_degree) in zip( + G2.in_degree(), G2.out_degree() + ) + } + ), + ) + + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u], self.mapped[8]} + + def test_covered_neighbors_no_labels(self): + G1 = nx.DiGraph() + G1.add_edges_from(self.G1_edges) + G1.add_node(0) + G2 = nx.relabel_nodes(G1, self.mapped) + + G1_degree = { + n: (in_degree, out_degree) + for (n, in_degree), (_, out_degree) in zip(G1.in_degree, G1.out_degree) + } + + l1 = dict(G1.nodes(data=None, default=-1)) + l2 = dict(G2.nodes(data=None, default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups( + { + node: (in_degree, out_degree) + for (node, in_degree), (_, out_degree) in zip( + G2.in_degree(), G2.out_degree() + ) + } + ), + ) + + m = {9: self.mapped[9], 1: self.mapped[1]} + m_rev = {self.mapped[9]: 9, self.mapped[1]: 1} + + T1_out = {2, 4, 6} + T1_in = {5, 7, 8} + T1_tilde = {0, 3} + T2_out = {"b", "d", "f"} + T2_in = {"e", "g", "h"} + T2_tilde = {"x", "c"} + + sparams = _StateParameters( + m, m_rev, T1_out, T1_in, T1_tilde, None, T2_out, T2_in, T2_tilde, None + ) + + u = 5 + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + u = 6 + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + # Change the direction of an edge to make the degree orientation same as first candidate of u. + G1.remove_edge(4, 2) + G1.add_edge(2, 4) + G2.remove_edge("d", "b") + G2.add_edge("b", "d") + + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups( + { + node: (in_degree, out_degree) + for (node, in_degree), (_, out_degree) in zip( + G2.in_degree(), G2.out_degree() + ) + } + ), + ) + + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u], self.mapped[2]} + + def test_covered_neighbors_with_labels(self): + G1 = nx.DiGraph() + G1.add_edges_from(self.G1_edges) + G1.add_node(0) + G2 = nx.relabel_nodes(G1, self.mapped) + + G1.remove_edge(4, 2) + G1.add_edge(2, 4) + G2.remove_edge("d", "b") + G2.add_edge("b", "d") + + G1_degree = { + n: (in_degree, out_degree) + for (n, in_degree), (_, out_degree) in zip(G1.in_degree, G1.out_degree) + } + + nx.set_node_attributes( + G1, + dict(zip(G1, it.cycle(labels_many))), + "label", + ) + nx.set_node_attributes( + G2, + dict( + zip( + [self.mapped[n] for n in G1], + it.cycle(labels_many), + ) + ), + "label", + ) + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups( + { + node: (in_degree, out_degree) + for (node, in_degree), (_, out_degree) in zip( + G2.in_degree(), G2.out_degree() + ) + } + ), + ) + + m = {9: self.mapped[9], 1: self.mapped[1]} + m_rev = {self.mapped[9]: 9, self.mapped[1]: 1} + + T1_out = {2, 4, 6} + T1_in = {5, 7, 8} + T1_tilde = {0, 3} + T2_out = {"b", "d", "f"} + T2_in = {"e", "g", "h"} + T2_tilde = {"x", "c"} + + sparams = _StateParameters( + m, m_rev, T1_out, T1_in, T1_tilde, None, T2_out, T2_in, T2_tilde, None + ) + + u = 5 + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + u = 6 + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + # Assign to 2, the same label as 6 + G1.nodes[2]["label"] = G1.nodes[u]["label"] + G2.nodes[self.mapped[2]]["label"] = G1.nodes[u]["label"] + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups( + { + node: (in_degree, out_degree) + for (node, in_degree), (_, out_degree) in zip( + G2.in_degree(), G2.out_degree() + ) + } + ), + ) + + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u], self.mapped[2]} + + # Change the direction of an edge to make the degree orientation same as first candidate of u. + G1.remove_edge(2, 4) + G1.add_edge(4, 2) + G2.remove_edge("b", "d") + G2.add_edge("d", "b") + + gparams = _GraphParameters( + G1, + G2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups( + { + node: (in_degree, out_degree) + for (node, in_degree), (_, out_degree) in zip( + G2.in_degree(), G2.out_degree() + ) + } + ), + ) + + candidates = _find_candidates_Di(u, gparams, sparams, G1_degree) + assert candidates == {self.mapped[u]} + + def test_same_in_out_degrees_no_candidate(self): + g1 = nx.DiGraph([(4, 1), (4, 2), (3, 4), (5, 4), (6, 4)]) + g2 = nx.DiGraph([(1, 4), (2, 4), (3, 4), (4, 5), (4, 6)]) + + l1 = dict(g1.nodes(data=None, default=-1)) + l2 = dict(g2.nodes(data=None, default=-1)) + gparams = _GraphParameters( + g1, + g2, + l1, + l2, + nx.utils.groups(l1), + nx.utils.groups(l2), + nx.utils.groups( + { + node: (in_degree, out_degree) + for (node, in_degree), (_, out_degree) in zip( + g2.in_degree(), g2.out_degree() + ) + } + ), + ) + + g1_degree = { + n: (in_degree, out_degree) + for (n, in_degree), (_, out_degree) in zip(g1.in_degree, g1.out_degree) + } + + m = {1: 1, 2: 2, 3: 3} + m_rev = m.copy() + + T1_out = {4} + T1_in = {4} + T1_tilde = {5, 6} + T2_out = {4} + T2_in = {4} + T2_tilde = {5, 6} + + sparams = _StateParameters( + m, m_rev, T1_out, T1_in, T1_tilde, None, T2_out, T2_in, T2_tilde, None + ) + + u = 4 + # despite the same in and out degree, there's no candidate for u=4 + candidates = _find_candidates_Di(u, gparams, sparams, g1_degree) + assert candidates == set() + # Notice how the regular candidate selection method returns wrong result. + assert _find_candidates(u, gparams, sparams, g1_degree) == {4} + + +class TestGraphISOFeasibility: + def test_const_covered_neighbors(self): + G1 = nx.Graph([(0, 1), (1, 2), (3, 0), (3, 2)]) + G2 = nx.Graph([("a", "b"), ("b", "c"), ("k", "a"), ("k", "c")]) + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c"}, + {"a": 0, "b": 1, "c": 2}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 3, "k" + assert _consistent_PT(u, v, gparams, sparams) + + def test_const_no_covered_neighbors(self): + G1 = nx.Graph([(0, 1), (1, 2), (3, 4), (3, 5)]) + G2 = nx.Graph([("a", "b"), ("b", "c"), ("k", "w"), ("k", "z")]) + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c"}, + {"a": 0, "b": 1, "c": 2}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 3, "k" + assert _consistent_PT(u, v, gparams, sparams) + + def test_const_mixed_covered_uncovered_neighbors(self): + G1 = nx.Graph([(0, 1), (1, 2), (3, 0), (3, 2), (3, 4), (3, 5)]) + G2 = nx.Graph( + [("a", "b"), ("b", "c"), ("k", "a"), ("k", "c"), ("k", "w"), ("k", "z")] + ) + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c"}, + {"a": 0, "b": 1, "c": 2}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 3, "k" + assert _consistent_PT(u, v, gparams, sparams) + + def test_const_fail_cases(self): + G1 = nx.Graph( + [ + (0, 1), + (1, 2), + (10, 0), + (10, 3), + (10, 4), + (10, 5), + (10, 6), + (4, 1), + (5, 3), + ] + ) + G2 = nx.Graph( + [ + ("a", "b"), + ("b", "c"), + ("k", "a"), + ("k", "d"), + ("k", "e"), + ("k", "f"), + ("k", "g"), + ("e", "b"), + ("f", "d"), + ] + ) + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 10, "k" + assert _consistent_PT(u, v, gparams, sparams) + + # Delete one uncovered neighbor of u. Notice how it still passes the test. + # Two reasons for this: + # 1. If u, v had different degrees from the beginning, they wouldn't + # be selected as candidates in the first place. + # 2. Even if they are selected, consistency is basically 1-look-ahead, + # meaning that we take into consideration the relation of the + # candidates with their mapped neighbors. The node we deleted is + # not a covered neighbor. + # Such nodes will be checked by the cut_PT function, which is + # basically the 2-look-ahead, checking the relation of the + # candidates with T1, T2 (in which belongs the node we just deleted). + G1.remove_node(6) + assert _consistent_PT(u, v, gparams, sparams) + + # Add one more covered neighbor of u in G1 + G1.add_edge(u, 2) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compensate in G2 + G2.add_edge(v, "c") + assert _consistent_PT(u, v, gparams, sparams) + + # Add one more covered neighbor of v in G2 + G2.add_edge(v, "x") + G1.add_node(7) + sparams.mapping.update({7: "x"}) + sparams.reverse_mapping.update({"x": 7}) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compendate in G1 + G1.add_edge(u, 7) + assert _consistent_PT(u, v, gparams, sparams) + + @pytest.mark.parametrize("graph_type", (nx.Graph, nx.DiGraph)) + def test_cut_inconsistent_labels(self, graph_type): + G1 = graph_type( + [ + (0, 1), + (1, 2), + (10, 0), + (10, 3), + (10, 4), + (10, 5), + (10, 6), + (4, 1), + (5, 3), + ] + ) + G2 = graph_type( + [ + ("a", "b"), + ("b", "c"), + ("k", "a"), + ("k", "d"), + ("k", "e"), + ("k", "f"), + ("k", "g"), + ("e", "b"), + ("f", "d"), + ] + ) + + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + l1.update({6: "green"}) # Change the label of one neighbor of u + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + + u, v = 10, "k" + assert _cut_PT(u, v, gparams, sparams) + + def test_cut_consistent_labels(self): + G1 = nx.Graph( + [ + (0, 1), + (1, 2), + (10, 0), + (10, 3), + (10, 4), + (10, 5), + (10, 6), + (4, 1), + (5, 3), + ] + ) + G2 = nx.Graph( + [ + ("a", "b"), + ("b", "c"), + ("k", "a"), + ("k", "d"), + ("k", "e"), + ("k", "f"), + ("k", "g"), + ("e", "b"), + ("f", "d"), + ] + ) + + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4, 5}, + None, + {6}, + None, + {"e", "f"}, + None, + {"g"}, + None, + ) + + u, v = 10, "k" + assert not _cut_PT(u, v, gparams, sparams) + + def test_cut_same_labels(self): + G1 = nx.Graph( + [ + (0, 1), + (1, 2), + (10, 0), + (10, 3), + (10, 4), + (10, 5), + (10, 6), + (4, 1), + (5, 3), + ] + ) + mapped = {0: "a", 1: "b", 2: "c", 3: "d", 4: "e", 5: "f", 6: "g", 10: "k"} + G2 = nx.relabel_nodes(G1, mapped) + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4, 5}, + None, + {6}, + None, + {"e", "f"}, + None, + {"g"}, + None, + ) + + u, v = 10, "k" + assert not _cut_PT(u, v, gparams, sparams) + + # Change intersection between G1[u] and T1, so it's not the same as the one between G2[v] and T2 + G1.remove_edge(u, 4) + assert _cut_PT(u, v, gparams, sparams) + + # Compensate in G2 + G2.remove_edge(v, mapped[4]) + assert not _cut_PT(u, v, gparams, sparams) + + # Change intersection between G2[v] and T2_tilde, so it's not the same as the one between G1[u] and T1_tilde + G2.remove_edge(v, mapped[6]) + assert _cut_PT(u, v, gparams, sparams) + + # Compensate in G1 + G1.remove_edge(u, 6) + assert not _cut_PT(u, v, gparams, sparams) + + # Add disconnected nodes, which will form the new Ti_out + G1.add_nodes_from([6, 7, 8]) + G2.add_nodes_from(["g", "y", "z"]) + sparams.T1_tilde.update({6, 7, 8}) + sparams.T2_tilde.update({"g", "y", "z"}) + + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + + assert not _cut_PT(u, v, gparams, sparams) + + # Add some new nodes to the mapping + sparams.mapping.update({6: "g", 7: "y"}) + sparams.reverse_mapping.update({"g": 6, "y": 7}) + + # Add more nodes to T1, T2. + G1.add_edges_from([(6, 20), (7, 20), (6, 21)]) + G2.add_edges_from([("g", "i"), ("g", "j"), ("y", "j")]) + + sparams.mapping.update({20: "j", 21: "i"}) + sparams.reverse_mapping.update({"j": 20, "i": 21}) + sparams.T1.update({20, 21}) + sparams.T2.update({"i", "j"}) + sparams.T1_tilde.difference_update({6, 7}) + sparams.T2_tilde.difference_update({"g", "y"}) + + assert not _cut_PT(u, v, gparams, sparams) + + # Add nodes from the new T1 and T2, as neighbors of u and v respectively + G1.add_edges_from([(u, 20), (u, 21)]) + G2.add_edges_from([(v, "i"), (v, "j")]) + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + + assert not _cut_PT(u, v, gparams, sparams) + + # Change the edges, maintaining the G1[u]-T1 intersection + G1.remove_edge(u, 20) + G1.add_edge(u, 4) + assert not _cut_PT(u, v, gparams, sparams) + + # Connect u to 8 which is still in T1_tilde + G1.add_edge(u, 8) + assert _cut_PT(u, v, gparams, sparams) + + # Same for v and z, so that inters(G1[u], T1out) == inters(G2[v], T2out) + G2.add_edge(v, "z") + assert not _cut_PT(u, v, gparams, sparams) + + def test_cut_different_labels(self): + G1 = nx.Graph( + [ + (0, 1), + (1, 2), + (1, 14), + (0, 4), + (1, 5), + (2, 6), + (3, 7), + (3, 6), + (4, 10), + (4, 9), + (6, 10), + (20, 9), + (20, 15), + (20, 12), + (20, 11), + (12, 13), + (11, 13), + (20, 8), + (20, 3), + (20, 5), + (20, 0), + ] + ) + mapped = { + 0: "a", + 1: "b", + 2: "c", + 3: "d", + 4: "e", + 5: "f", + 6: "g", + 7: "h", + 8: "i", + 9: "j", + 10: "k", + 11: "l", + 12: "m", + 13: "n", + 14: "o", + 15: "p", + 20: "x", + } + G2 = nx.relabel_nodes(G1, mapped) + + l1 = {n: "none" for n in G1.nodes()} + l2 = {} + + l1.update( + { + 9: "blue", + 15: "blue", + 12: "blue", + 11: "green", + 3: "green", + 8: "red", + 0: "red", + 5: "yellow", + } + ) + l2.update({mapped[n]: l for n, l in l1.items()}) + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4, 5, 6, 7, 14}, + None, + {9, 10, 15, 12, 11, 13, 8}, + None, + {"e", "f", "g", "h", "o"}, + None, + {"j", "k", "l", "m", "n", "i", "p"}, + None, + ) + + u, v = 20, "x" + assert not _cut_PT(u, v, gparams, sparams) + + # Change the orientation of the labels on neighbors of u compared to neighbors of v. Leave the structure intact + l1.update({9: "red"}) + assert _cut_PT(u, v, gparams, sparams) + + # compensate in G2 + l2.update({mapped[9]: "red"}) + assert not _cut_PT(u, v, gparams, sparams) + + # Change the intersection of G1[u] and T1 + G1.add_edge(u, 4) + assert _cut_PT(u, v, gparams, sparams) + + # Same for G2[v] and T2 + G2.add_edge(v, mapped[4]) + assert not _cut_PT(u, v, gparams, sparams) + + # Change the intersection of G2[v] and T2_tilde + G2.remove_edge(v, mapped[8]) + assert _cut_PT(u, v, gparams, sparams) + + # Same for G1[u] and T1_tilde + G1.remove_edge(u, 8) + assert not _cut_PT(u, v, gparams, sparams) + + # Place 8 and mapped[8] in T1 and T2 respectively, by connecting it to covered nodes + G1.add_edge(8, 3) + G2.add_edge(mapped[8], mapped[3]) + sparams.T1.add(8) + sparams.T2.add(mapped[8]) + sparams.T1_tilde.remove(8) + sparams.T2_tilde.remove(mapped[8]) + + assert not _cut_PT(u, v, gparams, sparams) + + # Remove neighbor of u from T1 + G1.remove_node(5) + l1.pop(5) + sparams.T1.remove(5) + assert _cut_PT(u, v, gparams, sparams) + + # Same in G2 + G2.remove_node(mapped[5]) + l2.pop(mapped[5]) + sparams.T2.remove(mapped[5]) + assert not _cut_PT(u, v, gparams, sparams) + + def test_feasibility_same_labels(self): + G1 = nx.Graph( + [ + (0, 1), + (1, 2), + (1, 14), + (0, 4), + (1, 5), + (2, 6), + (3, 7), + (3, 6), + (4, 10), + (4, 9), + (6, 10), + (20, 9), + (20, 15), + (20, 12), + (20, 11), + (12, 13), + (11, 13), + (20, 8), + (20, 2), + (20, 5), + (20, 0), + ] + ) + mapped = { + 0: "a", + 1: "b", + 2: "c", + 3: "d", + 4: "e", + 5: "f", + 6: "g", + 7: "h", + 8: "i", + 9: "j", + 10: "k", + 11: "l", + 12: "m", + 13: "n", + 14: "o", + 15: "p", + 20: "x", + } + G2 = nx.relabel_nodes(G1, mapped) + + l1 = {n: "blue" for n in G1.nodes()} + l2 = {mapped[n]: "blue" for n in G1.nodes()} + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4, 5, 6, 7, 14}, + None, + {9, 10, 15, 12, 11, 13, 8}, + None, + {"e", "f", "g", "h", "o"}, + None, + {"j", "k", "l", "m", "n", "i", "p"}, + None, + ) + + u, v = 20, "x" + assert not _cut_PT(u, v, gparams, sparams) + + # Change structure in G2 such that, ONLY consistency is harmed + G2.remove_edge(mapped[20], mapped[2]) + G2.add_edge(mapped[20], mapped[3]) + + # Consistency check fails, while the cutting rules are satisfied! + assert not _cut_PT(u, v, gparams, sparams) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compensate in G1 and make it consistent + G1.remove_edge(20, 2) + G1.add_edge(20, 3) + assert not _cut_PT(u, v, gparams, sparams) + assert _consistent_PT(u, v, gparams, sparams) + + # ONLY fail the cutting check + G2.add_edge(v, mapped[10]) + assert _cut_PT(u, v, gparams, sparams) + assert _consistent_PT(u, v, gparams, sparams) + + def test_feasibility_different_labels(self): + G1 = nx.Graph( + [ + (0, 1), + (1, 2), + (1, 14), + (0, 4), + (1, 5), + (2, 6), + (3, 7), + (3, 6), + (4, 10), + (4, 9), + (6, 10), + (20, 9), + (20, 15), + (20, 12), + (20, 11), + (12, 13), + (11, 13), + (20, 8), + (20, 2), + (20, 5), + (20, 0), + ] + ) + mapped = { + 0: "a", + 1: "b", + 2: "c", + 3: "d", + 4: "e", + 5: "f", + 6: "g", + 7: "h", + 8: "i", + 9: "j", + 10: "k", + 11: "l", + 12: "m", + 13: "n", + 14: "o", + 15: "p", + 20: "x", + } + G2 = nx.relabel_nodes(G1, mapped) + + l1 = {n: "none" for n in G1.nodes()} + l2 = {} + + l1.update( + { + 9: "blue", + 15: "blue", + 12: "blue", + 11: "green", + 2: "green", + 8: "red", + 0: "red", + 5: "yellow", + } + ) + l2.update({mapped[n]: l for n, l in l1.items()}) + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4, 5, 6, 7, 14}, + None, + {9, 10, 15, 12, 11, 13, 8}, + None, + {"e", "f", "g", "h", "o"}, + None, + {"j", "k", "l", "m", "n", "i", "p"}, + None, + ) + + u, v = 20, "x" + assert not _cut_PT(u, v, gparams, sparams) + + # Change structure in G2 such that, ONLY consistency is harmed + G2.remove_edge(mapped[20], mapped[2]) + G2.add_edge(mapped[20], mapped[3]) + l2.update({mapped[3]: "green"}) + + # Consistency check fails, while the cutting rules are satisfied! + assert not _cut_PT(u, v, gparams, sparams) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compensate in G1 and make it consistent + G1.remove_edge(20, 2) + G1.add_edge(20, 3) + l1.update({3: "green"}) + assert not _cut_PT(u, v, gparams, sparams) + assert _consistent_PT(u, v, gparams, sparams) + + # ONLY fail the cutting check + l1.update({5: "red"}) + assert _cut_PT(u, v, gparams, sparams) + assert _consistent_PT(u, v, gparams, sparams) + + +class TestMultiGraphISOFeasibility: + def test_const_covered_neighbors(self): + G1 = nx.MultiGraph( + [(0, 1), (0, 1), (1, 2), (3, 0), (3, 0), (3, 0), (3, 2), (3, 2)] + ) + G2 = nx.MultiGraph( + [ + ("a", "b"), + ("a", "b"), + ("b", "c"), + ("k", "a"), + ("k", "a"), + ("k", "a"), + ("k", "c"), + ("k", "c"), + ] + ) + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c"}, + {"a": 0, "b": 1, "c": 2}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 3, "k" + assert _consistent_PT(u, v, gparams, sparams) + + def test_const_no_covered_neighbors(self): + G1 = nx.MultiGraph([(0, 1), (0, 1), (1, 2), (3, 4), (3, 4), (3, 5)]) + G2 = nx.MultiGraph([("a", "b"), ("b", "c"), ("k", "w"), ("k", "w"), ("k", "z")]) + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c"}, + {"a": 0, "b": 1, "c": 2}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 3, "k" + assert _consistent_PT(u, v, gparams, sparams) + + def test_const_mixed_covered_uncovered_neighbors(self): + G1 = nx.MultiGraph( + [(0, 1), (1, 2), (3, 0), (3, 0), (3, 0), (3, 2), (3, 2), (3, 4), (3, 5)] + ) + G2 = nx.MultiGraph( + [ + ("a", "b"), + ("b", "c"), + ("k", "a"), + ("k", "a"), + ("k", "a"), + ("k", "c"), + ("k", "c"), + ("k", "w"), + ("k", "z"), + ] + ) + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c"}, + {"a": 0, "b": 1, "c": 2}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 3, "k" + assert _consistent_PT(u, v, gparams, sparams) + + def test_const_fail_cases(self): + G1 = nx.MultiGraph( + [ + (0, 1), + (1, 2), + (10, 0), + (10, 0), + (10, 0), + (10, 3), + (10, 3), + (10, 4), + (10, 5), + (10, 6), + (10, 6), + (4, 1), + (5, 3), + ] + ) + mapped = {0: "a", 1: "b", 2: "c", 3: "d", 4: "e", 5: "f", 6: "g", 10: "k"} + G2 = nx.relabel_nodes(G1, mapped) + + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 10, "k" + assert _consistent_PT(u, v, gparams, sparams) + + # Delete one uncovered neighbor of u. Notice how it still passes the test. Two reasons for this: + # 1. If u, v had different degrees from the beginning, they wouldn't be selected as candidates in the first + # place. + # 2. Even if they are selected, consistency is basically 1-look-ahead, meaning that we take into consideration + # the relation of the candidates with their mapped neighbors. The node we deleted is not a covered neighbor. + # Such nodes will be checked by the cut_PT function, which is basically the 2-look-ahead, checking the + # relation of the candidates with T1, T2 (in which belongs the node we just deleted). + G1.remove_node(6) + assert _consistent_PT(u, v, gparams, sparams) + + # Add one more covered neighbor of u in G1 + G1.add_edge(u, 2) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compensate in G2 + G2.add_edge(v, "c") + assert _consistent_PT(u, v, gparams, sparams) + + # Add one more covered neighbor of v in G2 + G2.add_edge(v, "x") + G1.add_node(7) + sparams.mapping.update({7: "x"}) + sparams.reverse_mapping.update({"x": 7}) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compendate in G1 + G1.add_edge(u, 7) + assert _consistent_PT(u, v, gparams, sparams) + + # Delete an edge between u and a covered neighbor + G1.remove_edges_from([(u, 0), (u, 0)]) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compensate in G2 + G2.remove_edges_from([(v, mapped[0]), (v, mapped[0])]) + assert _consistent_PT(u, v, gparams, sparams) + + # Remove an edge between v and a covered neighbor + G2.remove_edge(v, mapped[3]) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compensate in G1 + G1.remove_edge(u, 3) + assert _consistent_PT(u, v, gparams, sparams) + + def test_cut_same_labels(self): + G1 = nx.MultiGraph( + [ + (0, 1), + (1, 2), + (10, 0), + (10, 0), + (10, 0), + (10, 3), + (10, 3), + (10, 4), + (10, 4), + (10, 5), + (10, 5), + (10, 5), + (10, 5), + (10, 6), + (10, 6), + (4, 1), + (5, 3), + ] + ) + mapped = {0: "a", 1: "b", 2: "c", 3: "d", 4: "e", 5: "f", 6: "g", 10: "k"} + G2 = nx.relabel_nodes(G1, mapped) + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4, 5}, + None, + {6}, + None, + {"e", "f"}, + None, + {"g"}, + None, + ) + + u, v = 10, "k" + assert not _cut_PT(u, v, gparams, sparams) + + # Remove one of the multiple edges between u and a neighbor + G1.remove_edge(u, 4) + assert _cut_PT(u, v, gparams, sparams) + + # Compensate in G2 + G1.remove_edge(u, 4) + G2.remove_edges_from([(v, mapped[4]), (v, mapped[4])]) + assert not _cut_PT(u, v, gparams, sparams) + + # Change intersection between G2[v] and T2_tilde, so it's not the same as the one between G1[u] and T1_tilde + G2.remove_edge(v, mapped[6]) + assert _cut_PT(u, v, gparams, sparams) + + # Compensate in G1 + G1.remove_edge(u, 6) + assert not _cut_PT(u, v, gparams, sparams) + + # Add more edges between u and neighbor which belongs in T1_tilde + G1.add_edges_from([(u, 5), (u, 5), (u, 5)]) + assert _cut_PT(u, v, gparams, sparams) + + # Compensate in G2 + G2.add_edges_from([(v, mapped[5]), (v, mapped[5]), (v, mapped[5])]) + assert not _cut_PT(u, v, gparams, sparams) + + # Add disconnected nodes, which will form the new Ti_out + G1.add_nodes_from([6, 7, 8]) + G2.add_nodes_from(["g", "y", "z"]) + G1.add_edges_from([(u, 6), (u, 6), (u, 6), (u, 8)]) + G2.add_edges_from([(v, "g"), (v, "g"), (v, "g"), (v, "z")]) + + sparams.T1_tilde.update({6, 7, 8}) + sparams.T2_tilde.update({"g", "y", "z"}) + + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + + assert not _cut_PT(u, v, gparams, sparams) + + # Add some new nodes to the mapping + sparams.mapping.update({6: "g", 7: "y"}) + sparams.reverse_mapping.update({"g": 6, "y": 7}) + + # Add more nodes to T1, T2. + G1.add_edges_from([(6, 20), (7, 20), (6, 21)]) + G2.add_edges_from([("g", "i"), ("g", "j"), ("y", "j")]) + + sparams.T1.update({20, 21}) + sparams.T2.update({"i", "j"}) + sparams.T1_tilde.difference_update({6, 7}) + sparams.T2_tilde.difference_update({"g", "y"}) + + assert not _cut_PT(u, v, gparams, sparams) + + # Remove some edges + G2.remove_edge(v, "g") + assert _cut_PT(u, v, gparams, sparams) + + G1.remove_edge(u, 6) + G1.add_edge(u, 8) + G2.add_edge(v, "z") + assert not _cut_PT(u, v, gparams, sparams) + + # Add nodes from the new T1 and T2, as neighbors of u and v respectively + G1.add_edges_from([(u, 20), (u, 20), (u, 20), (u, 21)]) + G2.add_edges_from([(v, "i"), (v, "i"), (v, "i"), (v, "j")]) + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + + assert not _cut_PT(u, v, gparams, sparams) + + # Change the edges + G1.remove_edge(u, 20) + G1.add_edge(u, 4) + assert _cut_PT(u, v, gparams, sparams) + + G2.remove_edge(v, "i") + G2.add_edge(v, mapped[4]) + assert not _cut_PT(u, v, gparams, sparams) + + def test_cut_different_labels(self): + G1 = nx.MultiGraph( + [ + (0, 1), + (0, 1), + (1, 2), + (1, 2), + (1, 14), + (0, 4), + (1, 5), + (2, 6), + (3, 7), + (3, 6), + (4, 10), + (4, 9), + (6, 10), + (20, 9), + (20, 9), + (20, 9), + (20, 15), + (20, 15), + (20, 12), + (20, 11), + (20, 11), + (20, 11), + (12, 13), + (11, 13), + (20, 8), + (20, 8), + (20, 3), + (20, 3), + (20, 5), + (20, 5), + (20, 5), + (20, 0), + (20, 0), + (20, 0), + ] + ) + mapped = { + 0: "a", + 1: "b", + 2: "c", + 3: "d", + 4: "e", + 5: "f", + 6: "g", + 7: "h", + 8: "i", + 9: "j", + 10: "k", + 11: "l", + 12: "m", + 13: "n", + 14: "o", + 15: "p", + 20: "x", + } + G2 = nx.relabel_nodes(G1, mapped) + + l1 = {n: "none" for n in G1.nodes()} + l2 = {} + + l1.update( + { + 9: "blue", + 15: "blue", + 12: "blue", + 11: "green", + 3: "green", + 8: "red", + 0: "red", + 5: "yellow", + } + ) + l2.update({mapped[n]: l for n, l in l1.items()}) + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4, 5, 6, 7, 14}, + None, + {9, 10, 15, 12, 11, 13, 8}, + None, + {"e", "f", "g", "h", "o"}, + None, + {"j", "k", "l", "m", "n", "i", "p"}, + None, + ) + + u, v = 20, "x" + assert not _cut_PT(u, v, gparams, sparams) + + # Change the orientation of the labels on neighbors of u compared to neighbors of v. Leave the structure intact + l1.update({9: "red"}) + assert _cut_PT(u, v, gparams, sparams) + + # compensate in G2 + l2.update({mapped[9]: "red"}) + assert not _cut_PT(u, v, gparams, sparams) + + # Change the intersection of G1[u] and T1 + G1.add_edge(u, 4) + assert _cut_PT(u, v, gparams, sparams) + + # Same for G2[v] and T2 + G2.add_edge(v, mapped[4]) + assert not _cut_PT(u, v, gparams, sparams) + + # Delete one from the multiple edges + G2.remove_edge(v, mapped[8]) + assert _cut_PT(u, v, gparams, sparams) + + # Same for G1[u] and T1_tilde + G1.remove_edge(u, 8) + assert not _cut_PT(u, v, gparams, sparams) + + # Place 8 and mapped[8] in T1 and T2 respectively, by connecting it to covered nodes + G1.add_edges_from([(8, 3), (8, 3), (8, u)]) + G2.add_edges_from([(mapped[8], mapped[3]), (mapped[8], mapped[3])]) + sparams.T1.add(8) + sparams.T2.add(mapped[8]) + sparams.T1_tilde.remove(8) + sparams.T2_tilde.remove(mapped[8]) + + assert _cut_PT(u, v, gparams, sparams) + + # Fix uneven edges + G1.remove_edge(8, u) + assert not _cut_PT(u, v, gparams, sparams) + + # Remove neighbor of u from T1 + G1.remove_node(5) + l1.pop(5) + sparams.T1.remove(5) + assert _cut_PT(u, v, gparams, sparams) + + # Same in G2 + G2.remove_node(mapped[5]) + l2.pop(mapped[5]) + sparams.T2.remove(mapped[5]) + assert not _cut_PT(u, v, gparams, sparams) + + def test_feasibility_same_labels(self): + G1 = nx.MultiGraph( + [ + (0, 1), + (0, 1), + (1, 2), + (1, 2), + (1, 14), + (0, 4), + (1, 5), + (2, 6), + (3, 7), + (3, 6), + (4, 10), + (4, 9), + (6, 10), + (20, 9), + (20, 9), + (20, 9), + (20, 15), + (20, 15), + (20, 12), + (20, 11), + (20, 11), + (20, 11), + (12, 13), + (11, 13), + (20, 8), + (20, 8), + (20, 3), + (20, 3), + (20, 5), + (20, 5), + (20, 5), + (20, 0), + (20, 0), + (20, 0), + ] + ) + mapped = { + 0: "a", + 1: "b", + 2: "c", + 3: "d", + 4: "e", + 5: "f", + 6: "g", + 7: "h", + 8: "i", + 9: "j", + 10: "k", + 11: "l", + 12: "m", + 13: "n", + 14: "o", + 15: "p", + 20: "x", + } + G2 = nx.relabel_nodes(G1, mapped) + l1 = {n: "blue" for n in G1.nodes()} + l2 = {mapped[n]: "blue" for n in G1.nodes()} + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4, 5, 6, 7, 14}, + None, + {9, 10, 15, 12, 11, 13, 8}, + None, + {"e", "f", "g", "h", "o"}, + None, + {"j", "k", "l", "m", "n", "i", "p"}, + None, + ) + + u, v = 20, "x" + assert not _cut_PT(u, v, gparams, sparams) + + # Change structure in G2 such that, ONLY consistency is harmed + G2.remove_edges_from([(mapped[20], mapped[3]), (mapped[20], mapped[3])]) + G2.add_edges_from([(mapped[20], mapped[2]), (mapped[20], mapped[2])]) + + # Consistency check fails, while the cutting rules are satisfied! + assert not _cut_PT(u, v, gparams, sparams) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compensate in G1 and make it consistent + G1.remove_edges_from([(20, 3), (20, 3)]) + G1.add_edges_from([(20, 2), (20, 2)]) + assert not _cut_PT(u, v, gparams, sparams) + assert _consistent_PT(u, v, gparams, sparams) + + # ONLY fail the cutting check + G2.add_edges_from([(v, mapped[10])] * 5) + assert _cut_PT(u, v, gparams, sparams) + assert _consistent_PT(u, v, gparams, sparams) + + # Pass all tests + G1.add_edges_from([(u, 10)] * 5) + assert not _cut_PT(u, v, gparams, sparams) + assert _consistent_PT(u, v, gparams, sparams) + + def test_feasibility_different_labels(self): + G1 = nx.MultiGraph( + [ + (0, 1), + (0, 1), + (1, 2), + (1, 2), + (1, 14), + (0, 4), + (1, 5), + (2, 6), + (3, 7), + (3, 6), + (4, 10), + (4, 9), + (6, 10), + (20, 9), + (20, 9), + (20, 9), + (20, 15), + (20, 15), + (20, 12), + (20, 11), + (20, 11), + (20, 11), + (12, 13), + (11, 13), + (20, 8), + (20, 8), + (20, 2), + (20, 2), + (20, 5), + (20, 5), + (20, 5), + (20, 0), + (20, 0), + (20, 0), + ] + ) + mapped = { + 0: "a", + 1: "b", + 2: "c", + 3: "d", + 4: "e", + 5: "f", + 6: "g", + 7: "h", + 8: "i", + 9: "j", + 10: "k", + 11: "l", + 12: "m", + 13: "n", + 14: "o", + 15: "p", + 20: "x", + } + G2 = nx.relabel_nodes(G1, mapped) + l1 = {n: "none" for n in G1.nodes()} + l2 = {} + + l1.update( + { + 9: "blue", + 15: "blue", + 12: "blue", + 11: "green", + 2: "green", + 8: "red", + 0: "red", + 5: "yellow", + } + ) + l2.update({mapped[n]: l for n, l in l1.items()}) + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4, 5, 6, 7, 14}, + None, + {9, 10, 15, 12, 11, 13, 8}, + None, + {"e", "f", "g", "h", "o"}, + None, + {"j", "k", "l", "m", "n", "i", "p"}, + None, + ) + + u, v = 20, "x" + assert not _cut_PT(u, v, gparams, sparams) + + # Change structure in G2 such that, ONLY consistency is harmed + G2.remove_edges_from([(mapped[20], mapped[2]), (mapped[20], mapped[2])]) + G2.add_edges_from([(mapped[20], mapped[3]), (mapped[20], mapped[3])]) + l2.update({mapped[3]: "green"}) + + # Consistency check fails, while the cutting rules are satisfied! + assert not _cut_PT(u, v, gparams, sparams) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compensate in G1 and make it consistent + G1.remove_edges_from([(20, 2), (20, 2)]) + G1.add_edges_from([(20, 3), (20, 3)]) + l1.update({3: "green"}) + assert not _cut_PT(u, v, gparams, sparams) + assert _consistent_PT(u, v, gparams, sparams) + + # ONLY fail the cutting check + l1.update({5: "red"}) + assert _cut_PT(u, v, gparams, sparams) + assert _consistent_PT(u, v, gparams, sparams) + + +class TestDiGraphISOFeasibility: + def test_const_covered_neighbors(self): + G1 = nx.DiGraph([(0, 1), (1, 2), (0, 3), (2, 3)]) + G2 = nx.DiGraph([("a", "b"), ("b", "c"), ("a", "k"), ("c", "k")]) + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c"}, + {"a": 0, "b": 1, "c": 2}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 3, "k" + assert _consistent_PT(u, v, gparams, sparams) + + def test_const_no_covered_neighbors(self): + G1 = nx.DiGraph([(0, 1), (1, 2), (3, 4), (3, 5)]) + G2 = nx.DiGraph([("a", "b"), ("b", "c"), ("k", "w"), ("k", "z")]) + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c"}, + {"a": 0, "b": 1, "c": 2}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 3, "k" + assert _consistent_PT(u, v, gparams, sparams) + + def test_const_mixed_covered_uncovered_neighbors(self): + G1 = nx.DiGraph([(0, 1), (1, 2), (3, 0), (3, 2), (3, 4), (3, 5)]) + G2 = nx.DiGraph( + [("a", "b"), ("b", "c"), ("k", "a"), ("k", "c"), ("k", "w"), ("k", "z")] + ) + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c"}, + {"a": 0, "b": 1, "c": 2}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 3, "k" + assert _consistent_PT(u, v, gparams, sparams) + + def test_const_fail_cases(self): + G1 = nx.DiGraph( + [ + (0, 1), + (2, 1), + (10, 0), + (10, 3), + (10, 4), + (5, 10), + (10, 6), + (1, 4), + (5, 3), + ] + ) + G2 = nx.DiGraph( + [ + ("a", "b"), + ("c", "b"), + ("k", "a"), + ("k", "d"), + ("k", "e"), + ("f", "k"), + ("k", "g"), + ("b", "e"), + ("f", "d"), + ] + ) + gparams = _GraphParameters(G1, G2, None, None, None, None, None) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + u, v = 10, "k" + assert _consistent_PT(u, v, gparams, sparams) + + # Delete one uncovered neighbor of u. Notice how it still passes the + # test. Two reasons for this: + # 1. If u, v had different degrees from the beginning, they wouldn't + # be selected as candidates in the first place. + # 2. Even if they are selected, consistency is basically + # 1-look-ahead, meaning that we take into consideration the + # relation of the candidates with their mapped neighbors. + # The node we deleted is not a covered neighbor. + # Such nodes will be checked by the cut_PT function, which is + # basically the 2-look-ahead, checking the relation of the + # candidates with T1, T2 (in which belongs the node we just deleted). + G1.remove_node(6) + assert _consistent_PT(u, v, gparams, sparams) + + # Add one more covered neighbor of u in G1 + G1.add_edge(u, 2) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compensate in G2 + G2.add_edge(v, "c") + assert _consistent_PT(u, v, gparams, sparams) + + # Add one more covered neighbor of v in G2 + G2.add_edge(v, "x") + G1.add_node(7) + sparams.mapping.update({7: "x"}) + sparams.reverse_mapping.update({"x": 7}) + assert not _consistent_PT(u, v, gparams, sparams) + + # Compensate in G1 + G1.add_edge(u, 7) + assert _consistent_PT(u, v, gparams, sparams) + + def test_cut_inconsistent_labels(self): + G1 = nx.DiGraph( + [ + (0, 1), + (2, 1), + (10, 0), + (10, 3), + (10, 4), + (5, 10), + (10, 6), + (1, 4), + (5, 3), + ] + ) + G2 = nx.DiGraph( + [ + ("a", "b"), + ("c", "b"), + ("k", "a"), + ("k", "d"), + ("k", "e"), + ("f", "k"), + ("k", "g"), + ("b", "e"), + ("f", "d"), + ] + ) + + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + l1.update({5: "green"}) # Change the label of one neighbor of u + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + None, + None, + None, + None, + None, + None, + None, + None, + ) + + u, v = 10, "k" + assert _cut_PT(u, v, gparams, sparams) + + def test_cut_consistent_labels(self): + G1 = nx.DiGraph( + [ + (0, 1), + (2, 1), + (10, 0), + (10, 3), + (10, 4), + (5, 10), + (10, 6), + (1, 4), + (5, 3), + ] + ) + G2 = nx.DiGraph( + [ + ("a", "b"), + ("c", "b"), + ("k", "a"), + ("k", "d"), + ("k", "e"), + ("f", "k"), + ("k", "g"), + ("b", "e"), + ("f", "d"), + ] + ) + + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4}, + {5, 10}, + {6}, + None, + {"e"}, + {"f", "k"}, + {"g"}, + None, + ) + + u, v = 10, "k" + assert not _cut_PT(u, v, gparams, sparams) + + def test_cut_same_labels(self): + G1 = nx.DiGraph( + [ + (0, 1), + (2, 1), + (10, 0), + (10, 3), + (10, 4), + (5, 10), + (10, 6), + (1, 4), + (5, 3), + ] + ) + mapped = {0: "a", 1: "b", 2: "c", 3: "d", 4: "e", 5: "f", 6: "g", 10: "k"} + G2 = nx.relabel_nodes(G1, mapped) + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4}, + {5, 10}, + {6}, + None, + {"e"}, + {"f", "k"}, + {"g"}, + None, + ) + + u, v = 10, "k" + assert not _cut_PT(u, v, gparams, sparams) + + # Change intersection between G1[u] and T1_out, so it's not the same as the one between G2[v] and T2_out + G1.remove_edge(u, 4) + assert _cut_PT(u, v, gparams, sparams) + + # Compensate in G2 + G2.remove_edge(v, mapped[4]) + assert not _cut_PT(u, v, gparams, sparams) + + # Change intersection between G1[u] and T1_in, so it's not the same as the one between G2[v] and T2_in + G1.remove_edge(5, u) + assert _cut_PT(u, v, gparams, sparams) + + # Compensate in G2 + G2.remove_edge(mapped[5], v) + assert not _cut_PT(u, v, gparams, sparams) + + # Change intersection between G2[v] and T2_tilde, so it's not the same as the one between G1[u] and T1_tilde + G2.remove_edge(v, mapped[6]) + assert _cut_PT(u, v, gparams, sparams) + + # Compensate in G1 + G1.remove_edge(u, 6) + assert not _cut_PT(u, v, gparams, sparams) + + # Add disconnected nodes, which will form the new Ti_tilde + G1.add_nodes_from([6, 7, 8]) + G2.add_nodes_from(["g", "y", "z"]) + sparams.T1_tilde.update({6, 7, 8}) + sparams.T2_tilde.update({"g", "y", "z"}) + + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + + assert not _cut_PT(u, v, gparams, sparams) + + def test_cut_different_labels(self): + G1 = nx.DiGraph( + [ + (0, 1), + (1, 2), + (14, 1), + (0, 4), + (1, 5), + (2, 6), + (3, 7), + (3, 6), + (10, 4), + (4, 9), + (6, 10), + (20, 9), + (20, 15), + (20, 12), + (20, 11), + (12, 13), + (11, 13), + (20, 8), + (20, 3), + (20, 5), + (0, 20), + ] + ) + mapped = { + 0: "a", + 1: "b", + 2: "c", + 3: "d", + 4: "e", + 5: "f", + 6: "g", + 7: "h", + 8: "i", + 9: "j", + 10: "k", + 11: "l", + 12: "m", + 13: "n", + 14: "o", + 15: "p", + 20: "x", + } + G2 = nx.relabel_nodes(G1, mapped) + + l1 = {n: "none" for n in G1.nodes()} + l2 = {} + + l1.update( + { + 9: "blue", + 15: "blue", + 12: "blue", + 11: "green", + 3: "green", + 8: "red", + 0: "red", + 5: "yellow", + } + ) + l2.update({mapped[n]: l for n, l in l1.items()}) + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c", 3: "d"}, + {"a": 0, "b": 1, "c": 2, "d": 3}, + {4, 5, 6, 7, 20}, + {14, 20}, + {9, 10, 15, 12, 11, 13, 8}, + None, + {"e", "f", "g", "x"}, + {"o", "x"}, + {"j", "k", "l", "m", "n", "i", "p"}, + None, + ) + + u, v = 20, "x" + assert not _cut_PT(u, v, gparams, sparams) + + # Change the orientation of the labels on neighbors of u compared to neighbors of v. Leave the structure intact + l1.update({9: "red"}) + assert _cut_PT(u, v, gparams, sparams) + + # compensate in G2 + l2.update({mapped[9]: "red"}) + assert not _cut_PT(u, v, gparams, sparams) + + # Change the intersection of G1[u] and T1_out + G1.add_edge(u, 4) + assert _cut_PT(u, v, gparams, sparams) + + # Same for G2[v] and T2_out + G2.add_edge(v, mapped[4]) + assert not _cut_PT(u, v, gparams, sparams) + + # Change the intersection of G1[u] and T1_in + G1.add_edge(u, 14) + assert _cut_PT(u, v, gparams, sparams) + + # Same for G2[v] and T2_in + G2.add_edge(v, mapped[14]) + assert not _cut_PT(u, v, gparams, sparams) + + # Change the intersection of G2[v] and T2_tilde + G2.remove_edge(v, mapped[8]) + assert _cut_PT(u, v, gparams, sparams) + + # Same for G1[u] and T1_tilde + G1.remove_edge(u, 8) + assert not _cut_PT(u, v, gparams, sparams) + + # Place 8 and mapped[8] in T1 and T2 respectively, by connecting it to covered nodes + G1.add_edge(8, 3) + G2.add_edge(mapped[8], mapped[3]) + sparams.T1.add(8) + sparams.T2.add(mapped[8]) + sparams.T1_tilde.remove(8) + sparams.T2_tilde.remove(mapped[8]) + + assert not _cut_PT(u, v, gparams, sparams) + + # Remove neighbor of u from T1 + G1.remove_node(5) + l1.pop(5) + sparams.T1.remove(5) + assert _cut_PT(u, v, gparams, sparams) + + # Same in G2 + G2.remove_node(mapped[5]) + l2.pop(mapped[5]) + sparams.T2.remove(mapped[5]) + assert not _cut_PT(u, v, gparams, sparams) + + def test_predecessor_T1_in_fail(self): + G1 = nx.DiGraph( + [(0, 1), (0, 3), (4, 0), (1, 5), (5, 2), (3, 6), (4, 6), (6, 5)] + ) + mapped = {0: "a", 1: "b", 2: "c", 3: "d", 4: "e", 5: "f", 6: "g"} + G2 = nx.relabel_nodes(G1, mapped) + l1 = {n: "blue" for n in G1.nodes()} + l2 = {n: "blue" for n in G2.nodes()} + + gparams = _GraphParameters( + G1, G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), None + ) + sparams = _StateParameters( + {0: "a", 1: "b", 2: "c"}, + {"a": 0, "b": 1, "c": 2}, + {3, 5}, + {4, 5}, + {6}, + None, + {"d", "f"}, + {"f"}, # mapped[4] is missing from T2_in + {"g"}, + None, + ) + + u, v = 6, "g" + assert _cut_PT(u, v, gparams, sparams) + + sparams.T2_in.add("e") + assert not _cut_PT(u, v, gparams, sparams) + + +class TestGraphTinoutUpdating: + edges = [ + (1, 3), + (2, 3), + (3, 4), + (4, 9), + (4, 5), + (3, 9), + (5, 8), + (5, 7), + (8, 7), + (6, 7), + ] + mapped = { + 0: "x", + 1: "a", + 2: "b", + 3: "c", + 4: "d", + 5: "e", + 6: "f", + 7: "g", + 8: "h", + 9: "i", + } + G1 = nx.Graph() + G1.add_edges_from(edges) + G1.add_node(0) + G2 = nx.relabel_nodes(G1, mapping=mapped) + + def test_updating(self): + G2_degree = dict(self.G2.degree) + gparams, sparams = _initialize_parameters(self.G1, self.G2, G2_degree) + m, m_rev, T1, _, T1_tilde, _, T2, _, T2_tilde, _ = sparams + + # Add node to the mapping + m[4] = self.mapped[4] + m_rev[self.mapped[4]] = 4 + _update_Tinout(4, self.mapped[4], gparams, sparams) + + assert T1 == {3, 5, 9} + assert T2 == {"c", "i", "e"} + assert T1_tilde == {0, 1, 2, 6, 7, 8} + assert T2_tilde == {"x", "a", "b", "f", "g", "h"} + + # Add node to the mapping + m[5] = self.mapped[5] + m_rev.update({self.mapped[5]: 5}) + _update_Tinout(5, self.mapped[5], gparams, sparams) + + assert T1 == {3, 9, 8, 7} + assert T2 == {"c", "i", "h", "g"} + assert T1_tilde == {0, 1, 2, 6} + assert T2_tilde == {"x", "a", "b", "f"} + + # Add node to the mapping + m[6] = self.mapped[6] + m_rev.update({self.mapped[6]: 6}) + _update_Tinout(6, self.mapped[6], gparams, sparams) + + assert T1 == {3, 9, 8, 7} + assert T2 == {"c", "i", "h", "g"} + assert T1_tilde == {0, 1, 2} + assert T2_tilde == {"x", "a", "b"} + + # Add node to the mapping + m[3] = self.mapped[3] + m_rev.update({self.mapped[3]: 3}) + _update_Tinout(3, self.mapped[3], gparams, sparams) + + assert T1 == {1, 2, 9, 8, 7} + assert T2 == {"a", "b", "i", "h", "g"} + assert T1_tilde == {0} + assert T2_tilde == {"x"} + + # Add node to the mapping + m[0] = self.mapped[0] + m_rev.update({self.mapped[0]: 0}) + _update_Tinout(0, self.mapped[0], gparams, sparams) + + assert T1 == {1, 2, 9, 8, 7} + assert T2 == {"a", "b", "i", "h", "g"} + assert T1_tilde == set() + assert T2_tilde == set() + + def test_restoring(self): + m = {0: "x", 3: "c", 4: "d", 5: "e", 6: "f"} + m_rev = {"x": 0, "c": 3, "d": 4, "e": 5, "f": 6} + + T1 = {1, 2, 7, 9, 8} + T2 = {"a", "b", "g", "i", "h"} + T1_tilde = set() + T2_tilde = set() + + gparams = _GraphParameters(self.G1, self.G2, {}, {}, {}, {}, {}) + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) + + # Remove a node from the mapping + m.pop(0) + m_rev.pop("x") + _restore_Tinout(0, self.mapped[0], gparams, sparams) + + assert T1 == {1, 2, 7, 9, 8} + assert T2 == {"a", "b", "g", "i", "h"} + assert T1_tilde == {0} + assert T2_tilde == {"x"} + + # Remove a node from the mapping + m.pop(6) + m_rev.pop("f") + _restore_Tinout(6, self.mapped[6], gparams, sparams) + + assert T1 == {1, 2, 7, 9, 8} + assert T2 == {"a", "b", "g", "i", "h"} + assert T1_tilde == {0, 6} + assert T2_tilde == {"x", "f"} + + # Remove a node from the mapping + m.pop(3) + m_rev.pop("c") + _restore_Tinout(3, self.mapped[3], gparams, sparams) + + assert T1 == {7, 9, 8, 3} + assert T2 == {"g", "i", "h", "c"} + assert T1_tilde == {0, 6, 1, 2} + assert T2_tilde == {"x", "f", "a", "b"} + + # Remove a node from the mapping + m.pop(5) + m_rev.pop("e") + _restore_Tinout(5, self.mapped[5], gparams, sparams) + + assert T1 == {9, 3, 5} + assert T2 == {"i", "c", "e"} + assert T1_tilde == {0, 6, 1, 2, 7, 8} + assert T2_tilde == {"x", "f", "a", "b", "g", "h"} + + # Remove a node from the mapping + m.pop(4) + m_rev.pop("d") + _restore_Tinout(4, self.mapped[4], gparams, sparams) + + assert T1 == set() + assert T2 == set() + assert T1_tilde == set(self.G1.nodes()) + assert T2_tilde == set(self.G2.nodes()) + + +class TestDiGraphTinoutUpdating: + edges = [ + (1, 3), + (3, 2), + (3, 4), + (4, 9), + (4, 5), + (3, 9), + (5, 8), + (5, 7), + (8, 7), + (7, 6), + ] + mapped = { + 0: "x", + 1: "a", + 2: "b", + 3: "c", + 4: "d", + 5: "e", + 6: "f", + 7: "g", + 8: "h", + 9: "i", + } + G1 = nx.DiGraph(edges) + G1.add_node(0) + G2 = nx.relabel_nodes(G1, mapping=mapped) + + def test_updating(self): + G2_degree = { + n: (in_degree, out_degree) + for (n, in_degree), (_, out_degree) in zip( + self.G2.in_degree, self.G2.out_degree + ) + } + gparams, sparams = _initialize_parameters(self.G1, self.G2, G2_degree) + m, m_rev, T1_out, T1_in, T1_tilde, _, T2_out, T2_in, T2_tilde, _ = sparams + + # Add node to the mapping + m[4] = self.mapped[4] + m_rev[self.mapped[4]] = 4 + _update_Tinout(4, self.mapped[4], gparams, sparams) + + assert T1_out == {5, 9} + assert T1_in == {3} + assert T2_out == {"i", "e"} + assert T2_in == {"c"} + assert T1_tilde == {0, 1, 2, 6, 7, 8} + assert T2_tilde == {"x", "a", "b", "f", "g", "h"} + + # Add node to the mapping + m[5] = self.mapped[5] + m_rev[self.mapped[5]] = 5 + _update_Tinout(5, self.mapped[5], gparams, sparams) + + assert T1_out == {9, 8, 7} + assert T1_in == {3} + assert T2_out == {"i", "g", "h"} + assert T2_in == {"c"} + assert T1_tilde == {0, 1, 2, 6} + assert T2_tilde == {"x", "a", "b", "f"} + + # Add node to the mapping + m[6] = self.mapped[6] + m_rev[self.mapped[6]] = 6 + _update_Tinout(6, self.mapped[6], gparams, sparams) + + assert T1_out == {9, 8, 7} + assert T1_in == {3, 7} + assert T2_out == {"i", "g", "h"} + assert T2_in == {"c", "g"} + assert T1_tilde == {0, 1, 2} + assert T2_tilde == {"x", "a", "b"} + + # Add node to the mapping + m[3] = self.mapped[3] + m_rev[self.mapped[3]] = 3 + _update_Tinout(3, self.mapped[3], gparams, sparams) + + assert T1_out == {9, 8, 7, 2} + assert T1_in == {7, 1} + assert T2_out == {"i", "g", "h", "b"} + assert T2_in == {"g", "a"} + assert T1_tilde == {0} + assert T2_tilde == {"x"} + + # Add node to the mapping + m[0] = self.mapped[0] + m_rev[self.mapped[0]] = 0 + _update_Tinout(0, self.mapped[0], gparams, sparams) + + assert T1_out == {9, 8, 7, 2} + assert T1_in == {7, 1} + assert T2_out == {"i", "g", "h", "b"} + assert T2_in == {"g", "a"} + assert T1_tilde == set() + assert T2_tilde == set() + + def test_restoring(self): + m = {0: "x", 3: "c", 4: "d", 5: "e", 6: "f"} + m_rev = {"x": 0, "c": 3, "d": 4, "e": 5, "f": 6} + + T1_out = {2, 7, 9, 8} + T1_in = {1, 7} + T2_out = {"b", "g", "i", "h"} + T2_in = {"a", "g"} + T1_tilde = set() + T2_tilde = set() + + gparams = _GraphParameters(self.G1, self.G2, {}, {}, {}, {}, {}) + sparams = _StateParameters( + m, m_rev, T1_out, T1_in, T1_tilde, None, T2_out, T2_in, T2_tilde, None + ) + + # Remove a node from the mapping + m.pop(0) + m_rev.pop("x") + _restore_Tinout_Di(0, self.mapped[0], gparams, sparams) + + assert T1_out == {2, 7, 9, 8} + assert T1_in == {1, 7} + assert T2_out == {"b", "g", "i", "h"} + assert T2_in == {"a", "g"} + assert T1_tilde == {0} + assert T2_tilde == {"x"} + + # Remove a node from the mapping + m.pop(6) + m_rev.pop("f") + _restore_Tinout_Di(6, self.mapped[6], gparams, sparams) + + assert T1_out == {2, 9, 8, 7} + assert T1_in == {1} + assert T2_out == {"b", "i", "h", "g"} + assert T2_in == {"a"} + assert T1_tilde == {0, 6} + assert T2_tilde == {"x", "f"} + + # Remove a node from the mapping + m.pop(3) + m_rev.pop("c") + _restore_Tinout_Di(3, self.mapped[3], gparams, sparams) + + assert T1_out == {9, 8, 7} + assert T1_in == {3} + assert T2_out == {"i", "h", "g"} + assert T2_in == {"c"} + assert T1_tilde == {0, 6, 1, 2} + assert T2_tilde == {"x", "f", "a", "b"} + + # Remove a node from the mapping + m.pop(5) + m_rev.pop("e") + _restore_Tinout_Di(5, self.mapped[5], gparams, sparams) + + assert T1_out == {9, 5} + assert T1_in == {3} + assert T2_out == {"i", "e"} + assert T2_in == {"c"} + assert T1_tilde == {0, 6, 1, 2, 8, 7} + assert T2_tilde == {"x", "f", "a", "b", "h", "g"} + + # Remove a node from the mapping + m.pop(4) + m_rev.pop("d") + _restore_Tinout_Di(4, self.mapped[4], gparams, sparams) + + assert T1_out == set() + assert T1_in == set() + assert T2_out == set() + assert T2_in == set() + assert T1_tilde == set(self.G1.nodes()) + assert T2_tilde == set(self.G2.nodes()) diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_vf2userfunc.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_vf2userfunc.py new file mode 100644 index 00000000..b44f4588 --- /dev/null +++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/isomorphism/tests/test_vf2userfunc.py @@ -0,0 +1,200 @@ +""" +Tests for VF2 isomorphism algorithm for weighted graphs. +""" + +import math +from operator import eq + +import networkx as nx +import networkx.algorithms.isomorphism as iso + + +def test_simple(): + # 16 simple tests + w = "weight" + edges = [(0, 0, 1), (0, 0, 1.5), (0, 1, 2), (1, 0, 3)] + for g1 in [nx.Graph(), nx.DiGraph(), nx.MultiGraph(), nx.MultiDiGraph()]: + g1.add_weighted_edges_from(edges) + g2 = g1.subgraph(g1.nodes()) + if g1.is_multigraph(): + em = iso.numerical_multiedge_match("weight", 1) + else: + em = iso.numerical_edge_match("weight", 1) + assert nx.is_isomorphic(g1, g2, edge_match=em) + + for mod1, mod2 in [(False, True), (True, False), (True, True)]: + # mod1 tests a regular edge + # mod2 tests a selfloop + if g2.is_multigraph(): + if mod1: + data1 = {0: {"weight": 10}} + if mod2: + data2 = {0: {"weight": 1}, 1: {"weight": 2.5}} + else: + if mod1: + data1 = {"weight": 10} + if mod2: + data2 = {"weight": 2.5} + + g2 = g1.subgraph(g1.nodes()).copy() + if mod1: + if not g1.is_directed(): + g2._adj[1][0] = data1 + g2._adj[0][1] = data1 + else: + g2._succ[1][0] = data1 + g2._pred[0][1] = data1 + if mod2: + if not g1.is_directed(): + g2._adj[0][0] = data2 + else: + g2._succ[0][0] = data2 + g2._pred[0][0] = data2 + + assert not nx.is_isomorphic(g1, g2, edge_match=em) + + +def test_weightkey(): + g1 = nx.DiGraph() + g2 = nx.DiGraph() + + g1.add_edge("A", "B", weight=1) + g2.add_edge("C", "D", weight=0) + + assert nx.is_isomorphic(g1, g2) + em = iso.numerical_edge_match("nonexistent attribute", 1) + assert nx.is_isomorphic(g1, g2, edge_match=em) + em = iso.numerical_edge_match("weight", 1) + assert not nx.is_isomorphic(g1, g2, edge_match=em) + + g2 = nx.DiGraph() + g2.add_edge("C", "D") + assert nx.is_isomorphic(g1, g2, edge_match=em) + + +class TestNodeMatch_Graph: + def setup_method(self): + self.g1 = nx.Graph() + self.g2 = nx.Graph() + self.build() + + def build(self): + self.nm = iso.categorical_node_match("color", "") + self.em = iso.numerical_edge_match("weight", 1) + + self.g1.add_node("A", color="red") + self.g2.add_node("C", color="blue") + + self.g1.add_edge("A", "B", weight=1) + self.g2.add_edge("C", "D", weight=1) + + def test_noweight_nocolor(self): + assert nx.is_isomorphic(self.g1, self.g2) + + def test_color1(self): + assert not nx.is_isomorphic(self.g1, self.g2, node_match=self.nm) + + def test_color2(self): + self.g1.nodes["A"]["color"] = "blue" + assert nx.is_isomorphic(self.g1, self.g2, node_match=self.nm) + + def test_weight1(self): + assert nx.is_isomorphic(self.g1, self.g2, edge_match=self.em) + + def test_weight2(self): + self.g1.add_edge("A", "B", weight=2) + assert not nx.is_isomorphic(self.g1, self.g2, edge_match=self.em) + + def test_colorsandweights1(self): + iso = nx.is_isomorphic(self.g1, self.g2, node_match=self.nm, edge_match=self.em) + assert not iso + + def test_colorsandweights2(self): + self.g1.nodes["A"]["color"] = "blue" + iso = nx.is_isomorphic(self.g1, self.g2, node_match=self.nm, edge_match=self.em) + assert iso + + def test_colorsandweights3(self): + # make the weights disagree + self.g1.add_edge("A", "B", weight=2) + assert not nx.is_isomorphic( + self.g1, self.g2, node_match=self.nm, edge_match=self.em + ) + + +class TestEdgeMatch_MultiGraph: + def setup_method(self): + self.g1 = nx.MultiGraph() + self.g2 = nx.MultiGraph() + self.GM = iso.MultiGraphMatcher + self.build() + + def build(self): + g1 = self.g1 + g2 = self.g2 + + # We will assume integer weights only. + g1.add_edge("A", "B", color="green", weight=0, size=0.5) + g1.add_edge("A", "B", color="red", weight=1, size=0.35) + g1.add_edge("A", "B", color="red", weight=2, size=0.65) + + g2.add_edge("C", "D", color="green", weight=1, size=0.5) + g2.add_edge("C", "D", color="red", weight=0, size=0.45) + g2.add_edge("C", "D", color="red", weight=2, size=0.65) + + if g1.is_multigraph(): + self.em = iso.numerical_multiedge_match("weight", 1) + self.emc = iso.categorical_multiedge_match("color", "") + self.emcm = iso.categorical_multiedge_match(["color", "weight"], ["", 1]) + self.emg1 = iso.generic_multiedge_match("color", "red", eq) + self.emg2 = iso.generic_multiedge_match( + ["color", "weight", "size"], + ["red", 1, 0.5], + [eq, eq, math.isclose], + ) + else: + self.em = iso.numerical_edge_match("weight", 1) + self.emc = iso.categorical_edge_match("color", "") + self.emcm = iso.categorical_edge_match(["color", "weight"], ["", 1]) + self.emg1 = iso.generic_multiedge_match("color", "red", eq) + self.emg2 = iso.generic_edge_match( + ["color", "weight", "size"], + ["red", 1, 0.5], + [eq, eq, math.isclose], + ) + + def test_weights_only(self): + assert nx.is_isomorphic(self.g1, self.g2, edge_match=self.em) + + def test_colors_only(self): + gm = self.GM(self.g1, self.g2, edge_match=self.emc) + assert gm.is_isomorphic() + + def test_colorsandweights(self): + gm = self.GM(self.g1, self.g2, edge_match=self.emcm) + assert not gm.is_isomorphic() + + def test_generic1(self): + gm = self.GM(self.g1, self.g2, edge_match=self.emg1) + assert gm.is_isomorphic() + + def test_generic2(self): + gm = self.GM(self.g1, self.g2, edge_match=self.emg2) + assert not gm.is_isomorphic() + + +class TestEdgeMatch_DiGraph(TestNodeMatch_Graph): + def setup_method(self): + TestNodeMatch_Graph.setup_method(self) + self.g1 = nx.DiGraph() + self.g2 = nx.DiGraph() + self.build() + + +class TestEdgeMatch_MultiDiGraph(TestEdgeMatch_MultiGraph): + def setup_method(self): + TestEdgeMatch_MultiGraph.setup_method(self) + self.g1 = nx.MultiDiGraph() + self.g2 = nx.MultiDiGraph() + self.GM = iso.MultiDiGraphMatcher + self.build() |