block by nitaku edf634f58f6ad7aec0c0

Prüfer sequence

Full Screen

A simple explorer of Prüfer sequences, a compact way of representing labeled trees.

Tree is used in a graph-theoretic meaning, i.e., they are undirected acyclic graphs. They also are labeled, so for example the tree (2)–(1)–(3) (P sequence = [1]) is different from (1)–(2)–(3) (P sequence = [2]). This is important when using Prüfer sequences for uniformly generating random tree topologies (i.e., unlabeled trees), since some topologies are more probable than others.

Code is mindlessly adapted from pseudocode found within the aforementioned Wikipedia page (and it seems to be slooow).

Useful links: a StackOverflow discussion about creating random trees with Prüfer sequences, an extensive blog post about creating random rooted trees (among other things).

index.js

index.html

index.coffee

index.css