### annotate env/lib/python3.9/site-packages/networkx/algorithms/tests/test_boundary.py @ 0:4f3585e2f14bdraftdefaulttip

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