diff options
| author | Konstantinos Petridis <petridkon@gmail.com> | 2022-10-05 01:58:07 +0300 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2022-10-04 15:58:07 -0700 |
| commit | a796f526c7ce6a7f182aee4b81b8499feabe1a45 (patch) | |
| tree | 0928ebd1b666800ab5d1c37745c64a5565b30df5 | |
| parent | 9443a42ec41244cc661b55238a68c504229decc8 (diff) | |
| download | networkx-a796f526c7ce6a7f182aee4b81b8499feabe1a45.tar.gz | |
VF2++ for Directed Graphs (#5972)
Modify vf2pp implementation to support directed graphs. Updates all helper
functions and state/parameter objects to account for in/out degree.
Includes other changes such as renaming the keyword argument from
node_labels to node_label to better reflect the fact that the label kwarg expects
a single value.
Co-authored-by: Ross Barnowski <rossbar@berkeley.edu>
Co-authored-by: Dan Schult <dschult@colgate.edu>
10 files changed, 1835 insertions, 166 deletions
diff --git a/networkx/algorithms/isomorphism/tests/vf2pp/test_Ti_computing.py b/networkx/algorithms/isomorphism/tests/vf2pp/test_Ti_computing.py index a1b834f0..f548fca0 100644 --- a/networkx/algorithms/isomorphism/tests/vf2pp/test_Ti_computing.py +++ b/networkx/algorithms/isomorphism/tests/vf2pp/test_Ti_computing.py @@ -6,11 +6,12 @@ from networkx.algorithms.isomorphism.vf2pp import ( ) from networkx.algorithms.isomorphism.vf2pp_helpers.state import ( _restore_Tinout, + _restore_Tinout_Di, _update_Tinout, ) -class TestTinoutUpdating: +class TestGraphTinoutUpdating: edges = [ (1, 3), (2, 3), @@ -41,8 +42,9 @@ class TestTinoutUpdating: G2 = nx.relabel_nodes(G1, mapping=mapped) def test_updating(self): - gparams, sparams = _initialize_parameters(self.G1, self.G2) - m, m_rev, T1, T1_tilde, T2, T2_tilde = sparams + 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] @@ -104,7 +106,9 @@ class TestTinoutUpdating: T2_tilde = set() gparams = _GraphParameters(self.G1, self.G2, {}, {}, {}, {}, {}) - sparams = _StateParameters(m, m_rev, T1, T1_tilde, T2, T2_tilde) + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) # Remove a node from the mapping m.pop(0) @@ -155,3 +159,179 @@ class TestTinoutUpdating: 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/networkx/algorithms/isomorphism/tests/vf2pp/test_candidates.py b/networkx/algorithms/isomorphism/tests/vf2pp/test_candidates.py index 9ddc3ec1..a233930b 100644 --- a/networkx/algorithms/isomorphism/tests/vf2pp/test_candidates.py +++ b/networkx/algorithms/isomorphism/tests/vf2pp/test_candidates.py @@ -4,11 +4,13 @@ import utils import networkx as nx from networkx.algorithms.isomorphism.vf2pp import _GraphParameters, _StateParameters -from networkx.algorithms.isomorphism.vf2pp_helpers.candidates import _find_candidates +from networkx.algorithms.isomorphism.vf2pp_helpers.candidates import ( + _find_candidates, + _find_candidates_Di, +) -class TestCandidateSelection: - G1 = nx.Graph() +class TestGraphCandidateSelection: G1_edges = [ (1, 2), (1, 4), @@ -36,21 +38,23 @@ class TestCandidateSelection: 9: "i", } - G1.add_edges_from(G1_edges) - G1.add_node(0) - G2 = nx.relabel_nodes(G1, mapped) - def test_no_covered_neighbors_no_labels(self): - l1 = dict(self.G1.nodes(data="label", default=-1)) - l2 = dict(self.G2.nodes(data="label", default=-1)) + 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( - self.G1, - self.G2, + G1, + G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), - nx.utils.groups({node: degree for node, degree in self.G2.degree()}), + nx.utils.groups({node: degree for node, degree in G2.degree()}), ) m = {9: self.mapped[9], 1: self.mapped[1]} @@ -61,14 +65,16 @@ class TestCandidateSelection: T2 = {"g", "h", "b", "d", "e"} T2_tilde = {"x", "c", "f"} - sparams = _StateParameters(m, m_rev, T1, T1_tilde, T2, T2_tilde) + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) u = 3 - candidates = _find_candidates(u, gparams, sparams) + candidates = _find_candidates(u, gparams, sparams, G1_degree) assert candidates == {self.mapped[u]} u = 0 - candidates = _find_candidates(u, gparams, sparams) + candidates = _find_candidates(u, gparams, sparams, G1_degree) assert candidates == {self.mapped[u]} m.pop(9) @@ -79,10 +85,12 @@ class TestCandidateSelection: T2 = {"g", "h", "b", "d", "e", "f"} T2_tilde = {"x", "c", "g", "h", "i"} - sparams = _StateParameters(m, m_rev, T1, T1_tilde, T2, T2_tilde) + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) u = 7 - candidates = _find_candidates(u, gparams, sparams) + candidates = _find_candidates(u, gparams, sparams, G1_degree) assert candidates == { self.mapped[u], self.mapped[8], @@ -91,31 +99,37 @@ class TestCandidateSelection: } 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( - self.G1, - dict(zip(self.G1, itertools.cycle(utils.labels_different))), + G1, + dict(zip(G1, itertools.cycle(utils.labels_different))), "label", ) nx.set_node_attributes( - self.G2, + G2, dict( zip( - [self.mapped[n] for n in self.G1], + [self.mapped[n] for n in G1], itertools.cycle(utils.labels_different), ) ), "label", ) - l1 = dict(self.G1.nodes(data="label", default=-1)) - l2 = dict(self.G2.nodes(data="label", default=-1)) + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) gparams = _GraphParameters( - self.G1, - self.G2, + G1, + G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), - nx.utils.groups({node: degree for node, degree in self.G2.degree()}), + nx.utils.groups({node: degree for node, degree in G2.degree()}), ) m = {9: self.mapped[9], 1: self.mapped[1]} @@ -126,32 +140,34 @@ class TestCandidateSelection: T2 = {"g", "h", "b", "d", "e", "f"} T2_tilde = {"x", "c"} - sparams = _StateParameters(m, m_rev, T1, T1_tilde, T2, T2_tilde) + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) u = 3 - candidates = _find_candidates(u, gparams, sparams) + candidates = _find_candidates(u, gparams, sparams, G1_degree) assert candidates == {self.mapped[u]} u = 0 - candidates = _find_candidates(u, gparams, sparams) + candidates = _find_candidates(u, gparams, sparams, G1_degree) assert candidates == {self.mapped[u]} # Change label of disconnected node - self.G1.nodes[u]["label"] = "blue" - l1 = dict(self.G1.nodes(data="label", default=-1)) - l2 = dict(self.G2.nodes(data="label", default=-1)) + G1.nodes[u]["label"] = "blue" + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) gparams = _GraphParameters( - self.G1, - self.G2, + G1, + G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), - nx.utils.groups({node: degree for node, degree in self.G2.degree()}), + nx.utils.groups({node: degree for node, degree in G2.degree()}), ) # No candidate - candidates = _find_candidates(u, gparams, sparams) + candidates = _find_candidates(u, gparams, sparams, G1_degree) assert candidates == set() m.pop(9) @@ -162,120 +178,620 @@ class TestCandidateSelection: T2 = {"b", "d", "e", "f"} T2_tilde = {"x", "c", "g", "h", "i"} - sparams = _StateParameters(m, m_rev, T1, T1_tilde, T2, T2_tilde) + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) u = 7 - candidates = _find_candidates(u, gparams, sparams) + candidates = _find_candidates(u, gparams, sparams, G1_degree) assert candidates == {self.mapped[u]} - self.G1.nodes[8]["label"] = self.G1.nodes[7]["label"] - self.G2.nodes[self.mapped[8]]["label"] = self.G1.nodes[7]["label"] - l1 = dict(self.G1.nodes(data="label", default=-1)) - l2 = dict(self.G2.nodes(data="label", default=-1)) + 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( - self.G1, - self.G2, + G1, + G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), - nx.utils.groups({node: degree for node, degree in self.G2.degree()}), + nx.utils.groups({node: degree for node, degree in G2.degree()}), ) - candidates = _find_candidates(u, gparams, sparams) + candidates = _find_candidates(u, gparams, sparams, G1_degree) assert candidates == {self.mapped[u], self.mapped[8]} def test_covered_neighbors_no_labels(self): - l1 = dict(self.G1.nodes(data=None, default=-1)) - l2 = dict(self.G2.nodes(data=None, default=-1)) + 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( - self.G1, - self.G2, + G1, + G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), - nx.utils.groups({node: degree for node, degree in self.G2.degree()}), + nx.utils.groups({node: degree for node, degree in 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_out = {0, 3} + T1_tilde = {0, 3} T2 = {"g", "h", "b", "d", "e", "f"} - T2_out = {"x", "c"} + T2_tilde = {"x", "c"} - sparams = _StateParameters(m, m_rev, T1, T1_out, T2, T2_out) + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) u = 5 - candidates = _find_candidates(u, gparams, sparams) + candidates = _find_candidates(u, gparams, sparams, G1_degree) assert candidates == {self.mapped[u]} u = 6 - candidates = _find_candidates(u, gparams, sparams) + 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( - self.G1, - dict(zip(self.G1, itertools.cycle(utils.labels_different))), + G1, + dict(zip(G1, itertools.cycle(utils.labels_different))), "label", ) nx.set_node_attributes( - self.G2, + G2, dict( zip( - [self.mapped[n] for n in self.G1], + [self.mapped[n] for n in G1], itertools.cycle(utils.labels_different), ) ), "label", ) - l1 = dict(self.G1.nodes(data="label", default=-1)) - l2 = dict(self.G2.nodes(data="label", default=-1)) + l1 = dict(G1.nodes(data="label", default=-1)) + l2 = dict(G2.nodes(data="label", default=-1)) gparams = _GraphParameters( - self.G1, - self.G2, + G1, + G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), - nx.utils.groups({node: degree for node, degree in self.G2.degree()}), + nx.utils.groups({node: degree for node, degree in 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_out = {0, 3} + T1_tilde = {0, 3} T2 = {"g", "h", "b", "d", "e", "f"} - T2_out = {"x", "c"} + T2_tilde = {"x", "c"} - sparams = _StateParameters(m, m_rev, T1, T1_out, T2, T2_out) + sparams = _StateParameters( + m, m_rev, T1, None, T1_tilde, None, T2, None, T2_tilde, None + ) u = 5 - candidates = _find_candidates(u, gparams, sparams) + candidates = _find_candidates(u, gparams, sparams, G1_degree) assert candidates == {self.mapped[u]} u = 6 - candidates = _find_candidates(u, gparams, sparams) + candidates = _find_candidates(u, gparams, sparams, G1_degree) assert candidates == {self.mapped[u]} # Assign to 2, the same label as 6 - self.G1.nodes[2]["label"] = self.G1.nodes[u]["label"] - self.G2.nodes[self.mapped[2]]["label"] = self.G1.nodes[u]["label"] - l1 = dict(self.G1.nodes(data="label", default=-1)) - l2 = dict(self.G2.nodes(data="label", default=-1)) + 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( - self.G1, - self.G2, + G1, + G2, l1, l2, nx.utils.groups(l1), nx.utils.groups(l2), - nx.utils.groups({node: degree for node, degree in self.G2.degree()}), + nx.utils.groups({node: degree for node, degree in G2.degree()}), ) - candidates = _find_candidates(u, gparams, sparams) + 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, itertools.cycle(utils.labels_different))), + "label", + ) + nx.set_node_attributes( + G2, + dict( + zip( + [self.mapped[n] for n in G1], + itertools.cycle(utils.labels_different), + ) + ), + "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, itertools.cycle(utils.labels_different))), + "label", + ) + nx.set_node_attributes( + G2, + dict( + zip( + [self.mapped[n] for n in G1], + itertools.cycle(utils.labels_different), + ) + ), + "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} diff --git a/networkx/algorithms/isomorphism/tests/vf2pp/test_feasibility.py b/networkx/algorithms/isomorphism/tests/vf2pp/test_feasibility.py index b6abcec6..f96c6bf7 100644 --- a/networkx/algorithms/isomorphism/tests/vf2pp/test_feasibility.py +++ b/networkx/algorithms/isomorphism/tests/vf2pp/test_feasibility.py @@ -1,3 +1,5 @@ +import pytest + import networkx as nx from networkx.algorithms.isomorphism.vf2pp import ( _feasibility, @@ -16,7 +18,16 @@ class TestGraphISOFeasibility: 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 + {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) @@ -26,7 +37,16 @@ class TestGraphISOFeasibility: 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 + {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) @@ -38,7 +58,16 @@ class TestGraphISOFeasibility: ) 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 + {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) @@ -78,17 +107,25 @@ class TestGraphISOFeasibility: 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). + # 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) @@ -111,8 +148,9 @@ class TestGraphISOFeasibility: G1.add_edge(u, 7) assert _consistent_PT(u, v, gparams, sparams) - def test_cut_inconsistent_labels(self): - G1 = nx.Graph( + @pytest.mark.parametrize("graph_type", (nx.Graph, nx.DiGraph)) + def test_cut_inconsistent_labels(self, graph_type): + G1 = graph_type( [ (0, 1), (1, 2), @@ -125,7 +163,7 @@ class TestGraphISOFeasibility: (5, 3), ] ) - G2 = nx.Graph( + G2 = graph_type( [ ("a", "b"), ("b", "c"), @@ -153,6 +191,10 @@ class TestGraphISOFeasibility: None, None, None, + None, + None, + None, + None, ) u, v = 10, "k" @@ -196,9 +238,13 @@ class TestGraphISOFeasibility: {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" @@ -230,9 +276,13 @@ class TestGraphISOFeasibility: {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" @@ -380,9 +430,13 @@ class TestGraphISOFeasibility: {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" @@ -491,9 +545,13 @@ class TestGraphISOFeasibility: {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" @@ -589,9 +647,13 @@ class TestGraphISOFeasibility: {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" @@ -638,7 +700,16 @@ class TestMultiGraphISOFeasibility: ) 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 + {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) @@ -648,7 +719,16 @@ class TestMultiGraphISOFeasibility: 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 + {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) @@ -672,7 +752,16 @@ class TestMultiGraphISOFeasibility: ) 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 + {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) @@ -706,6 +795,10 @@ class TestMultiGraphISOFeasibility: None, None, None, + None, + None, + None, + None, ) u, v = 10, "k" assert _consistent_PT(u, v, gparams, sparams) @@ -789,9 +882,13 @@ class TestMultiGraphISOFeasibility: {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" @@ -967,9 +1064,13 @@ class TestMultiGraphISOFeasibility: {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" @@ -1094,9 +1195,13 @@ class TestMultiGraphISOFeasibility: {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" @@ -1209,9 +1314,13 @@ class TestMultiGraphISOFeasibility: {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" @@ -1237,3 +1346,485 @@ class TestMultiGraphISOFeasibility: 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 = dict() + + 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) diff --git a/networkx/algorithms/isomorphism/tests/vf2pp/test_precheck.py b/networkx/algorithms/isomorphism/tests/vf2pp/test_precheck.py index 7f2733d8..4885458f 100644 --- a/networkx/algorithms/isomorphism/tests/vf2pp/test_precheck.py +++ b/networkx/algorithms/isomorphism/tests/vf2pp/test_precheck.py @@ -94,6 +94,6 @@ class TestPreCheck: G2, dict(zip(G2, itertools.cycle(colors2[::-1]))), "label" ) - assert not vf2pp_is_isomorphic(G1, G2, node_labels="label") + assert not vf2pp_is_isomorphic(G1, G2, node_label="label") G2.nodes[3]["label"] = "blue" - assert vf2pp_is_isomorphic(G1, G2, node_labels="label") + assert vf2pp_is_isomorphic(G1, G2, node_label="label") diff --git a/networkx/algorithms/isomorphism/tests/vf2pp/test_vf2pp.py b/networkx/algorithms/isomorphism/tests/vf2pp/test_vf2pp.py index 1558a5a6..f8f97bea 100644 --- a/networkx/algorithms/isomorphism/tests/vf2pp/test_vf2pp.py +++ b/networkx/algorithms/isomorphism/tests/vf2pp/test_vf2pp.py @@ -8,7 +8,7 @@ from networkx.algorithms.isomorphism.vf2pp import vf2pp_isomorphism class TestAllGraphTypesEdgeCases: - @pytest.mark.parametrize("graph_type", (nx.Graph, nx.MultiGraph)) + @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() @@ -22,13 +22,13 @@ class TestAllGraphTypesEdgeCases: H.add_node(0) assert vf2pp_isomorphism(G, H) == {0: 0} - @pytest.mark.parametrize("graph_type", (nx.Graph, nx.MultiGraph)) + @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)) + @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() @@ -1499,3 +1499,72 @@ class TestMultiGraphISOVF2pp: G1.add_edges_from([(i, i) for i in range(0, 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/networkx/algorithms/isomorphism/vf2pp.py b/networkx/algorithms/isomorphism/vf2pp.py index efc7e086..b2dc602c 100644 --- a/networkx/algorithms/isomorphism/vf2pp.py +++ b/networkx/algorithms/isomorphism/vf2pp.py @@ -37,7 +37,7 @@ Without node labels: >>> import networkx as nx >>> G1 = nx.path_graph(4) >>> G2 = nx.path_graph(4) ->>> nx.vf2pp_is_isomorphic(G1, G2, node_labels=None) +>>> nx.vf2pp_is_isomorphic(G1, G2, node_label=None) True >>> nx.vf2pp_isomorphism(G1, G2, node_label=None) {1: 1, 2: 2, 0: 0, 3: 3} @@ -49,7 +49,7 @@ With node labels: >>> mapped = {1: 1, 2: 2, 3: 3, 0: 0} >>> nx.set_node_attributes(G1, dict(zip(G1, ["blue", "red", "green", "yellow"])), "label") >>> nx.set_node_attributes(G2, dict(zip([mapped[u] for u in G1], ["blue", "red", "green", "yellow"])), "label") ->>> nx.vf2pp_is_isomorphic(G1, G2, node_labels="label") +>>> nx.vf2pp_is_isomorphic(G1, G2, node_label="label") True >>> nx.vf2pp_isomorphism(G1, G2, node_label="label") {1: 1, 2: 2, 0: 0, 3: 3} @@ -59,10 +59,10 @@ import collections import networkx as nx -from .vf2pp_helpers.candidates import _find_candidates +from .vf2pp_helpers.candidates import _find_candidates, _find_candidates_Di from .vf2pp_helpers.feasibility import _feasibility from .vf2pp_helpers.node_ordering import _matching_order -from .vf2pp_helpers.state import _restore_Tinout, _update_Tinout +from .vf2pp_helpers.state import _restore_Tinout, _restore_Tinout_Di, _update_Tinout __all__ = ["vf2pp_isomorphism", "vf2pp_is_isomorphic", "vf2pp_all_isomorphisms"] @@ -78,9 +78,21 @@ _GraphParameters = collections.namedtuple( "G2_nodes_of_degree", ], ) + _StateParameters = collections.namedtuple( "_StateParameters", - ["mapping", "reverse_mapping", "T1", "T1_tilde", "T2", "T2_tilde"], + [ + "mapping", + "reverse_mapping", + "T1", + "T1_in", + "T1_tilde", + "T1_tilde_in", + "T2", + "T2_in", + "T2_tilde", + "T2_tilde_in", + ], ) @@ -95,7 +107,7 @@ def vf2pp_isomorphism(G1, G2, node_label=None, default_label=None): node_label : str, optional The name of the node attribute to be used when comparing nodes. The default is `None`, meaning node attributes are not considered - in the comparison. Any node that doesn't have the `node_labels` + in the comparison. Any node that doesn't have the `node_label` attribute uses `default_label` instead. default_label : scalar @@ -114,7 +126,7 @@ def vf2pp_isomorphism(G1, G2, node_label=None, default_label=None): return None -def vf2pp_is_isomorphic(G1, G2, node_labels=None, default_label=None): +def vf2pp_is_isomorphic(G1, G2, node_label=None, default_label=None): """Examines whether G1 and G2 are isomorphic. Parameters @@ -125,7 +137,7 @@ def vf2pp_is_isomorphic(G1, G2, node_labels=None, default_label=None): node_label : str, optional The name of the node attribute to be used when comparing nodes. The default is `None`, meaning node attributes are not considered - in the comparison. Any node that doesn't have the `node_labels` + in the comparison. Any node that doesn't have the `node_label` attribute uses `default_label` instead. default_label : scalar @@ -137,12 +149,12 @@ def vf2pp_is_isomorphic(G1, G2, node_labels=None, default_label=None): bool True if the two graphs are isomorphic, False otherwise. """ - if vf2pp_isomorphism(G1, G2, node_labels, default_label) is not None: + if vf2pp_isomorphism(G1, G2, node_label, default_label) is not None: return True return False -def vf2pp_all_isomorphisms(G1, G2, node_labels=None, default_label=None): +def vf2pp_all_isomorphisms(G1, G2, node_label=None, default_label=None): """Yields all the possible mappings between G1 and G2. Parameters @@ -153,7 +165,7 @@ def vf2pp_all_isomorphisms(G1, G2, node_labels=None, default_label=None): node_label : str, optional The name of the node attribute to be used when comparing nodes. The default is `None`, meaning node attributes are not considered - in the comparison. Any node that doesn't have the `node_labels` + in the comparison. Any node that doesn't have the `node_label` attribute uses `default_label` instead. default_label : scalar @@ -164,18 +176,40 @@ def vf2pp_all_isomorphisms(G1, G2, node_labels=None, default_label=None): ------ dict Isomorphic mapping between the nodes in `G1` and `G2`. - """ if G1.number_of_nodes() == 0 or G2.number_of_nodes() == 0: return False + # Create the degree dicts based on graph type + if G1.is_directed(): + G1_degree = { + n: (in_degree, out_degree) + for (n, in_degree), (_, out_degree) in zip(G1.in_degree, G1.out_degree) + } + G2_degree = { + n: (in_degree, out_degree) + for (n, in_degree), (_, out_degree) in zip(G2.in_degree, G2.out_degree) + } + else: + G1_degree = dict(G1.degree) + G2_degree = dict(G2.degree) + + if not G1.is_directed(): + find_candidates = _find_candidates + restore_Tinout = _restore_Tinout + else: + find_candidates = _find_candidates_Di + restore_Tinout = _restore_Tinout_Di + # Check that both graphs have the same number of nodes and degree sequence - if not nx.faster_could_be_isomorphic(G1, G2): + if G1.order() != G2.order(): + return False + if sorted(G1_degree.values()) != sorted(G2_degree.values()): return False # Initialize parameters and cache necessary information about degree and labels graph_params, state_params = _initialize_parameters( - G1, G2, node_labels, default_label + G1, G2, G2_degree, node_label, default_label ) # Check if G1 and G2 have the same labels, and that number of nodes per label is equal between the two graphs @@ -187,7 +221,9 @@ def vf2pp_all_isomorphisms(G1, G2, node_labels=None, default_label=None): # Initialize the stack stack = [] - candidates = iter(_find_candidates(node_order[0], graph_params, state_params)) + candidates = iter( + find_candidates(node_order[0], graph_params, state_params, G1_degree) + ) stack.append((node_order[0], candidates)) mapping = state_params.mapping @@ -211,7 +247,7 @@ def vf2pp_all_isomorphisms(G1, G2, node_labels=None, default_label=None): popped_node2 = mapping[popped_node1] mapping.pop(popped_node1) reverse_mapping.pop(popped_node2) - _restore_Tinout(popped_node1, popped_node2, graph_params, state_params) + restore_Tinout(popped_node1, popped_node2, graph_params, state_params) continue if _feasibility(current_node, candidate, graph_params, state_params): @@ -228,7 +264,9 @@ def vf2pp_all_isomorphisms(G1, G2, node_labels=None, default_label=None): _update_Tinout(current_node, candidate, graph_params, state_params) # Append the next node and its candidates to the stack candidates = iter( - _find_candidates(node_order[matching_node], graph_params, state_params) + find_candidates( + node_order[matching_node], graph_params, state_params, G1_degree + ) ) stack.append((node_order[matching_node], candidates)) matching_node += 1 @@ -244,7 +282,7 @@ def _precheck_label_properties(graph_params): return True -def _initialize_parameters(G1, G2, node_labels=None, default_label=-1): +def _initialize_parameters(G1, G2, G2_degree, node_label=None, default_label=-1): """Initializes all the necessary parameters for VF2++ Parameters @@ -279,8 +317,8 @@ def _initialize_parameters(G1, G2, node_labels=None, default_label=-1): T1_out, T2_out: set Ti_out contains all the nodes from Gi, that are neither in the mapping nor in Ti """ - G1_labels = dict(G1.nodes(data=node_labels, default=default_label)) - G2_labels = dict(G2.nodes(data=node_labels, default=default_label)) + G1_labels = dict(G1.nodes(data=node_label, default=default_label)) + G2_labels = dict(G2.nodes(data=node_label, default=default_label)) graph_params = _GraphParameters( G1, @@ -289,11 +327,32 @@ def _initialize_parameters(G1, G2, node_labels=None, default_label=-1): G2_labels, nx.utils.groups(G1_labels), nx.utils.groups(G2_labels), - nx.utils.groups({node: degree for node, degree in G2.degree()}), + nx.utils.groups(G2_degree), ) + T1, T1_in = set(), set() + T2, T2_in = set(), set() + if G1.is_directed(): + T1_tilde, T1_tilde_in = ( + set(G1.nodes()), + set(), + ) # todo: do we need Ti_tilde_in? What nodes does it have? + T2_tilde, T2_tilde_in = set(G2.nodes()), set() + else: + T1_tilde, T1_tilde_in = set(G1.nodes()), set() + T2_tilde, T2_tilde_in = set(G2.nodes()), set() + state_params = _StateParameters( - dict(), dict(), set(), set(G1.nodes()), set(), set(G2.nodes()) + dict(), + dict(), + T1, + T1_in, + T1_tilde, + T1_tilde_in, + T2, + T2_in, + T2_tilde, + T2_tilde_in, ) return graph_params, state_params diff --git a/networkx/algorithms/isomorphism/vf2pp_helpers/candidates.py b/networkx/algorithms/isomorphism/vf2pp_helpers/candidates.py index f8e24ce6..8f6aeb0a 100644 --- a/networkx/algorithms/isomorphism/vf2pp_helpers/candidates.py +++ b/networkx/algorithms/isomorphism/vf2pp_helpers/candidates.py @@ -1,4 +1,6 @@ -def _find_candidates(u, graph_params, state_params): +def _find_candidates( + u, graph_params, state_params, G1_degree +): # todo: make the 4th argument the degree of u """Given node u of G1, finds the candidates of u from G2. Parameters @@ -28,8 +30,8 @@ def _find_candidates(u, graph_params, state_params): Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes that are not in the mapping, but are neighbors of nodes that are. - T1_out, T2_out: set - Ti_out contains all the nodes from Gi, that are neither in the mapping nor in Ti + T1_tilde, T2_tilde: set + Ti_tilde contains all the nodes from Gi, that are neither in the mapping nor in Ti Returns ------- @@ -37,13 +39,13 @@ def _find_candidates(u, graph_params, state_params): The nodes from G2 which are candidates for u. """ G1, G2, G1_labels, _, _, nodes_of_G2Labels, G2_nodes_of_degree = graph_params - mapping, reverse_mapping, _, _, _, T2_out = state_params + mapping, reverse_mapping, _, _, _, _, _, _, T2_tilde, _ = state_params covered_neighbors = [nbr for nbr in G1[u] if nbr in mapping] if not covered_neighbors: candidates = set(nodes_of_G2Labels[G1_labels[u]]) - candidates.intersection_update(G2_nodes_of_degree[G1.degree[u]]) - candidates.intersection_update(T2_out) + candidates.intersection_update(G2_nodes_of_degree[G1_degree[u]]) + candidates.intersection_update(T2_tilde) candidates.difference_update(reverse_mapping) if G1.is_multigraph(): candidates.difference_update( @@ -62,7 +64,56 @@ def _find_candidates(u, graph_params, state_params): common_nodes.intersection_update(G2[mapping[nbr1]]) common_nodes.difference_update(reverse_mapping) - common_nodes.intersection_update(G2_nodes_of_degree[G1.degree[u]]) + common_nodes.intersection_update(G2_nodes_of_degree[G1_degree[u]]) + common_nodes.intersection_update(nodes_of_G2Labels[G1_labels[u]]) + if G1.is_multigraph(): + common_nodes.difference_update( + { + node + for node in common_nodes + if G1.number_of_edges(u, u) != G2.number_of_edges(node, node) + } + ) + return common_nodes + + +def _find_candidates_Di(u, graph_params, state_params, G1_degree): + G1, G2, G1_labels, _, _, nodes_of_G2Labels, G2_nodes_of_degree = graph_params + mapping, reverse_mapping, _, _, _, _, _, _, T2_tilde, _ = state_params + + covered_successors = [succ for succ in G1[u] if succ in mapping] + covered_predecessors = [pred for pred in G1.pred[u] if pred in mapping] + + if not (covered_successors or covered_predecessors): + candidates = set(nodes_of_G2Labels[G1_labels[u]]) + candidates.intersection_update(G2_nodes_of_degree[G1_degree[u]]) + candidates.intersection_update(T2_tilde) + candidates.difference_update(reverse_mapping) + if G1.is_multigraph(): + candidates.difference_update( + { + node + for node in candidates + if G1.number_of_edges(u, u) != G2.number_of_edges(node, node) + } + ) + return candidates + + if covered_successors: + succ1 = covered_successors[0] + common_nodes = set(G2.pred[mapping[succ1]]) + + for succ1 in covered_successors[1:]: + common_nodes.intersection_update(G2.pred[mapping[succ1]]) + else: + pred1 = covered_predecessors.pop() + common_nodes = set(G2[mapping[pred1]]) + + for pred1 in covered_predecessors: + common_nodes.intersection_update(G2[mapping[pred1]]) + + common_nodes.difference_update(reverse_mapping) + common_nodes.intersection_update(G2_nodes_of_degree[G1_degree[u]]) common_nodes.intersection_update(nodes_of_G2Labels[G1_labels[u]]) if G1.is_multigraph(): common_nodes.difference_update( diff --git a/networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py b/networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py index b523f9f1..90e8fe86 100644 --- a/networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py +++ b/networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py @@ -93,17 +93,40 @@ def _cut_PT(u, v, graph_params, state_params): True if we should prune this branch, i.e. the node pair failed the cutting checks. False otherwise. """ G1, G2, G1_labels, G2_labels, _, _, _ = graph_params - _, _, T1, T1_tilde, T2, T2_tilde = state_params + ( + _, + _, + T1, + T1_in, + T1_tilde, + _, + T2, + T2_in, + T2_tilde, + _, + ) = state_params + + u_labels_predecessors, v_labels_predecessors = {}, {} + if G1.is_directed(): + u_labels_predecessors = nx.utils.groups( + {n1: G1_labels[n1] for n1 in G1.pred[u]} + ) + v_labels_predecessors = nx.utils.groups( + {n2: G2_labels[n2] for n2 in G2.pred[v]} + ) + + if set(u_labels_predecessors.keys()) != set(v_labels_predecessors.keys()): + return True - u_labels_neighbors = nx.utils.groups({n1: G1_labels[n1] for n1 in G1[u]}) - v_labels_neighbors = nx.utils.groups({n2: G2_labels[n2] for n2 in G2[v]}) + u_labels_successors = nx.utils.groups({n1: G1_labels[n1] for n1 in G1[u]}) + v_labels_successors = nx.utils.groups({n2: G2_labels[n2] for n2 in G2[v]}) # if the neighbors of u, do not have the same labels as those of v, NOT feasible. - if set(u_labels_neighbors.keys()) != set(v_labels_neighbors.keys()): + if set(u_labels_successors.keys()) != set(v_labels_successors.keys()): return True - for label, G1_nbh in u_labels_neighbors.items(): - G2_nbh = v_labels_neighbors[label] + for label, G1_nbh in u_labels_successors.items(): + G2_nbh = v_labels_successors[label] if G1.is_multigraph(): # Check for every neighbor in the neighborhood, if u-nbr1 has same edges as v-nbr2 @@ -119,6 +142,33 @@ def _cut_PT(u, v, graph_params, state_params): return True if len(T1_tilde.intersection(G1_nbh)) != len(T2_tilde.intersection(G2_nbh)): return True + if G1.is_directed() and len(T1_in.intersection(G1_nbh)) != len( + T2_in.intersection(G2_nbh) + ): + return True + + if not G1.is_directed(): + return False + + for label, G1_pred in u_labels_predecessors.items(): + G2_pred = v_labels_predecessors[label] + + if G1.is_multigraph(): + # Check for every neighbor in the neighborhood, if u-nbr1 has same edges as v-nbr2 + u_pred_edges = sorted(G1.number_of_edges(u, x) for x in G1_pred) + v_pred_edges = sorted(G2.number_of_edges(v, x) for x in G2_pred) + if any( + u_nbr_edges != v_nbr_edges + for u_nbr_edges, v_nbr_edges in zip(u_pred_edges, v_pred_edges) + ): + return True + + if len(T1.intersection(G1_pred)) != len(T2.intersection(G2_pred)): + return True + if len(T1_tilde.intersection(G1_pred)) != len(T2_tilde.intersection(G2_pred)): + return True + if len(T1_in.intersection(G1_pred)) != len(T2_in.intersection(G2_pred)): + return True return False @@ -176,4 +226,22 @@ def _consistent_PT(u, v, graph_params, state_params): v, neighbor ): return False + + if not G1.is_directed(): + return True + + for predecessor in G1.pred[u]: + if predecessor in mapping: + if G1.number_of_edges(u, predecessor) != G2.number_of_edges( + v, mapping[predecessor] + ): + return False + + for predecessor in G2.pred[v]: + if predecessor in reverse_mapping: + if G1.number_of_edges( + u, reverse_mapping[predecessor] + ) != G2.number_of_edges(v, predecessor): + return False + return True diff --git a/networkx/algorithms/isomorphism/vf2pp_helpers/node_ordering.py b/networkx/algorithms/isomorphism/vf2pp_helpers/node_ordering.py index 464010b9..97c5c606 100644 --- a/networkx/algorithms/isomorphism/vf2pp_helpers/node_ordering.py +++ b/networkx/algorithms/isomorphism/vf2pp_helpers/node_ordering.py @@ -31,6 +31,9 @@ def _matching_order(graph_params): if not G1 and not G2: return {} + if G1.is_directed(): + G1 = G1.to_undirected(as_view=True) + V1_unordered = set(G1.nodes()) label_rarity = {label: len(nodes) for label, nodes in nodes_of_G2Labels.items()} used_degrees = {node: 0 for node in G1} diff --git a/networkx/algorithms/isomorphism/vf2pp_helpers/state.py b/networkx/algorithms/isomorphism/vf2pp_helpers/state.py index 93648bc5..27ddac9c 100644 --- a/networkx/algorithms/isomorphism/vf2pp_helpers/state.py +++ b/networkx/algorithms/isomorphism/vf2pp_helpers/state.py @@ -39,21 +39,52 @@ def _update_Tinout(new_node1, new_node2, graph_params, state_params): Ti_out contains all the nodes from Gi, that are neither in the mapping nor in Ti """ G1, G2, _, _, _, _, _ = graph_params - mapping, reverse_mapping, T1, T1_tilde, T2, T2_tilde = state_params + ( + mapping, + reverse_mapping, + T1, + T1_in, + T1_tilde, + T1_tilde_in, + T2, + T2_in, + T2_tilde, + T2_tilde_in, + ) = state_params - uncovered_neighbors_G1 = {nbr for nbr in G1[new_node1] if nbr not in mapping} - uncovered_neighbors_G2 = { - nbr for nbr in G2[new_node2] if nbr not in reverse_mapping + uncovered_successors_G1 = {succ for succ in G1[new_node1] if succ not in mapping} + uncovered_successors_G2 = { + succ for succ in G2[new_node2] if succ not in reverse_mapping } # Add the uncovered neighbors of node1 and node2 in T1 and T2 respectively - T1.update(uncovered_neighbors_G1) - T2.update(uncovered_neighbors_G2) + T1.update(uncovered_successors_G1) + T2.update(uncovered_successors_G2) T1.discard(new_node1) T2.discard(new_node2) - T1_tilde.difference_update(uncovered_neighbors_G1) - T2_tilde.difference_update(uncovered_neighbors_G2) + T1_tilde.difference_update(uncovered_successors_G1) + T2_tilde.difference_update(uncovered_successors_G2) + T1_tilde.discard(new_node1) + T2_tilde.discard(new_node2) + + if not G1.is_directed(): + return + + uncovered_predecessors_G1 = { + pred for pred in G1.pred[new_node1] if pred not in mapping + } + uncovered_predecessors_G2 = { + pred for pred in G2.pred[new_node2] if pred not in reverse_mapping + } + + T1_in.update(uncovered_predecessors_G1) + T2_in.update(uncovered_predecessors_G2) + T1_in.discard(new_node1) + T2_in.discard(new_node2) + + T1_tilde.difference_update(uncovered_predecessors_G1) + T2_tilde.difference_update(uncovered_predecessors_G2) T1_tilde.discard(new_node1) T2_tilde.discard(new_node2) @@ -88,40 +119,141 @@ def _restore_Tinout(popped_node1, popped_node2, graph_params, state_params): Ti contains uncovered neighbors of covered nodes from Gi, i.e. nodes that are not in the mapping, but are neighbors of nodes that are. - T1_out, T2_out: set + T1_tilde, T2_tilde: set Ti_out contains all the nodes from Gi, that are neither in the mapping nor in Ti """ # If the node we want to remove from the mapping, has at least one covered neighbor, add it to T1. G1, G2, _, _, _, _, _ = graph_params - mapping, reverse_mapping, T1, T1_out, T2, T2_out = state_params + ( + mapping, + reverse_mapping, + T1, + T1_in, + T1_tilde, + T1_tilde_in, + T2, + T2_in, + T2_tilde, + T2_tilde_in, + ) = state_params is_added = False - for nbr in G1[popped_node1]: - if nbr in mapping: - T1.add( - popped_node1 - ) # if a neighbor of the excluded node1 is in the mapping, keep node1 in T1 + for neighbor in G1[popped_node1]: + if neighbor in mapping: + # if a neighbor of the excluded node1 is in the mapping, keep node1 in T1 is_added = True - else: # check if its neighbor has another connection with a covered node. If not, only then exclude it from T1 - if any(nbr2 in mapping for nbr2 in G1[nbr]): + T1.add(popped_node1) + else: + # check if its neighbor has another connection with a covered node. If not, only then exclude it from T1 + if any(nbr in mapping for nbr in G1[neighbor]): continue - T1.discard(nbr) - T1_out.add(nbr) + T1.discard(neighbor) + T1_tilde.add(neighbor) - # Case where the node is not present in neither the mapping nor T1. By deffinition it should belong to T1_out + # Case where the node is not present in neither the mapping nor T1. By definition, it should belong to T1_tilde if not is_added: - T1_out.add(popped_node1) + T1_tilde.add(popped_node1) is_added = False - for nbr in G2[popped_node2]: - if nbr in reverse_mapping: - T2.add(popped_node2) + for neighbor in G2[popped_node2]: + if neighbor in reverse_mapping: is_added = True + T2.add(popped_node2) else: - if any(nbr2 in reverse_mapping for nbr2 in G2[nbr]): + if any(nbr in reverse_mapping for nbr in G2[neighbor]): continue - T2.discard(nbr) - T2_out.add(nbr) + T2.discard(neighbor) + T2_tilde.add(neighbor) + + if not is_added: + T2_tilde.add(popped_node2) + + +def _restore_Tinout_Di(popped_node1, popped_node2, graph_params, state_params): + # If the node we want to remove from the mapping, has at least one covered neighbor, add it to T1. + G1, G2, _, _, _, _, _ = graph_params + ( + mapping, + reverse_mapping, + T1, + T1_in, + T1_tilde, + T1_tilde_in, + T2, + T2_in, + T2_tilde, + T2_tilde_in, + ) = state_params + + is_added = False + for successor in G1[popped_node1]: + if successor in mapping: + # if a neighbor of the excluded node1 is in the mapping, keep node1 in T1 + is_added = True + T1_in.add(popped_node1) + else: + # check if its neighbor has another connection with a covered node. If not, only then exclude it from T1 + if not any(pred in mapping for pred in G1.pred[successor]): + T1.discard(successor) + + if not any(succ in mapping for succ in G1[successor]): + T1_in.discard(successor) + + if successor not in T1: + if successor not in T1_in: + T1_tilde.add(successor) + + for predecessor in G1.pred[popped_node1]: + if predecessor in mapping: + # if a neighbor of the excluded node1 is in the mapping, keep node1 in T1 + is_added = True + T1.add(popped_node1) + else: + # check if its neighbor has another connection with a covered node. If not, only then exclude it from T1 + if not any(pred in mapping for pred in G1.pred[predecessor]): + T1.discard(predecessor) + + if not any(succ in mapping for succ in G1[predecessor]): + T1_in.discard(predecessor) + + if not (predecessor in T1 or predecessor in T1_in): + T1_tilde.add(predecessor) + + # Case where the node is not present in neither the mapping nor T1. By deffinition it should belong to T1_tilde + if not is_added: + T1_tilde.add(popped_node1) + + is_added = False + for successor in G2[popped_node2]: + if successor in reverse_mapping: + is_added = True + T2_in.add(popped_node2) + else: + if not any(pred in reverse_mapping for pred in G2.pred[successor]): + T2.discard(successor) + + if not any(succ in reverse_mapping for succ in G2[successor]): + T2_in.discard(successor) + + if successor not in T2: + if successor not in T2_in: + T2_tilde.add(successor) + + for predecessor in G2.pred[popped_node2]: + if predecessor in reverse_mapping: + # if a neighbor of the excluded node1 is in the mapping, keep node1 in T1 + is_added = True + T2.add(popped_node2) + else: + # check if its neighbor has another connection with a covered node. If not, only then exclude it from T1 + if not any(pred in reverse_mapping for pred in G2.pred[predecessor]): + T2.discard(predecessor) + + if not any(succ in reverse_mapping for succ in G2[predecessor]): + T2_in.discard(predecessor) + + if not (predecessor in T2 or predecessor in T2_in): + T2_tilde.add(predecessor) if not is_added: - T2_out.add(popped_node2) + T2_tilde.add(popped_node2) |