Layout geometry for tree structures / laying out nodes attractively
I have a tree-lik开发者_StackOverflow中文版e data structure and I'd like to draw it on an SVG canvas (using jQuery SVG.) I'd like to render the nodes spreading out from top to bottom in an attractively-spaced manner.
Ideally I need a class or function to which I can pass a representation of the tree and get back the X and Y coordinates of each node. Unfortunately my Googling has been frustrated by thousands of hits for the list-tree GUI widget, which isn't what I want.
Ideally this would be some Javascript, but I could also use some Python (used on the server-side.) I had a look at this Python stuff on Github but I really can't make head-nor-tail of its usage (or get it to run.) I've also had a brief look at ete2a1, but it has failed to install properly, the docs are unfinished, and it seems more geared to actually rendering trees as images rather than doing geometry.
Apologies if this is a vague question, let me know if I can make it clearer. Basically, I've got this:
Tree("Root",
Tree("leaf 1",
Tree("leaf 2",
Tree("leaf 4"),
Tree("leaf 5")), Tree("leaf 3",
Tree("leaf 6"))))
which would render:
Root
|
leaf 1
|
/\
/ \
leaf 2 leaf 3
/\ \
/ \ \
leaf 4 leaf 5 leaf 6
(Ugh, that might not be quite right, but you get the idea.)
Any tips greatly appreciated!
I highly recommend d3.js. This collapsible dendrogram is great for large datasets. There's also a regular dendrogram. Very easy to just plug and play, especially with jQuery background.
I worked on this some time ago and dug out my old implementation in javascript.
This assumes all nodes have the same width, but it will generalize nicely to the case where each node contains its own custom width. Just look for node_size references and generalize accordingly.
Below is a complete HTML file with the javascript embedded. Refreshing the browser makes a new random tree and draws it. But you can ignore my drawing routines that use old CSS tricks to render boxes and lines. The coordinates are stored in the tree nodes.
Here is an example output. It shows the only significant weakness. It's "left greedy". Where a subtree like that rooted at 60 could slide left and right, it will always be as far left as possible. A special purpose hack solves this for leaves between non-leaves of the same parent, e.g. 73. A general solution is trickier.
<html>
<head>
<style>
.node {
position: absolute;
background-color: #0000cc;
color: #ffffff;
font-size: 12px;
font-family: sans-serif;
text-align: center;
vertical-align: middle;
border: 1px solid #000088;
}
.dot {
position: absolute;
background-color: black;
width: 1px;
height: 1px;
overflow:hidden;
}
</style>
<script>
var node_size = 18
var horizontal_gap = 16
var vertical_gap = 32
// Draw a graph node.
function node(lbl, x, y, sz) {
if (!sz) sz = node_size
var h = sz / 2
document.write('<div class="node" style="left:' + (x - h) + 'px;top:' + (y - h) +
'px;width:' + sz + 'px;height:' + sz + 'px;line-height:' + sz +
'px;">' + lbl + '</div>')
}
// Draw a 1-pixel black dot.
function dot(x, y) {
document.write('<div class="dot" style="left:' + x + 'px;top:' + y + 'px;"></div>')
}
// Draw a line between two points. Slow but sure...
function arc(x0, y0, x1, y1) {
var dx = x1 - x0
var dy = y1 - y0
var x = x0
var y = y0
if (abs(dx) > abs(dy)) {
var yinc = dy / dx
if (dx < 0)
while (x >= x1) { dot(x, y); --x; y -= yinc }
else
while (x <= x1) { dot(x, y); ++x; y += yinc }
}
else {
var xinc = dx / dy
if (dy < 0)
while (y >= y1) { dot(x, y); --y; x -= xinc }
else
while (y <= y1) { dot(x, y); ++y; x += xinc }
}
}
// Tree node.
function Tree(lbl, children) {
this.lbl = lbl
this.children = children ? children : []
// This will be filled with the x-offset of this node wrt its parent.
this.offset = 0
// Optional coordinates that can be written by place(x, y)
this.x = 0
this.y = 0
}
Tree.prototype.is_leaf = function() { return this.children.length == 0 }
// Label the tree with given root (x,y) coordinates using the offset
// information created by extent().
Tree.prototype.place = function(x, y) {
var n_children = this.children.length
var y_children = y + vertical_gap + node_size
for (var i = 0; i < n_children; i++) {
var child = this.children[i]
child.place(x + child.offset, y_children)
}
this.x = x
this.y = y
}
// Draw the tree after it has been labeled w ith extent() and place().
Tree.prototype.draw = function () {
var n_children = this.children.length
for (var i = 0; i < n_children; i++) {
var child = this.children[i]
arc(this.x, this.y + 0.5 * node_size + 2, child.x, child.y - 0.5 * node_size)
child.draw()
}
node(this.lbl, this.x, this.y)
}
// Recursively assign offsets to subtrees and return an extent
// that gives the shape of this tree.
//
// An extent is an array of left-right x-coordinate ranges,
// one element per tree level. The root of the tree is at
// the origin of its coordinate system.
//
// We merge successive extents by finding the minimum shift
// to the right that will cause the extent being merged to
// not overlap any of the previous ones.
Tree.prototype.extent = function() {
var n_children = this.children.length
// Get the extents of the children
var child_extents = []
for (var i = 0; i < n_children; i++)
child_extents.push(this.children[i].extent())
// Compute a minimum non-overlapping x-offset for each extent
var rightmost = []
var offset = 0
for (i = 0; i < n_children; i++) {
var ext = child_extents[i]
// Find the necessary offset.
offset = 0
for (var j = 0; j < min(ext.length, rightmost.length); j++)
offset = max(offset, rightmost[j] - ext[j][0] + horizontal_gap)
// Update rightmost
for (var j = 0; j < ext.length; j++)
if (j < rightmost.length)
rightmost[j] = offset + ext[j][1]
else
rightmost.push(offset + ext[j][1])
this.children[i].offset = offset
}
rightmost = null // Gc, come get it.
// Center leaves between non-leaf siblings with a tiny state machine.
// This is optional, but eliminates a minor leftward skew in appearance.
var state = 0
var i0 = 0
for (i = 0; i < n_children; i++) {
if (state == 0) {
state = this.children[i].is_leaf() ? 3 : 1
} else if (state == 1) {
if (this.children[i].is_leaf()) {
state = 2
i0 = i - 1 // Found leaf after non-leaf. Remember the non-leaf.
}
} else if (state == 2) {
if (!this.children[i].is_leaf()) {
state = 1 // Found matching non-leaf. Reposition the leaves between.
var dofs = (this.children[i].offset - this.children[i0].offset) / (i - i0)
offset = this.children[i0].offset
for (j = i0 + 1; j < i; j++)
this.children[j].offset = (offset += dofs)
}
} else {
if (!this.children[i].is_leaf()) state = 1
}
}
// Adjust to center the root on its children
for (i = 0; i < n_children; i++)
this.children[i].offset -= 0.5 * offset
// Merge the offset extents of the children into one for this tree
var rtn = [ [-0.5 * node_size, 0.5 * node_size] ]
// Keep track of subtrees currently on left and right edges.
var lft = 0
var rgt = n_children - 1
i = 0
for (i = 0; lft <= rgt; i++) {
while (lft <= rgt && i >= child_extents[lft].length) ++lft
while (lft <= rgt && i >= child_extents[rgt].length) --rgt
if (lft > rgt) break
var x0 = child_extents[lft][i][0] + this.children[lft].offset
var x1 = child_extents[rgt][i][1] + this.children[rgt].offset
rtn.push([x0, x1])
}
return rtn
}
// Return what the bounding box for the tree would be if it were drawn at (0,0).
// To place it at the upper left corner of a div, draw at (-bb[0], -bb[1])
// The box is given as [x_left, y_top, width, height]
function bounding_box(extent) {
var x0 = extent[0][0]
var x1 = extent[0][1]
for (var i = 1; i < extent.length; i++) {
x0 = min(x0, extent[i][0])
x1 = max(x1, extent[i][1])
}
return [x0, -0.5 * node_size, x1 - x0, (node_size + vertical_gap) * extent.length - vertical_gap ]
}
function min(x, y) { return x < y ? x : y }
function max(x, y) { return x > y ? x : y }
function abs(x) { return x < 0 ? -x : x }
// Generate a random tree with given depth and minimum number of children of the root.
// The min_children field is optional. Use e.g. 2 to avoid trivial trees.
var node_label = 0
function random_tree(depth, min_children) {
var n_children = depth <= 1 || Math.random() < 0.5 ? 0 : Math.round(Math.random() * 4)
if (min_children) n_children = max(n_children, min_children)
var children = []
for (var i = 0; i < n_children; i++)
children.push(random_tree(depth - 1, min_children - 1))
return new Tree('' + node_label++, children)
}
</script>
</head>
<body>
<div style="width:1000px;height:800px">
<script>
// Generate a random tree.
tree = random_tree(10, 2)
// Label it with node offsets and get its extent.
e = tree.extent()
// Retrieve a bounding box [x,y,width,height] from the extent.
bb = bounding_box(e)
// Label each node with its (x,y) coordinate placing root at given location.
tree.place(-bb[0] + horizontal_gap, -bb[1] + horizontal_gap)
// Draw using the labels.
tree.draw()
</script>
</div>
</body>
</html>
I'm going to provide an answer here based on the Python I hacked together two years ago, although it's far from a good one. As Oli Charlesworth suggested, I used Graphviz via PyDot. The full script is posted below, but first the setup I had to do to make it work (assuming you're using virtualenv):
First, make sure graphviz is installed. Assuming you're using something with apt:
$> sudo apt-get install graphviz
Make a new virtualenv with virtualenv wrapper:
$> mkvirtualenv pydot
In the new virtualenv, pin the pyparsing version to a pre-2.0 one (required for the dot_parser to work):
(pydot)$> pip install pyparsing==1.5.7
Install pydot:
(pydot)$> pip install pydot
Now the Python I used (warning: it is not nice):
import os
import re
import sys
import tempfile
import pydot
TEST_GRAPH = {
"Root" : {
"inputs" : [],
},
"Leaf1" : {
"inputs" : ["Root"],
},
"Leaf2" : {
"inputs" : ["Leaf1"],
},
"Leaf3" : {
"inputs" : ["Leaf1"],
},
"Leaf4" : {
"inputs" : ["Leaf2"],
},
"Leaf5" : {
"inputs" : ["Leaf2"],
},
"Leaf6" : {
"inputs" : ["Leaf3"],
},
}
class DotError(StandardError):
"""Dot problems."""
# http://www.graphviz.org/doc/info/lang.html
RAW_NAME_RE = r"(^[A-Za-z_][a-zA-Z0-9_]*$)|(^-?([.[0-9]+|[0-9]+(.[0-9]*)?)$)"
def conditional_quote(name):
"""Dot quotes names if they match the regex above, otherwise not"""
if re.match(RAW_NAME_RE, name) is None:
return "\"%s\"" % name
return name
def get_node_positions(nodedict, aspect=None):
"""Build the pydot graph, outputting a dictionary of name -> [x,y]"""
# Tweak positioning parameters as required:
g = pydot.Dot(margin="0.1", ranksep="0.7", nodesep="1.5")
if aspect is not None:
g.set_aspect(round(aspect))
for name, node in nodedict.items():
n = pydot.Node(name, width="0.5", fixedsize="0.5")
g.add_node(n)
for name, node in nodedict.items():
for i in node["inputs"]:
try:
src = g.get_node(conditional_quote(i))
if isinstance(src, list):
src = src[0]
dst = g.get_node(conditional_quote(name))
if isinstance(dst, list):
dst = dst[0]
g.add_edge(pydot.Edge(src, dst))
except IndexError:
print "Input %s not found" % i
# dot doesn't seem to work on < 4 nodes... prevent it from
# by just throwing an error
if len(nodedict) < 4:
raise DotError("Dot breaks with less than 4 nodes.")
# Now the particularly horrible bit. Write the script as a dot file,
# then read it in again and extract the positionings.
# WARNING: Currently doesn't clean up the temp file.
with tempfile.NamedTemporaryFile(delete=False, suffix=".dot") as t:
t.close()
g.write_dot(t.name)
g = pydot.graph_from_dot_file(t.name)
out = {}
for name, node in nodedict.items():
gn = g.get_node(conditional_quote(name))
if isinstance(gn, list):
gn = gn[0]
out[name] = [int(d) \
for d in gn.get_pos().replace('"', "").split(",")]
return out
if __name__ == "__main__":
print(get_node_positions(TEST_GRAPH))
Although this is pretty ugly, it did more or less serve my purposes. I'd be interested to see a nicer solution if anyone can find one.
加载中,请稍侯......
精彩评论