Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# 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. The Prüfer sequence of the given tree. list NetworkXPointlessConcept – If the number of nodes in T is less than two. NotATree – If T is not a tree. KeyError – If the set of nodes in T 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  and has a running time of $$O(n \log n)$$.

References

  Wang, Xiaodong, Lei Wang, and Yingjie Wu. “An optimal algorithm for Prufer codes.” Journal of Software Engineering and Applications 2.02 (2009): 111.

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