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).
// Generated by CoffeeScript 1.4.0
(function() {
var R, attempt, height, input, links_layer, load, nodes_layer, prufer2graph, redraw, select, svg, width;
prufer2graph = function(prufer) {
var degree, graph, i, n, t, u, v, _i, _len, _ref;
prufer = prufer.map(function(i) {
return i - 1;
});
t = prufer.length;
graph = {
nodes: d3.range(t + 2).map(function(i) {
return {
id: i + 1
};
}),
links: []
};
degree = d3.range(t + 2).map(function() {
return 1;
});
prufer.forEach(function(i) {
if (i > t) {
throw 'Invalid Prufer sequence!';
}
return degree[i] += 1;
});
prufer.forEach(function(i) {
var j, n, _i, _len, _ref, _results;
_ref = graph.nodes;
_results = [];
for (j = _i = 0, _len = _ref.length; _i < _len; j = ++_i) {
n = _ref[j];
if (degree[j] === 1) {
graph.links.push({
source: graph.nodes[i],
target: n,
id: "(" + (Math.min(i, j)) + ")--(" + (Math.max(i, j)) + ")"
});
degree[i] -= 1;
degree[j] -= 1;
break;
} else {
_results.push(void 0);
}
}
return _results;
});
u = null;
v = null;
_ref = graph.nodes;
for (i = _i = 0, _len = _ref.length; _i < _len; i = ++_i) {
n = _ref[i];
if (degree[i] === 1) {
if (u === null) {
u = n;
} else {
v = n;
break;
}
}
}
graph.links.push({
source: u,
target: v,
id: "(" + (Math.min(u.id, v.id)) + ")--(" + (Math.max(u.id, v.id)) + ")"
});
return graph;
};
R = 16;
svg = d3.select('svg');
width = svg.node().getBoundingClientRect().width;
height = svg.node().getBoundingClientRect().height;
links_layer = svg.append('g');
nodes_layer = svg.append('g');
redraw = function(data) {
var d3cola, enter_nodes, graph, links, nodes;
graph = prufer2graph(data);
/* create nodes and links
*/
nodes = nodes_layer.selectAll('.node').data(graph.nodes, function(d) {
return d.id;
});
enter_nodes = nodes.enter().append('g').attr('class', 'node');
enter_nodes.append('circle').attr('r', R);
/* draw the label
*/
enter_nodes.append('text').text(function(d) {
return d.id;
}).attr('dy', '0.35em');
nodes.exit().remove();
links = links_layer.selectAll('.link').data(graph.links, function(d) {
return d.id;
});
links.enter().append('line').attr('class', 'link');
links.exit().remove();
/* cola layout
*/
graph.nodes.forEach(function(v) {
v.width = 2.5 * R;
return v.height = 2.5 * R;
});
d3cola = cola.d3adaptor().size([width, height]).linkDistance(40).avoidOverlaps(true).nodes(graph.nodes).links(graph.links).on('tick', function() {
/* update nodes and links
*/
nodes.attr('transform', function(d) {
return "translate(" + d.x + "," + d.y + ")";
});
return links.attr('x1', function(d) {
return d.source.x;
}).attr('y1', function(d) {
return d.source.y;
}).attr('x2', function(d) {
return d.target.x;
}).attr('y2', function(d) {
return d.target.y;
});
});
enter_nodes.call(d3cola.drag);
return d3cola.start(30, 30, 30);
};
input = d3.select('input');
input.on('input', function() {
return attempt(this.value);
});
select = d3.select('select');
select.on('input', function() {
return load(this.value);
});
load = function(value) {
input.node().value = value;
return attempt(value);
};
attempt = function(value) {
var data;
try {
data = JSON.parse(value);
redraw(data);
return input.classed('error', false);
} catch (e) {
return input.classed('error', true);
}
};
load(select.node().value);
}).call(this);
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Prüfer sequence</title>
<link rel="stylesheet" href="index.css">
<script src="//d3js.org/d3.v3.min.js"></script>
<script src="//marvl.infotech.monash.edu/webcola/cola.v3.min.js"></script>
</head>
<body>
<svg width="960px" height="500px"></svg>
<input type='text'>
<select>
<option value='[4,3,4,5,6,7,3,3,6,6,6,2,5,2,1,8,8]' label='Large'>
<option value='[1,2,1,3,3,5]' label='Medium'>
<option value='[4,4,4,5]' label='Small'>
<option value='[1,2,5,2,2,2,6,1,7,8,10,10,3,3,16,6,6,12,15,2,1,8,8,2,2,4,6,9,19,8,7,12,11,4,2,19,11,9,9,7]' label='Huge'>
<option value='[1,1,1,1,1,1]' label='Asterisk'>
<option value='[2,1,3,1,4,1,5,1,6]' label='Star'>
<option value='[1]' label='Minimal I'>
<option value='[2]' label='Minimal II'>
<option value='[]' label='Null'>
</select>
<script src="index.js"></script>
</body>
</html>
# https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence
prufer2graph = (prufer) ->
prufer = prufer.map (i) -> i-1 # convert to zero-based indexing
t = prufer.length
graph = {
nodes: d3.range(t+2).map (i) -> {id: i+1}
links: []
}
degree = d3.range(t+2).map () -> 1
prufer.forEach (i) ->
if i > t
throw 'Invalid Prufer sequence!'
degree[i] += 1
prufer.forEach (i) ->
for n, j in graph.nodes
if degree[j] is 1
graph.links.push {source: graph.nodes[i], target: n, id: "(#{Math.min(i,j)})--(#{Math.max(i,j)})"}
degree[i] -= 1
degree[j] -= 1
break
u = null
v = null
for n,i in graph.nodes
if degree[i] is 1
if u is null
u = n
else
v = n
break
graph.links.push {source: u, target: v, id: "(#{Math.min(u.id,v.id)})--(#{Math.max(u.id,v.id)})"}
return graph
R = 16
svg = d3.select('svg')
width = svg.node().getBoundingClientRect().width
height = svg.node().getBoundingClientRect().height
links_layer = svg.append('g')
nodes_layer = svg.append('g')
redraw = (data) ->
graph = prufer2graph(data)
### create nodes and links ###
nodes = nodes_layer.selectAll('.node')
.data(graph.nodes, (d) -> d.id)
enter_nodes = nodes.enter().append('g')
.attr('class', 'node')
enter_nodes.append('circle')
.attr('r', R)
### draw the label ###
enter_nodes.append('text')
.text((d) -> d.id)
.attr('dy', '0.35em')
nodes.exit().remove()
links = links_layer.selectAll('.link')
.data(graph.links, (d) -> d.id)
links
.enter().append('line')
.attr('class', 'link')
links.exit().remove()
### cola layout ###
graph.nodes.forEach (v) ->
v.width = 2.5*R
v.height = 2.5*R
d3cola = cola.d3adaptor()
.size([width, height])
.linkDistance(40)
.avoidOverlaps(true)
.nodes(graph.nodes)
.links(graph.links)
.on 'tick', () ->
### update nodes and links ###
nodes
.attr('transform', (d) -> "translate(#{d.x},#{d.y})")
links
.attr('x1', (d) -> d.source.x)
.attr('y1', (d) -> d.source.y)
.attr('x2', (d) -> d.target.x)
.attr('y2', (d) -> d.target.y)
enter_nodes
.call(d3cola.drag)
d3cola.start(30,30,30)
input = d3.select('input')
input.on 'input', () -> attempt(this.value)
select = d3.select('select')
select.on 'input', () -> load(this.value)
load = (value) ->
input.node().value = value
attempt(value)
attempt = (value) ->
try
data = JSON.parse value
redraw(data)
input.classed('error', false)
catch e
input.classed('error', true)
load(select.node().value).node > circle {
fill: #ddddee;
stroke: #777788;
stroke-width: 2px;
}
.node > text {
font-family: sans-serif;
text-anchor: middle;
pointer-events: none;
}
.link {
stroke: #eedddd;
stroke-width: 4px;
}
input {
position: absolute;
top: 10px;
left: 120px;
width: 826px;
height: 16px;
font-family: monospace;
}
input.error {
outline: 2px solid red;
}
select {
position: absolute;
top: 10px;
left: 10px;
width: 100px;
height: 22px;
font-family: monospace;
}