Module prufer 

Prüfer-sequence tree decoder (ALGO-CN-016).

Counterpart of igraph_from_prufer() in references/igraph/src/constructors/prufer.c:55-125.

A Prüfer sequence is a length-(n-2) string over the alphabet {0, 1, …, n-1} that uniquely encodes a labelled tree on n vertices. The bijection works in both directions:

• Encoding (not provided here — see igraph_to_prufer upstream): repeatedly remove the smallest-labelled leaf and record its sole neighbour’s label; stop with two vertices left.
• Decoding (this module): walk the sequence left-to-right, peel off the smallest leaf at each step, and emit the implied edges.

Implementation follows Micikevičius, Caminiti & Deo, “Linear-time Algorithms for Encoding Trees as Sequences of Node Labels”, which achieves O(n) instead of the naïve O(n²) priority-queue version. The trick is to track each vertex’s residual degree (how many times it still appears in the unread tail of the Prüfer sequence) and cascade through leaves discovered as a side-effect of removing one.

The decoder always produces an undirected tree on n vertices with exactly n - 1 edges. The empty Prüfer sequence yields the 2-vertex path graph P_2 (single edge 0—1).

Time complexity: O(|V|) where |V| = prufer.len() + 2.

Functions

from_prufer

Decode a Prüfer sequence into the unique labelled tree it represents.

to_prufer

Encode a labelled tree into its unique Prüfer sequence.