networkx 2.8.2 Pypi GitHub Homepage
Other Docs
NotesParametersReturnsBackRef
from_prufer_sequence(sequence)

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.

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 networkx.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)$.

Parameters

sequence : list

A Prüfer sequence, which is a list of n - 2 integers between zero and n - 1, inclusive.

Returns

NetworkX graph

The tree corresponding to the given Prüfer sequence.

Returns the tree corresponding to the given Prüfer sequence.

See Also

from_nested_tuple
to_prufer_sequence

Examples

There is a bijection between Prüfer sequences and labeled trees, so this function is the inverse of the to_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
See :

Back References

The following pages refer to to this document either explicitly or contain code examples using this.

networkx.algorithms.tree.coding.from_prufer_sequence networkx.algorithms.tree.coding.from_nested_tuple networkx.algorithms.tree.coding.to_prufer_sequence

Local connectivity graph

Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.

Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)

SVG is more flexible but power hungry; and does not scale well to 50 + nodes.

All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them


GitHub : /networkx/algorithms/tree/coding.py#314
type: <class 'function'>
Commit: