1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
"""Unit tests for the broadcasting module."""
import math
import networkx as nx
def test_example_tree_broadcast():
"""
Test the BROADCAST algorithm on the example in the paper titled: "Information Dissemination in Trees"
"""
edge_list = [
(0, 1),
(1, 2),
(2, 7),
(3, 4),
(5, 4),
(4, 7),
(6, 7),
(7, 9),
(8, 9),
(9, 13),
(13, 14),
(14, 15),
(14, 16),
(14, 17),
(13, 11),
(11, 10),
(11, 12),
(13, 18),
(18, 19),
(18, 20),
]
G = nx.Graph(edge_list)
b_T, b_C = nx.tree_broadcast_center(G)
assert b_T == 6
assert b_C == {13, 9}
# test broadcast time from specific vertex
assert nx.tree_broadcast_time(G, 17) == 8
assert nx.tree_broadcast_time(G, 3) == 9
# test broadcast time of entire tree
assert nx.tree_broadcast_time(G) == 10
def test_path_broadcast():
for i in range(2, 12):
G = nx.path_graph(i)
b_T, b_C = nx.tree_broadcast_center(G)
assert b_T == math.ceil(i / 2)
assert b_C == {
math.ceil(i / 2),
math.floor(i / 2),
math.ceil(i / 2 - 1),
math.floor(i / 2 - 1),
}
assert nx.tree_broadcast_time(G) == i - 1
def test_empty_graph_broadcast():
H = nx.empty_graph(1)
b_T, b_C = nx.tree_broadcast_center(H)
assert b_T == 0
assert b_C == {0}
assert nx.tree_broadcast_time(H) == 0
def test_star_broadcast():
for i in range(4, 12):
G = nx.star_graph(i)
b_T, b_C = nx.tree_broadcast_center(G)
assert b_T == i
assert b_C == set(G.nodes())
assert nx.tree_broadcast_time(G) == b_T
def test_binomial_tree_broadcast():
for i in range(2, 8):
G = nx.binomial_tree(i)
b_T, b_C = nx.tree_broadcast_center(G)
assert b_T == i
assert b_C == {0, 2 ** (i - 1)}
assert nx.tree_broadcast_time(G) == 2 * i - 1
|