Skip to content

Instantly share code, notes, and snippets.

@nitaku

nitaku/README.md

Last active March 9, 2020 10:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save nitaku/edf634f58f6ad7aec0c0 to your computer and use it in GitHub Desktop.
Save nitaku/edf634f58f6ad7aec0c0 to your computer and use it in GitHub Desktop.
Download ZIP
Prüfer sequence
Raw
README.md

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

Raw
index.coffee
# 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)
Raw
index.css
.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;
}
Raw
index.html
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Prüfer sequence</title>
<link rel="stylesheet" href="index.css">
<script src="http://d3js.org/d3.v3.min.js"></script>
<script src="http://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>
Raw
index.js
// 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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment