center#

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:

GNetworkX graph: A tree graph (undirected, acyclic graph).

Returns:

centerlist: 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]