Skip to content

Instantly share code, notes, and snippets.

@nitaku

nitaku/README.md

Last active October 15, 2015 20:15
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nitaku/f0b021b0a56fee82dd97 to your computer and use it in GitHub Desktop.
Save nitaku/f0b021b0a56fee82dd97 to your computer and use it in GitHub Desktop.
Download ZIP
Tangled tree II
Raw
README.md

An improved layout for tangled trees. With respect to the first example, which only constrained the layout to always produce downward links, this one also ensures that nodes at the same depth are keep aligned.

As in this quite old example, we used the maximum distance from a node to a root to introduce the concept of depth (remember that a tangled tree structure is not actually a tree). Longest path algorithms are not so common, so we relied on a technique based on topological sorting. A simple JS snippet by Shinout is used to perform the topological sorting.

Raw
index.coffee
graph = {
nodes: [
{id: 'A'},
{id: 'B'},
{id: 'C'},
{id: 'D'},
{id: 'E'},
{id: 'F'},
{id: 'G'},
{id: 'H'},
{id: 'I'},
{id: 'J'},
{id: 'Z'}
],
links: [
{id: 1, source: 'A', target: 'B'},
{id: 2, source: 'A', target: 'C'},
{id: 3, source: 'A', target: 'D'},
{id: 4, source: 'B', target: 'E'},
{id: 5, source: 'B', target: 'F'},
{id: 6, source: 'C', target: 'G'},
{id: 7, source: 'C', target: 'F'},
{id: 8, source: 'F', target: 'G'},
{id: 9, source: 'G', target: 'H'},
{id: 10, source: 'G', target: 'I'},
{id: 11, source: 'H', target: 'I'},
{id: 12, source: 'I', target: 'J'},
{id: 13, source: 'Z', target: 'B'},
]
}
### objectify the graph ###
### resolve node IDs (not optimized at all!) ###
for l in graph.links
for n in graph.nodes
if l.source is n.id
l.source = n
if l.target is n.id
l.target = n
### store the node index into the node itself ###
for n, i in graph.nodes
n.i = i
### store neighbor nodes into each node ###
for n, i in graph.nodes
n.in_neighbors = []
n.out_neighbors = []
for l in graph.links
l.source.out_neighbors.push l.target
l.target.in_neighbors.push l.source
### compute longest distances ###
topological_order = tsort(graph.links.map (l) -> [l.source.i, l.target.i])
# console.debug 'Topological order: ' + topological_order
for n in graph.nodes
n.longest_dist = -Infinity
# A (0) and Z (0) are root nodes
graph.nodes[0].longest_dist = 0
graph.nodes[10].longest_dist = 0
for i in topological_order
n = graph.nodes[i]
for nn in n.out_neighbors
if nn.longest_dist < n.longest_dist+1
nn.longest_dist = n.longest_dist+1
# console.debug graph.nodes
graph.constraints = []
### create the alignment contraints ###
levels = _.uniq graph.nodes.map (n) -> n.longest_dist
levels.forEach (depth) ->
graph.constraints.push {
type: 'alignment',
axis: 'y',
offsets: graph.nodes.filter((n) -> n.longest_dist is depth).map (n) -> {
node: n.i,
offset: 0
}
}
R = 18
PAD_MULTIPLIER = 3.5
### create the position contraints ###
levels.forEach (depth, i) ->
if i < levels.length-1
n1 = _.find graph.nodes, (n) -> n.longest_dist is depth
n2 = _.find graph.nodes, (n) -> n.longest_dist is depth+1
graph.constraints.push {
axis: 'y',
left: n1.i,
right: n2.i,
gap: 2*R
}
svg = d3.select('svg')
width = svg.node().getBoundingClientRect().width
height = svg.node().getBoundingClientRect().height
defs = svg.append('defs')
### define arrow markers for graph links ###
defs.append('marker')
.attr
id: 'end-arrow'
viewBox: '0 0 10 10'
refX: 4+R
refY: 5
orient: 'auto'
.append('path')
.attr
d: 'M0,0 L0,10 L10,5 z'
### create nodes and links ###
links = svg.selectAll('.link')
.data(graph.links, (d) -> d.id)
links
.enter().append('line')
.attr('class', 'link')
nodes = svg.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')
### cola layout ###
graph.nodes.forEach (v) ->
v.width = PAD_MULTIPLIER*R
v.height = PAD_MULTIPLIER*R
d3cola = cola.d3adaptor()
.size([width, height])
.linkDistance(60)
.constraints(graph.constraints)
.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(100,30,30)
Raw
index.css
.node > circle {
fill: #dddddd;
stroke: #777777;
stroke-width: 2px;
}
.node > text {
font-family: sans-serif;
text-anchor: middle;
pointer-events: none;
}
.link {
stroke: #DDD;
stroke-width: 4px;
marker-end: url(#end-arrow);
}
#end-arrow {
fill: #DDD;
}
Raw
index.html
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Tangled tree II</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>
<script src="tsort.js"></script>
<script src="http://cdnjs.cloudflare.com/ajax/libs/lodash.js/3.10.0/lodash.min.js"></script>
</head>
<body>
<svg width="960px" height="500px"></svg>
<script src="index.js"></script>
</body>
</html>
Raw
index.js
// Generated by CoffeeScript 1.4.0
(function() {
var PAD_MULTIPLIER, R, d3cola, defs, enter_nodes, graph, height, i, l, levels, links, n, nn, nodes, svg, topological_order, width, _i, _j, _k, _l, _len, _len1, _len2, _len3, _len4, _len5, _len6, _len7, _m, _n, _o, _p, _ref, _ref1, _ref2, _ref3, _ref4, _ref5, _ref6;
graph = {
nodes: [
{
id: 'A'
}, {
id: 'B'
}, {
id: 'C'
}, {
id: 'D'
}, {
id: 'E'
}, {
id: 'F'
}, {
id: 'G'
}, {
id: 'H'
}, {
id: 'I'
}, {
id: 'J'
}, {
id: 'Z'
}
],
links: [
{
id: 1,
source: 'A',
target: 'B'
}, {
id: 2,
source: 'A',
target: 'C'
}, {
id: 3,
source: 'A',
target: 'D'
}, {
id: 4,
source: 'B',
target: 'E'
}, {
id: 5,
source: 'B',
target: 'F'
}, {
id: 6,
source: 'C',
target: 'G'
}, {
id: 7,
source: 'C',
target: 'F'
}, {
id: 8,
source: 'F',
target: 'G'
}, {
id: 9,
source: 'G',
target: 'H'
}, {
id: 10,
source: 'G',
target: 'I'
}, {
id: 11,
source: 'H',
target: 'I'
}, {
id: 12,
source: 'I',
target: 'J'
}, {
id: 13,
source: 'Z',
target: 'B'
}
]
};
/* objectify the graph
*/
/* resolve node IDs (not optimized at all!)
*/
_ref = graph.links;
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
l = _ref[_i];
_ref1 = graph.nodes;
for (_j = 0, _len1 = _ref1.length; _j < _len1; _j++) {
n = _ref1[_j];
if (l.source === n.id) {
l.source = n;
}
if (l.target === n.id) {
l.target = n;
}
}
}
/* store the node index into the node itself
*/
_ref2 = graph.nodes;
for (i = _k = 0, _len2 = _ref2.length; _k < _len2; i = ++_k) {
n = _ref2[i];
n.i = i;
}
/* store neighbor nodes into each node
*/
_ref3 = graph.nodes;
for (i = _l = 0, _len3 = _ref3.length; _l < _len3; i = ++_l) {
n = _ref3[i];
n.in_neighbors = [];
n.out_neighbors = [];
}
_ref4 = graph.links;
for (_m = 0, _len4 = _ref4.length; _m < _len4; _m++) {
l = _ref4[_m];
l.source.out_neighbors.push(l.target);
l.target.in_neighbors.push(l.source);
}
/* compute longest distances
*/
topological_order = tsort(graph.links.map(function(l) {
return [l.source.i, l.target.i];
}));
_ref5 = graph.nodes;
for (_n = 0, _len5 = _ref5.length; _n < _len5; _n++) {
n = _ref5[_n];
n.longest_dist = -Infinity;
}
graph.nodes[0].longest_dist = 0;
graph.nodes[10].longest_dist = 0;
for (_o = 0, _len6 = topological_order.length; _o < _len6; _o++) {
i = topological_order[_o];
n = graph.nodes[i];
_ref6 = n.out_neighbors;
for (_p = 0, _len7 = _ref6.length; _p < _len7; _p++) {
nn = _ref6[_p];
if (nn.longest_dist < n.longest_dist + 1) {
nn.longest_dist = n.longest_dist + 1;
}
}
}
graph.constraints = [];
/* create the alignment contraints
*/
levels = _.uniq(graph.nodes.map(function(n) {
return n.longest_dist;
}));
levels.forEach(function(depth) {
return graph.constraints.push({
type: 'alignment',
axis: 'y',
offsets: graph.nodes.filter(function(n) {
return n.longest_dist === depth;
}).map(function(n) {
return {
node: n.i,
offset: 0
};
})
});
});
R = 18;
PAD_MULTIPLIER = 3.5;
/* create the position contraints
*/
levels.forEach(function(depth, i) {
var n1, n2;
if (i < levels.length - 1) {
n1 = _.find(graph.nodes, function(n) {
return n.longest_dist === depth;
});
n2 = _.find(graph.nodes, function(n) {
return n.longest_dist === depth + 1;
});
return graph.constraints.push({
axis: 'y',
left: n1.i,
right: n2.i,
gap: 2 * R
});
}
});
svg = d3.select('svg');
width = svg.node().getBoundingClientRect().width;
height = svg.node().getBoundingClientRect().height;
defs = svg.append('defs');
/* define arrow markers for graph links
*/
defs.append('marker').attr({
id: 'end-arrow',
viewBox: '0 0 10 10',
refX: 4 + R,
refY: 5,
orient: 'auto'
}).append('path').attr({
d: 'M0,0 L0,10 L10,5 z'
});
/* create nodes and links
*/
links = svg.selectAll('.link').data(graph.links, function(d) {
return d.id;
});
links.enter().append('line').attr('class', 'link');
nodes = svg.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');
/* cola layout
*/
graph.nodes.forEach(function(v) {
v.width = PAD_MULTIPLIER * R;
return v.height = PAD_MULTIPLIER * R;
});
d3cola = cola.d3adaptor().size([width, height]).linkDistance(60).constraints(graph.constraints).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);
d3cola.start(100, 30, 30);
}).call(this);
Raw
tsort.js
/**
* general topological sort
* @author SHIN Suzuki (shinout310@gmail.com)
* @param Array<Array> edges : list of edges. each edge forms Array<ID,ID> e.g. [12 , 3]
*
* @returns Array : topological sorted list of IDs
**/
function tsort(edges) {
var nodes = {}, // hash: stringified id of the node => { id: id, afters: lisf of ids }
sorted = [], // sorted list of IDs ( returned value )
visited = {}; // hash: id of already visited node => true
var Node = function(id) {
this.id = id;
this.afters = [];
};
// 1. build data structures
edges.forEach(function(v) {
var from = v[0], to = v[1];
if (!nodes[from]) nodes[from] = new Node(from);
if (!nodes[to]) nodes[to] = new Node(to);
nodes[from].afters.push(to);
});
// 2. topological sort
Object.keys(nodes).forEach(function visit(idstr, ancestors) {
var node = nodes[idstr],
id = node.id;
// if already exists, do nothing
if (visited[idstr]) return;
if (!Array.isArray(ancestors)) ancestors = [];
ancestors.push(id);
visited[idstr] = true;
node.afters.forEach(function(afterID) {
if (ancestors.indexOf(afterID) >= 0) // if already in ancestors, a closed chain exists.
throw new Error('closed chain : ' + afterID + ' is in ' + id);
visit(afterID.toString(), ancestors.map(function(v) { return v })); // recursive call
});
sorted.unshift(id);
});
return sorted;
}
/**
* TEST
**/
function tsortTest() {
// example 1: success
var edges = [
[1, 2],
[1, 3],
[2, 4],
[3, 4]
];
var sorted = tsort(edges);
console.log(sorted);
// example 2: failure ( A > B > C > A )
edges = [
['A', 'B'],
['B', 'C'],
['C', 'A']
];
try {
sorted = tsort(edges);
}
catch (e) {
console.log(e.message);
}
// example 3: generate random edges
var max = 100, iteration = 30;
function randomInt(max) {
return Math.floor(Math.random() * max) + 1;
}
edges = (function() {
var ret = [], i = 0;
while (i++ < iteration) ret.push( [randomInt(max), randomInt(max)] );
return ret;
})();
try {
sorted = tsort(edges);
console.log("succeeded", sorted);
}
catch (e) {
console.log("failed", e.message);
}
}
// for node.js
if (typeof exports == 'object' && exports === this) {
module.exports = tsort;
if (process.argv[1] === __filename) tsortTest();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment