Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_boundary.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
| author | shellac |
|---|---|
| date | Mon, 22 Mar 2021 18:12:50 +0000 |
| parents | |
| children |
comparison
equal
deleted
inserted
replaced
| -1:000000000000 | 0:4f3585e2f14b |
|---|---|
| 1 """Unit tests for the :mod:`networkx.algorithms.boundary` module.""" | |
| 2 | |
| 3 from itertools import combinations | |
| 4 | |
| 5 import networkx as nx | |
| 6 from networkx.testing import almost_equal, assert_edges_equal | |
| 7 from networkx import convert_node_labels_to_integers as cnlti | |
| 8 | |
| 9 | |
| 10 class TestNodeBoundary: | |
| 11 """Unit tests for the :func:`~networkx.node_boundary` function.""" | |
| 12 | |
| 13 def test_null_graph(self): | |
| 14 """Tests that the null graph has empty node boundaries.""" | |
| 15 null = nx.null_graph() | |
| 16 assert nx.node_boundary(null, []) == set() | |
| 17 assert nx.node_boundary(null, [], []) == set() | |
| 18 assert nx.node_boundary(null, [1, 2, 3]) == set() | |
| 19 assert nx.node_boundary(null, [1, 2, 3], [4, 5, 6]) == set() | |
| 20 assert nx.node_boundary(null, [1, 2, 3], [3, 4, 5]) == set() | |
| 21 | |
| 22 def test_path_graph(self): | |
| 23 P10 = cnlti(nx.path_graph(10), first_label=1) | |
| 24 assert nx.node_boundary(P10, []) == set() | |
| 25 assert nx.node_boundary(P10, [], []) == set() | |
| 26 assert nx.node_boundary(P10, [1, 2, 3]) == {4} | |
| 27 assert nx.node_boundary(P10, [4, 5, 6]) == {3, 7} | |
| 28 assert nx.node_boundary(P10, [3, 4, 5, 6, 7]) == {2, 8} | |
| 29 assert nx.node_boundary(P10, [8, 9, 10]) == {7} | |
| 30 assert nx.node_boundary(P10, [4, 5, 6], [9, 10]) == set() | |
| 31 | |
| 32 def test_complete_graph(self): | |
| 33 K10 = cnlti(nx.complete_graph(10), first_label=1) | |
| 34 assert nx.node_boundary(K10, []) == set() | |
| 35 assert nx.node_boundary(K10, [], []) == set() | |
| 36 assert nx.node_boundary(K10, [1, 2, 3]) == {4, 5, 6, 7, 8, 9, 10} | |
| 37 assert nx.node_boundary(K10, [4, 5, 6]) == {1, 2, 3, 7, 8, 9, 10} | |
| 38 assert nx.node_boundary(K10, [3, 4, 5, 6, 7]) == {1, 2, 8, 9, 10} | |
| 39 assert nx.node_boundary(K10, [4, 5, 6], []) == set() | |
| 40 assert nx.node_boundary(K10, K10) == set() | |
| 41 assert nx.node_boundary(K10, [1, 2, 3], [3, 4, 5]) == {4, 5} | |
| 42 | |
| 43 def test_petersen(self): | |
| 44 """Check boundaries in the petersen graph | |
| 45 | |
| 46 cheeger(G,k)=min(|bdy(S)|/|S| for |S|=k, 0<k<=|V(G)|/2) | |
| 47 | |
| 48 """ | |
| 49 | |
| 50 def cheeger(G, k): | |
| 51 return min(len(nx.node_boundary(G, nn)) / k for nn in combinations(G, k)) | |
| 52 | |
| 53 P = nx.petersen_graph() | |
| 54 assert almost_equal(cheeger(P, 1), 3.00, places=2) | |
| 55 assert almost_equal(cheeger(P, 2), 2.00, places=2) | |
| 56 assert almost_equal(cheeger(P, 3), 1.67, places=2) | |
| 57 assert almost_equal(cheeger(P, 4), 1.00, places=2) | |
| 58 assert almost_equal(cheeger(P, 5), 0.80, places=2) | |
| 59 | |
| 60 def test_directed(self): | |
| 61 """Tests the node boundary of a directed graph.""" | |
| 62 G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]) | |
| 63 S = {0, 1} | |
| 64 boundary = nx.node_boundary(G, S) | |
| 65 expected = {2} | |
| 66 assert boundary == expected | |
| 67 | |
| 68 def test_multigraph(self): | |
| 69 """Tests the node boundary of a multigraph.""" | |
| 70 G = nx.MultiGraph(list(nx.cycle_graph(5).edges()) * 2) | |
| 71 S = {0, 1} | |
| 72 boundary = nx.node_boundary(G, S) | |
| 73 expected = {2, 4} | |
| 74 assert boundary == expected | |
| 75 | |
| 76 def test_multidigraph(self): | |
| 77 """Tests the edge boundary of a multdiigraph.""" | |
| 78 edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)] | |
| 79 G = nx.MultiDiGraph(edges * 2) | |
| 80 S = {0, 1} | |
| 81 boundary = nx.node_boundary(G, S) | |
| 82 expected = {2} | |
| 83 assert boundary == expected | |
| 84 | |
| 85 | |
| 86 class TestEdgeBoundary: | |
| 87 """Unit tests for the :func:`~networkx.edge_boundary` function.""" | |
| 88 | |
| 89 def test_null_graph(self): | |
| 90 null = nx.null_graph() | |
| 91 assert list(nx.edge_boundary(null, [])) == [] | |
| 92 assert list(nx.edge_boundary(null, [], [])) == [] | |
| 93 assert list(nx.edge_boundary(null, [1, 2, 3])) == [] | |
| 94 assert list(nx.edge_boundary(null, [1, 2, 3], [4, 5, 6])) == [] | |
| 95 assert list(nx.edge_boundary(null, [1, 2, 3], [3, 4, 5])) == [] | |
| 96 | |
| 97 def test_path_graph(self): | |
| 98 P10 = cnlti(nx.path_graph(10), first_label=1) | |
| 99 assert list(nx.edge_boundary(P10, [])) == [] | |
| 100 assert list(nx.edge_boundary(P10, [], [])) == [] | |
| 101 assert list(nx.edge_boundary(P10, [1, 2, 3])) == [(3, 4)] | |
| 102 assert sorted(nx.edge_boundary(P10, [4, 5, 6])) == [(4, 3), (6, 7)] | |
| 103 assert sorted(nx.edge_boundary(P10, [3, 4, 5, 6, 7])) == [(3, 2), (7, 8)] | |
| 104 assert list(nx.edge_boundary(P10, [8, 9, 10])) == [(8, 7)] | |
| 105 assert sorted(nx.edge_boundary(P10, [4, 5, 6], [9, 10])) == [] | |
| 106 assert list(nx.edge_boundary(P10, [1, 2, 3], [3, 4, 5])) == [(2, 3), (3, 4)] | |
| 107 | |
| 108 def test_complete_graph(self): | |
| 109 K10 = cnlti(nx.complete_graph(10), first_label=1) | |
| 110 | |
| 111 def ilen(iterable): | |
| 112 return sum(1 for i in iterable) | |
| 113 | |
| 114 assert list(nx.edge_boundary(K10, [])) == [] | |
| 115 assert list(nx.edge_boundary(K10, [], [])) == [] | |
| 116 assert ilen(nx.edge_boundary(K10, [1, 2, 3])) == 21 | |
| 117 assert ilen(nx.edge_boundary(K10, [4, 5, 6, 7])) == 24 | |
| 118 assert ilen(nx.edge_boundary(K10, [3, 4, 5, 6, 7])) == 25 | |
| 119 assert ilen(nx.edge_boundary(K10, [8, 9, 10])) == 21 | |
| 120 assert_edges_equal( | |
| 121 nx.edge_boundary(K10, [4, 5, 6], [9, 10]), | |
| 122 [(4, 9), (4, 10), (5, 9), (5, 10), (6, 9), (6, 10)], | |
| 123 ) | |
| 124 assert_edges_equal( | |
| 125 nx.edge_boundary(K10, [1, 2, 3], [3, 4, 5]), | |
| 126 [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5)], | |
| 127 ) | |
| 128 | |
| 129 def test_directed(self): | |
| 130 """Tests the edge boundary of a directed graph.""" | |
| 131 G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)]) | |
| 132 S = {0, 1} | |
| 133 boundary = list(nx.edge_boundary(G, S)) | |
| 134 expected = [(1, 2)] | |
| 135 assert boundary == expected | |
| 136 | |
| 137 def test_multigraph(self): | |
| 138 """Tests the edge boundary of a multigraph.""" | |
| 139 G = nx.MultiGraph(list(nx.cycle_graph(5).edges()) * 2) | |
| 140 S = {0, 1} | |
| 141 boundary = list(nx.edge_boundary(G, S)) | |
| 142 expected = [(0, 4), (0, 4), (1, 2), (1, 2)] | |
| 143 assert boundary == expected | |
| 144 | |
| 145 def test_multidigraph(self): | |
| 146 """Tests the edge boundary of a multdiigraph.""" | |
| 147 edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)] | |
| 148 G = nx.MultiDiGraph(edges * 2) | |
| 149 S = {0, 1} | |
| 150 boundary = list(nx.edge_boundary(G, S)) | |
| 151 expected = [(1, 2), (1, 2)] | |
| 152 assert boundary == expected |