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