networkx.algorithms.tree.coding.to_prufer_sequence¶

to_prufer_sequence
(T)[source]¶ Returns the Prüfer sequence of the given tree.
A Prüfer sequence is a list of n  2 numbers between 0 and n  1, inclusive. The tree corresponding to a given Prüfer sequence can be recovered by repeatedly joining a node in the sequence with a node with the smallest potential degree according to the sequence.
Parameters: T (NetworkX graph) – An undirected graph object representing a tree.
Returns: The Prüfer sequence of the given tree.
Return type: list
Raises: NetworkXPointlessConcept
– If the number of nodes inT
is less than two.NotATree
– IfT
is not a tree.KeyError
– If the set of nodes inT
is not {0, …, n  1}.
Notes
There is a bijection from labeled trees to Prüfer sequences. This function is the inverse of the
from_prufer_sequence()
function.Sometimes Prüfer sequences use nodes labeled from 1 to n instead of from 0 to n  1. This function requires nodes to be labeled in the latter form. You can use
relabel_nodes()
to relabel the nodes of your tree to the appropriate format.This implementation is from [1] and has a running time of \(O(n \log n)\).
See also
References
[1] Wang, Xiaodong, Lei Wang, and Yingjie Wu. “An optimal algorithm for Prufer codes.” Journal of Software Engineering and Applications 2.02 (2009): 111. <https://doi.org/10.4236/jsea.2009.22016> Examples
There is a bijection between Prüfer sequences and labeled trees, so this function is the inverse of the
from_prufer_sequence()
function:>>> edges = [(0, 3), (1, 3), (2, 3), (3, 4), (4, 5)] >>> tree = nx.Graph(edges) >>> sequence = nx.to_prufer_sequence(tree) >>> sequence [3, 3, 3, 4] >>> tree2 = nx.from_prufer_sequence(sequence) >>> list(tree2.edges()) == edges True