"""
Algorithms for computing distance measures on trees.
"""
import networkx as nx
__all__ = [
"center",
"centroid",
]
[docs]
@nx.utils.not_implemented_for("directed")
def center(G):
"""Returns the center of an undirected tree graph.
The center of a tree consists of nodes that minimize the maximum eccentricity.
That is, these nodes minimize the maximum distance to all other nodes.
This implementation currently only works for unweighted edges.
If the input graph is not a tree, results are not guaranteed to be correct and while
some non-trees will raise an ``nx.NotATree`` exception, not all non-trees will be discovered.
Thus, this function should not be used if caller is unsure whether the input graph
is a tree. Use ``nx.is_tree(G)`` to check.
Parameters
----------
G : NetworkX graph
A tree graph (undirected, acyclic graph).
Returns
-------
center : list
A list of nodes forming the center of the tree. This can be one or two nodes.
Raises
------
NetworkXNotImplemented
If the input graph is directed.
NotATree
If the algorithm detects the input graph is not a tree. There is no guarantee
this error will always raise if a non-tree is passed.
Notes
-----
This algorithm iteratively removes leaves (nodes with degree 1) from the tree until
there are only 1 or 2 nodes left. The remaining nodes form the center of the tree.
This algorithm's time complexity is ``O(N)`` where ``N`` is the number of nodes in the tree.
Examples
--------
>>> G = nx.Graph([(1, 2), (1, 3), (2, 4), (2, 5)])
>>> nx.tree.center(G)
[1, 2]
>>> G = nx.path_graph(5)
>>> nx.tree.center(G)
[2]
"""
center_candidates_degree = dict(G.degree)
leaves = {node for node, degree in center_candidates_degree.items() if degree == 1}
# It's better to fail than an infinite loop, so check leaves to ensure progress.
while len(center_candidates_degree) > 2 and leaves:
new_leaves = set()
for leaf in leaves:
del center_candidates_degree[leaf]
for neighbor in G.neighbors(leaf):
if neighbor not in center_candidates_degree:
continue
center_candidates_degree[neighbor] -= 1
if (cddn := center_candidates_degree[neighbor]) == 1:
new_leaves.add(neighbor)
elif cddn == 0 and len(center_candidates_degree) != 1:
raise nx.NotATree("input graph is not a tree")
leaves = new_leaves
n = len(center_candidates_degree)
# check disconnected or cyclic
if (n == 2 and not leaves) or n not in {1, 2}:
# We have detected graph is not a tree. This check does not cover all cases.
# For example, `nx.Graph([(0, 0)])` will not raise an error.
raise nx.NotATree("input graph is not a tree")
return list(center_candidates_degree)
def _subtree_sizes(G, root):
"""Return a `dict` of the size of each subtree, for every subtree
of a tree rooted at a given node.
For every node in the given tree, consider the new tree that would
be created by detaching it from its parent node (if any). The
number of nodes in the resulting tree rooted at that node is then
assigned as the value for that node in the return dictionary.
Parameters
----------
G : NetworkX graph
A tree.
root : node
A node in `G`.
Returns
-------
s : dict
Dictionary of number of nodes in every subtree of this tree,
keyed on the root node for each subtree.
Examples
--------
>>> _subtree_sizes(nx.path_graph(4), 0)
{0: 4, 1: 3, 2: 2, 3: 1}
>>> _subtree_sizes(nx.path_graph(4), 2)
{2: 4, 1: 2, 0: 1, 3: 1}
"""
sizes = {root: 1}
stack = [root]
for parent, child in nx.dfs_edges(G, root):
while stack[-1] != parent:
descendant = stack.pop()
sizes[stack[-1]] += sizes[descendant]
stack.append(child)
sizes[child] = 1
for child, parent in nx.utils.pairwise(reversed(stack)):
sizes[parent] += sizes[child]
return sizes
[docs]
@nx.utils.not_implemented_for("directed")
@nx._dispatchable
def centroid(G):
"""Return the centroid of an unweighted tree.
The centroid of a tree is the set of nodes such that removing any
one of them would split the tree into a forest of subtrees, each
with at most ``N / 2`` nodes, where ``N`` is the number of nodes
in the original tree. This set may contain two nodes if removing
an edge between them results in two trees of size exactly ``N /
2``.
Parameters
----------
G : NetworkX graph
A tree.
Returns
-------
c : list
List of nodes in centroid of the tree. This could be one or two nodes.
Raises
------
NotATree
If the input graph is not a tree.
NotImplementedException
If the input graph is directed.
NetworkXPointlessConcept
If `G` has no nodes or edges.
Notes
-----
This algorithm's time complexity is ``O(N)`` where ``N`` is the
number of nodes in the tree.
In unweighted trees the centroid coincides with the barycenter,
the node or nodes that minimize the sum of distances to all other
nodes. However, this concept is different from that of the graph
center, which is the set of nodes minimizing the maximum distance
to all other nodes.
Examples
--------
>>> G = nx.path_graph(4)
>>> nx.tree.centroid(G)
[1, 2]
A star-shaped tree with one long branch illustrates the difference
between the centroid and the center. The center lies near the
middle of the long branch, minimizing maximum distance. The
centroid, however, limits the size of any resulting subtree to at
most half the total nodes, forcing it to remain near the hub when
enough short branches are present.
>>> G = nx.star_graph(6)
>>> nx.add_path(G, [6, 7, 8, 9, 10])
>>> nx.tree.centroid(G), nx.tree.center(G)
([0], [7])
See Also
--------
:func:`~networkx.algorithms.distance_measures.barycenter`
:func:`~networkx.algorithms.distance_measures.center`
center : tree center
"""
if not nx.is_tree(G):
raise nx.NotATree("provided graph is not a tree")
prev, root = None, nx.utils.arbitrary_element(G)
sizes = _subtree_sizes(G, root)
total_size = G.number_of_nodes()
def _heaviest_child(prev, root):
return max(
(x for x in G.neighbors(root) if x != prev), key=sizes.get, default=None
)
hc = _heaviest_child(prev, root)
while max(total_size - sizes[root], sizes.get(hc, 0)) > total_size / 2:
prev, root = root, hc
hc = _heaviest_child(prev, root)
return [root] + [
x for x in G.neighbors(root) if x != prev and sizes[x] == total_size / 2
]
