Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/tests/test_core.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"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 import networkx as nx
2 from networkx.testing.utils import assert_nodes_equal
3
4
5 class TestCore:
6 @classmethod
7 def setup_class(cls):
8 # G is the example graph in Figure 1 from Batagelj and
9 # Zaversnik's paper titled An O(m) Algorithm for Cores
10 # Decomposition of Networks, 2003,
11 # http://arXiv.org/abs/cs/0310049. With nodes labeled as
12 # shown, the 3-core is given by nodes 1-8, the 2-core by nodes
13 # 9-16, the 1-core by nodes 17-20 and node 21 is in the
14 # 0-core.
15 t1 = nx.convert_node_labels_to_integers(nx.tetrahedral_graph(), 1)
16 t2 = nx.convert_node_labels_to_integers(t1, 5)
17 G = nx.union(t1, t2)
18 G.add_edges_from(
19 [
20 (3, 7),
21 (2, 11),
22 (11, 5),
23 (11, 12),
24 (5, 12),
25 (12, 19),
26 (12, 18),
27 (3, 9),
28 (7, 9),
29 (7, 10),
30 (9, 10),
31 (9, 20),
32 (17, 13),
33 (13, 14),
34 (14, 15),
35 (15, 16),
36 (16, 13),
37 ]
38 )
39 G.add_node(21)
40 cls.G = G
41
42 # Create the graph H resulting from the degree sequence
43 # [0, 1, 2, 2, 2, 2, 3] when using the Havel-Hakimi algorithm.
44
45 degseq = [0, 1, 2, 2, 2, 2, 3]
46 H = nx.havel_hakimi_graph(degseq)
47 mapping = {6: 0, 0: 1, 4: 3, 5: 6, 3: 4, 1: 2, 2: 5}
48 cls.H = nx.relabel_nodes(H, mapping)
49
50 def test_trivial(self):
51 """Empty graph"""
52 G = nx.Graph()
53 assert nx.find_cores(G) == {}
54
55 def test_find_cores(self):
56 core = nx.find_cores(self.G)
57 nodes_by_core = [
58 sorted([n for n in core if core[n] == val]) for val in range(4)
59 ]
60 assert_nodes_equal(nodes_by_core[0], [21])
61 assert_nodes_equal(nodes_by_core[1], [17, 18, 19, 20])
62 assert_nodes_equal(nodes_by_core[2], [9, 10, 11, 12, 13, 14, 15, 16])
63 assert_nodes_equal(nodes_by_core[3], [1, 2, 3, 4, 5, 6, 7, 8])
64
65 def test_core_number(self):
66 # smoke test real name
67 cores = nx.core_number(self.G)
68
69 def test_find_cores2(self):
70 core = nx.find_cores(self.H)
71 nodes_by_core = [
72 sorted([n for n in core if core[n] == val]) for val in range(3)
73 ]
74 assert_nodes_equal(nodes_by_core[0], [0])
75 assert_nodes_equal(nodes_by_core[1], [1, 3])
76 assert_nodes_equal(nodes_by_core[2], [2, 4, 5, 6])
77
78 def test_directed_find_cores(self):
79 """core number had a bug for directed graphs found in issue #1959"""
80 # small example where too timid edge removal can make cn[2] = 3
81 G = nx.DiGraph()
82 edges = [(1, 2), (2, 1), (2, 3), (2, 4), (3, 4), (4, 3)]
83 G.add_edges_from(edges)
84 assert nx.core_number(G) == {1: 2, 2: 2, 3: 2, 4: 2}
85 # small example where too aggressive edge removal can make cn[2] = 2
86 more_edges = [(1, 5), (3, 5), (4, 5), (3, 6), (4, 6), (5, 6)]
87 G.add_edges_from(more_edges)
88 assert nx.core_number(G) == {1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3}
89
90 def test_main_core(self):
91 main_core_subgraph = nx.k_core(self.H)
92 assert sorted(main_core_subgraph.nodes()) == [2, 4, 5, 6]
93
94 def test_k_core(self):
95 # k=0
96 k_core_subgraph = nx.k_core(self.H, k=0)
97 assert sorted(k_core_subgraph.nodes()) == sorted(self.H.nodes())
98 # k=1
99 k_core_subgraph = nx.k_core(self.H, k=1)
100 assert sorted(k_core_subgraph.nodes()) == [1, 2, 3, 4, 5, 6]
101 # k = 2
102 k_core_subgraph = nx.k_core(self.H, k=2)
103 assert sorted(k_core_subgraph.nodes()) == [2, 4, 5, 6]
104
105 def test_main_crust(self):
106 main_crust_subgraph = nx.k_crust(self.H)
107 assert sorted(main_crust_subgraph.nodes()) == [0, 1, 3]
108
109 def test_k_crust(self):
110 # k = 0
111 k_crust_subgraph = nx.k_crust(self.H, k=2)
112 assert sorted(k_crust_subgraph.nodes()) == sorted(self.H.nodes())
113 # k=1
114 k_crust_subgraph = nx.k_crust(self.H, k=1)
115 assert sorted(k_crust_subgraph.nodes()) == [0, 1, 3]
116 # k=2
117 k_crust_subgraph = nx.k_crust(self.H, k=0)
118 assert sorted(k_crust_subgraph.nodes()) == [0]
119
120 def test_main_shell(self):
121 main_shell_subgraph = nx.k_shell(self.H)
122 assert sorted(main_shell_subgraph.nodes()) == [2, 4, 5, 6]
123
124 def test_k_shell(self):
125 # k=0
126 k_shell_subgraph = nx.k_shell(self.H, k=2)
127 assert sorted(k_shell_subgraph.nodes()) == [2, 4, 5, 6]
128 # k=1
129 k_shell_subgraph = nx.k_shell(self.H, k=1)
130 assert sorted(k_shell_subgraph.nodes()) == [1, 3]
131 # k=2
132 k_shell_subgraph = nx.k_shell(self.H, k=0)
133 assert sorted(k_shell_subgraph.nodes()) == [0]
134
135 def test_k_corona(self):
136 # k=0
137 k_corona_subgraph = nx.k_corona(self.H, k=2)
138 assert sorted(k_corona_subgraph.nodes()) == [2, 4, 5, 6]
139 # k=1
140 k_corona_subgraph = nx.k_corona(self.H, k=1)
141 assert sorted(k_corona_subgraph.nodes()) == [1]
142 # k=2
143 k_corona_subgraph = nx.k_corona(self.H, k=0)
144 assert sorted(k_corona_subgraph.nodes()) == [0]
145
146 def test_k_truss(self):
147 # k=-1
148 k_truss_subgraph = nx.k_truss(self.G, -1)
149 assert sorted(k_truss_subgraph.nodes()) == list(range(1, 21))
150 # k=0
151 k_truss_subgraph = nx.k_truss(self.G, 0)
152 assert sorted(k_truss_subgraph.nodes()) == list(range(1, 21))
153 # k=1
154 k_truss_subgraph = nx.k_truss(self.G, 1)
155 assert sorted(k_truss_subgraph.nodes()) == list(range(1, 21))
156 # k=2
157 k_truss_subgraph = nx.k_truss(self.G, 2)
158 assert sorted(k_truss_subgraph.nodes()) == list(range(1, 21))
159 # k=3
160 k_truss_subgraph = nx.k_truss(self.G, 3)
161 assert sorted(k_truss_subgraph.nodes()) == list(range(1, 13))
162
163 k_truss_subgraph = nx.k_truss(self.G, 4)
164 assert sorted(k_truss_subgraph.nodes()) == list(range(1, 9))
165
166 k_truss_subgraph = nx.k_truss(self.G, 5)
167 assert sorted(k_truss_subgraph.nodes()) == []
168
169 def test_onion_layers(self):
170 layers = nx.onion_layers(self.G)
171 nodes_by_layer = [
172 sorted([n for n in layers if layers[n] == val]) for val in range(1, 7)
173 ]
174 assert_nodes_equal(nodes_by_layer[0], [21])
175 assert_nodes_equal(nodes_by_layer[1], [17, 18, 19, 20])
176 assert_nodes_equal(nodes_by_layer[2], [10, 12, 13, 14, 15, 16])
177 assert_nodes_equal(nodes_by_layer[3], [9, 11])
178 assert_nodes_equal(nodes_by_layer[4], [1, 2, 4, 5, 6, 8])
179 assert_nodes_equal(nodes_by_layer[5], [3, 7])