Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_cuts.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.cuts` module.""" | |
2 | |
3 | |
4 import networkx as nx | |
5 | |
6 | |
7 class TestCutSize: | |
8 """Unit tests for the :func:`~networkx.cut_size` function.""" | |
9 | |
10 def test_symmetric(self): | |
11 """Tests that the cut size is symmetric.""" | |
12 G = nx.barbell_graph(3, 0) | |
13 S = {0, 1, 4} | |
14 T = {2, 3, 5} | |
15 assert nx.cut_size(G, S, T) == 4 | |
16 assert nx.cut_size(G, T, S) == 4 | |
17 | |
18 def test_single_edge(self): | |
19 """Tests for a cut of a single edge.""" | |
20 G = nx.barbell_graph(3, 0) | |
21 S = {0, 1, 2} | |
22 T = {3, 4, 5} | |
23 assert nx.cut_size(G, S, T) == 1 | |
24 assert nx.cut_size(G, T, S) == 1 | |
25 | |
26 def test_directed(self): | |
27 """Tests that each directed edge is counted once in the cut.""" | |
28 G = nx.barbell_graph(3, 0).to_directed() | |
29 S = {0, 1, 2} | |
30 T = {3, 4, 5} | |
31 assert nx.cut_size(G, S, T) == 2 | |
32 assert nx.cut_size(G, T, S) == 2 | |
33 | |
34 def test_directed_symmetric(self): | |
35 """Tests that a cut in a directed graph is symmetric.""" | |
36 G = nx.barbell_graph(3, 0).to_directed() | |
37 S = {0, 1, 4} | |
38 T = {2, 3, 5} | |
39 assert nx.cut_size(G, S, T) == 8 | |
40 assert nx.cut_size(G, T, S) == 8 | |
41 | |
42 def test_multigraph(self): | |
43 """Tests that parallel edges are each counted for a cut.""" | |
44 G = nx.MultiGraph(["ab", "ab"]) | |
45 assert nx.cut_size(G, {"a"}, {"b"}) == 2 | |
46 | |
47 | |
48 class TestVolume: | |
49 """Unit tests for the :func:`~networkx.volume` function.""" | |
50 | |
51 def test_graph(self): | |
52 G = nx.cycle_graph(4) | |
53 assert nx.volume(G, {0, 1}) == 4 | |
54 | |
55 def test_digraph(self): | |
56 G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 0)]) | |
57 assert nx.volume(G, {0, 1}) == 2 | |
58 | |
59 def test_multigraph(self): | |
60 edges = list(nx.cycle_graph(4).edges()) | |
61 G = nx.MultiGraph(edges * 2) | |
62 assert nx.volume(G, {0, 1}) == 8 | |
63 | |
64 def test_multidigraph(self): | |
65 edges = [(0, 1), (1, 2), (2, 3), (3, 0)] | |
66 G = nx.MultiDiGraph(edges * 2) | |
67 assert nx.volume(G, {0, 1}) == 4 | |
68 | |
69 | |
70 class TestNormalizedCutSize: | |
71 """Unit tests for the :func:`~networkx.normalized_cut_size` | |
72 function. | |
73 | |
74 """ | |
75 | |
76 def test_graph(self): | |
77 G = nx.path_graph(4) | |
78 S = {1, 2} | |
79 T = set(G) - S | |
80 size = nx.normalized_cut_size(G, S, T) | |
81 # The cut looks like this: o-{-o--o-}-o | |
82 expected = 2 * ((1 / 4) + (1 / 2)) | |
83 assert expected == size | |
84 | |
85 def test_directed(self): | |
86 G = nx.DiGraph([(0, 1), (1, 2), (2, 3)]) | |
87 S = {1, 2} | |
88 T = set(G) - S | |
89 size = nx.normalized_cut_size(G, S, T) | |
90 # The cut looks like this: o-{->o-->o-}->o | |
91 expected = 2 * ((1 / 2) + (1 / 1)) | |
92 assert expected == size | |
93 | |
94 | |
95 class TestConductance: | |
96 """Unit tests for the :func:`~networkx.conductance` function.""" | |
97 | |
98 def test_graph(self): | |
99 G = nx.barbell_graph(5, 0) | |
100 # Consider the singleton sets containing the "bridge" nodes. | |
101 # There is only one cut edge, and each set has volume five. | |
102 S = {4} | |
103 T = {5} | |
104 conductance = nx.conductance(G, S, T) | |
105 expected = 1 / 5 | |
106 assert expected == conductance | |
107 | |
108 | |
109 class TestEdgeExpansion: | |
110 """Unit tests for the :func:`~networkx.edge_expansion` function.""" | |
111 | |
112 def test_graph(self): | |
113 G = nx.barbell_graph(5, 0) | |
114 S = set(range(5)) | |
115 T = set(G) - S | |
116 expansion = nx.edge_expansion(G, S, T) | |
117 expected = 1 / 5 | |
118 assert expected == expansion | |
119 | |
120 | |
121 class TestNodeExpansion: | |
122 """Unit tests for the :func:`~networkx.node_expansion` function. | |
123 | |
124 """ | |
125 | |
126 def test_graph(self): | |
127 G = nx.path_graph(8) | |
128 S = {3, 4, 5} | |
129 expansion = nx.node_expansion(G, S) | |
130 # The neighborhood of S has cardinality five, and S has | |
131 # cardinality three. | |
132 expected = 5 / 3 | |
133 assert expected == expansion | |
134 | |
135 | |
136 class TestBoundaryExpansion: | |
137 """Unit tests for the :func:`~networkx.boundary_expansion` function. | |
138 | |
139 """ | |
140 | |
141 def test_graph(self): | |
142 G = nx.complete_graph(10) | |
143 S = set(range(4)) | |
144 expansion = nx.boundary_expansion(G, S) | |
145 # The node boundary of S has cardinality six, and S has | |
146 # cardinality three. | |
147 expected = 6 / 4 | |
148 assert expected == expansion | |
149 | |
150 | |
151 class TestMixingExpansion: | |
152 """Unit tests for the :func:`~networkx.mixing_expansion` function. | |
153 | |
154 """ | |
155 | |
156 def test_graph(self): | |
157 G = nx.barbell_graph(5, 0) | |
158 S = set(range(5)) | |
159 T = set(G) - S | |
160 expansion = nx.mixing_expansion(G, S, T) | |
161 # There is one cut edge, and the total number of edges in the | |
162 # graph is twice the total number of edges in a clique of size | |
163 # five, plus one more for the bridge. | |
164 expected = 1 / (2 * (5 * 4 + 1)) | |
165 assert expected == expansion |