two version of R2R are hereHEADmaster

1 files changed, 154 insertions, 0 deletions

diff --git a/.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_boundary.py b/.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_boundary.py
new file mode 100644
index 00000000..856be465
--- /dev/null
+++ b/.venv/lib/python3.12/site-packages/networkx/algorithms/tests/test_boundary.py
@@ -0,0 +1,154 @@
+"""Unit tests for the :mod:`networkx.algorithms.boundary` module."""
+
+from itertools import combinations
+
+import pytest
+
+import networkx as nx
+from networkx import convert_node_labels_to_integers as cnlti
+from networkx.utils import edges_equal
+
+
+class TestNodeBoundary:
+    """Unit tests for the :func:`~networkx.node_boundary` function."""
+
+    def test_null_graph(self):
+        """Tests that the null graph has empty node boundaries."""
+        null = nx.null_graph()
+        assert nx.node_boundary(null, []) == set()
+        assert nx.node_boundary(null, [], []) == set()
+        assert nx.node_boundary(null, [1, 2, 3]) == set()
+        assert nx.node_boundary(null, [1, 2, 3], [4, 5, 6]) == set()
+        assert nx.node_boundary(null, [1, 2, 3], [3, 4, 5]) == set()
+
+    def test_path_graph(self):
+        P10 = cnlti(nx.path_graph(10), first_label=1)
+        assert nx.node_boundary(P10, []) == set()
+        assert nx.node_boundary(P10, [], []) == set()
+        assert nx.node_boundary(P10, [1, 2, 3]) == {4}
+        assert nx.node_boundary(P10, [4, 5, 6]) == {3, 7}
+        assert nx.node_boundary(P10, [3, 4, 5, 6, 7]) == {2, 8}
+        assert nx.node_boundary(P10, [8, 9, 10]) == {7}
+        assert nx.node_boundary(P10, [4, 5, 6], [9, 10]) == set()
+
+    def test_complete_graph(self):
+        K10 = cnlti(nx.complete_graph(10), first_label=1)
+        assert nx.node_boundary(K10, []) == set()
+        assert nx.node_boundary(K10, [], []) == set()
+        assert nx.node_boundary(K10, [1, 2, 3]) == {4, 5, 6, 7, 8, 9, 10}
+        assert nx.node_boundary(K10, [4, 5, 6]) == {1, 2, 3, 7, 8, 9, 10}
+        assert nx.node_boundary(K10, [3, 4, 5, 6, 7]) == {1, 2, 8, 9, 10}
+        assert nx.node_boundary(K10, [4, 5, 6], []) == set()
+        assert nx.node_boundary(K10, K10) == set()
+        assert nx.node_boundary(K10, [1, 2, 3], [3, 4, 5]) == {4, 5}
+
+    def test_petersen(self):
+        """Check boundaries in the petersen graph
+
+        cheeger(G,k)=min(|bdy(S)|/|S| for |S|=k, 0<k<=|V(G)|/2)
+
+        """
+
+        def cheeger(G, k):
+            return min(len(nx.node_boundary(G, nn)) / k for nn in combinations(G, k))
+
+        P = nx.petersen_graph()
+        assert cheeger(P, 1) == pytest.approx(3.00, abs=1e-2)
+        assert cheeger(P, 2) == pytest.approx(2.00, abs=1e-2)
+        assert cheeger(P, 3) == pytest.approx(1.67, abs=1e-2)
+        assert cheeger(P, 4) == pytest.approx(1.00, abs=1e-2)
+        assert cheeger(P, 5) == pytest.approx(0.80, abs=1e-2)
+
+    def test_directed(self):
+        """Tests the node boundary of a directed graph."""
+        G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
+        S = {0, 1}
+        boundary = nx.node_boundary(G, S)
+        expected = {2}
+        assert boundary == expected
+
+    def test_multigraph(self):
+        """Tests the node boundary of a multigraph."""
+        G = nx.MultiGraph(list(nx.cycle_graph(5).edges()) * 2)
+        S = {0, 1}
+        boundary = nx.node_boundary(G, S)
+        expected = {2, 4}
+        assert boundary == expected
+
+    def test_multidigraph(self):
+        """Tests the edge boundary of a multidigraph."""
+        edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
+        G = nx.MultiDiGraph(edges * 2)
+        S = {0, 1}
+        boundary = nx.node_boundary(G, S)
+        expected = {2}
+        assert boundary == expected
+
+
+class TestEdgeBoundary:
+    """Unit tests for the :func:`~networkx.edge_boundary` function."""
+
+    def test_null_graph(self):
+        null = nx.null_graph()
+        assert list(nx.edge_boundary(null, [])) == []
+        assert list(nx.edge_boundary(null, [], [])) == []
+        assert list(nx.edge_boundary(null, [1, 2, 3])) == []
+        assert list(nx.edge_boundary(null, [1, 2, 3], [4, 5, 6])) == []
+        assert list(nx.edge_boundary(null, [1, 2, 3], [3, 4, 5])) == []
+
+    def test_path_graph(self):
+        P10 = cnlti(nx.path_graph(10), first_label=1)
+        assert list(nx.edge_boundary(P10, [])) == []
+        assert list(nx.edge_boundary(P10, [], [])) == []
+        assert list(nx.edge_boundary(P10, [1, 2, 3])) == [(3, 4)]
+        assert sorted(nx.edge_boundary(P10, [4, 5, 6])) == [(4, 3), (6, 7)]
+        assert sorted(nx.edge_boundary(P10, [3, 4, 5, 6, 7])) == [(3, 2), (7, 8)]
+        assert list(nx.edge_boundary(P10, [8, 9, 10])) == [(8, 7)]
+        assert sorted(nx.edge_boundary(P10, [4, 5, 6], [9, 10])) == []
+        assert list(nx.edge_boundary(P10, [1, 2, 3], [3, 4, 5])) == [(2, 3), (3, 4)]
+
+    def test_complete_graph(self):
+        K10 = cnlti(nx.complete_graph(10), first_label=1)
+
+        def ilen(iterable):
+            return sum(1 for i in iterable)
+
+        assert list(nx.edge_boundary(K10, [])) == []
+        assert list(nx.edge_boundary(K10, [], [])) == []
+        assert ilen(nx.edge_boundary(K10, [1, 2, 3])) == 21
+        assert ilen(nx.edge_boundary(K10, [4, 5, 6, 7])) == 24
+        assert ilen(nx.edge_boundary(K10, [3, 4, 5, 6, 7])) == 25
+        assert ilen(nx.edge_boundary(K10, [8, 9, 10])) == 21
+        assert edges_equal(
+            nx.edge_boundary(K10, [4, 5, 6], [9, 10]),
+            [(4, 9), (4, 10), (5, 9), (5, 10), (6, 9), (6, 10)],
+        )
+        assert edges_equal(
+            nx.edge_boundary(K10, [1, 2, 3], [3, 4, 5]),
+            [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5)],
+        )
+
+    def test_directed(self):
+        """Tests the edge boundary of a directed graph."""
+        G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)])
+        S = {0, 1}
+        boundary = list(nx.edge_boundary(G, S))
+        expected = [(1, 2)]
+        assert boundary == expected
+
+    def test_multigraph(self):
+        """Tests the edge boundary of a multigraph."""
+        G = nx.MultiGraph(list(nx.cycle_graph(5).edges()) * 2)
+        S = {0, 1}
+        boundary = list(nx.edge_boundary(G, S))
+        expected = [(0, 4), (0, 4), (1, 2), (1, 2)]
+        assert boundary == expected
+
+    def test_multidigraph(self):
+        """Tests the edge boundary of a multidigraph."""
+        edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]
+        G = nx.MultiDiGraph(edges * 2)
+        S = {0, 1}
+        boundary = list(nx.edge_boundary(G, S))
+        expected = [(1, 2), (1, 2)]
+        assert boundary == expected