to_prufer_sequence(T)
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.
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)$.
An undirected graph object representing a tree.
If the number of nodes in T is less than two.
If T is not a tree.
If the set of nodes in T is not {0, …, n - 1}.
The Prüfer sequence of the given tree.
Returns the Prüfer sequence of the given tree.
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)See :
... list(tree2.edges()) == edges True
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.to_nested_tuple
networkx.algorithms.tree.coding.to_prufer_sequence
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