Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Routines to calculate the broadcast time of certain graphs.
3Broadcasting is an information dissemination problem in which a node in a graph,
4called the originator, must distribute a message to all other nodes by placing
5a series of calls along the edges of the graph. Once informed, other nodes aid
6the originator in distributing the message.
8The broadcasting must be completed as quickly as possible subject to the
9following constraints:
10- Each call requires one unit of time.
11- A node can only participate in one call per unit of time.
12- Each call only involves two adjacent nodes: a sender and a receiver.
13"""
15import networkx as nx
16from networkx.utils import not_implemented_for
18__all__ = [
19 "tree_broadcast_center",
20 "tree_broadcast_time",
21]
24def _get_max_broadcast_value(G, U, v, values):
25 adj = sorted(set(G.neighbors(v)) & U, key=values.get, reverse=True)
26 return max(values[u] + i for i, u in enumerate(adj, start=1))
29def _get_broadcast_centers(G, v, values, target):
30 adj = sorted(G.neighbors(v), key=values.get, reverse=True)
31 j = next(i for i, u in enumerate(adj, start=1) if values[u] + i == target)
32 return set([v] + adj[:j])
35@not_implemented_for("directed")
36@not_implemented_for("multigraph")
37@nx._dispatchable
38def tree_broadcast_center(G):
39 """Return the broadcast center of a tree.
41 The broadcast center of a graph `G` denotes the set of nodes having
42 minimum broadcast time [1]_. This function implements a linear algorithm
43 for determining the broadcast center of a tree with ``n`` nodes. As a
44 by-product, it also determines the broadcast time from the broadcast center.
46 Parameters
47 ----------
48 G : Graph
49 The graph should be an undirected tree.
51 Returns
52 -------
53 b_T, b_C : (int, set) tuple
54 Minimum broadcast time of the broadcast center in `G`, set of nodes
55 in the broadcast center.
57 Raises
58 ------
59 NetworkXNotImplemented
60 If `G` is directed or is a multigraph.
62 NotATree
63 If `G` is not a tree.
65 References
66 ----------
67 .. [1] Slater, P.J., Cockayne, E.J., Hedetniemi, S.T,
68 Information dissemination in trees. SIAM J.Comput. 10(4), 692–701 (1981)
69 """
70 # Assert that the graph G is a tree
71 if not nx.is_tree(G):
72 raise nx.NotATree("G is not a tree")
73 # step 0
74 if (n := len(G)) < 3:
75 return n - 1, set(G)
77 # step 1
78 U = {node for node, deg in G.degree if deg == 1}
79 values = {n: 0 for n in U}
80 T = G.copy()
81 T.remove_nodes_from(U)
83 # step 2
84 W = {node for node, deg in T.degree if deg == 1}
85 values.update((w, G.degree[w] - 1) for w in W)
87 # step 3
88 while len(T) >= 2:
89 # step 4
90 w = min(W, key=values.get)
91 v = next(T.neighbors(w))
93 # step 5
94 U.add(w)
95 W.remove(w)
96 T.remove_node(w)
98 # step 6
99 if T.degree(v) == 1:
100 # update t(v)
101 values.update({v: _get_max_broadcast_value(G, U, v, values)})
102 W.add(v)
104 # step 7
105 v = nx.utils.arbitrary_element(T)
106 b_T = _get_max_broadcast_value(G, U, v, values)
107 return b_T, _get_broadcast_centers(G, v, values, b_T)
110@not_implemented_for("directed")
111@not_implemented_for("multigraph")
112@nx._dispatchable
113def tree_broadcast_time(G, node=None):
114 """Return the minimum broadcast time of a (node in a) tree.
116 The minimum broadcast time of a node is defined as the minimum amount
117 of time required to complete broadcasting starting from that node.
118 The broadcast time of a graph is the maximum over
119 all nodes of the minimum broadcast time from that node [1]_.
120 This function returns the minimum broadcast time of `node`.
121 If `node` is `None`, the broadcast time for the graph is returned.
123 Parameters
124 ----------
125 G : Graph
126 The graph should be an undirected tree.
128 node : node, optional (default=None)
129 Starting node for the broadcasting. If `None`, the algorithm
130 returns the broadcast time of the graph instead.
132 Returns
133 -------
134 int
135 Minimum broadcast time of `node` in `G`, or broadcast time of `G`
136 if no node is provided.
138 Raises
139 ------
140 NetworkXNotImplemented
141 If `G` is directed or is a multigraph.
143 NodeNotFound
144 If `node` is not a node in `G`.
146 NotATree
147 If `G` is not a tree.
149 References
150 ----------
151 .. [1] Harutyunyan, H. A. and Li, Z.
152 "A Simple Construction of Broadcast Graphs."
153 In Computing and Combinatorics. COCOON 2019
154 (Ed. D. Z. Du and C. Tian.) Springer, pp. 240-253, 2019.
155 """
156 if node is not None and node not in G:
157 err = f"node {node} not in G"
158 raise nx.NodeNotFound(err)
159 b_T, b_C = tree_broadcast_center(G)
160 if node is None:
161 return b_T + sum(1 for _ in nx.bfs_layers(G, b_C)) - 1
162 return b_T + next(
163 d for d, layer in enumerate(nx.bfs_layers(G, b_C)) if node in layer
164 )