6 ms·
Tidier Drawings of Trees [pdf]
- mstolpm 11y agoTitle should contain (1981).
- bediger4000 11y agoI needed to draw tidy binary trees recently. I found the algorithm in this paper impenetrable, but the paper from which this one is derived (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150.4061&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.150...) had a very accessible algorithm, that produced results that I found acceptable.
- soegaard 11y agoThere are some improvements in Buchheim et al: ; http://dirk.jivas.de/papers/buchheim02improving.pdf http://dirk.jivas.de/papers/buchheim02improving.pdf See also "Compact layout of Layered Trees". Note that Bill Mill's blog post "Drawing Presentable Trees" presents the algorithm in a very readable manner: http://billmill.org/pymag-trees/
- mbostock 11y agoYep! This linear-time algorithm described by Buchheim et al. is used by d3.layout.tree: https://github.com/d3/d3-hierarchy/blob/master/src/tree.js https://github.com/d3/d3-hierarchy/blob/master/src/tree.js
- llimllib 11y agoI hadn't looked at that in forever! Glad somebody found it useful :) The layout is awful, so I just now limited the page width and centered the body, which should make it a bit more readable.
- peterhadlaw 11y agoThis is my Algorithms professor at IIT! :)
- channon 11y agohttps://iit.edu/news/iittoday/?p=47371 https://iit.edu/news/iittoday/?p=47371
- lemming 11y agoI love the fact that old papers often contain the complete source code to an implementation of the algorithm they're discussing.
- cm2187 11y agoDoes anyone know a good algorithm for drawing a genealogy tree? I tried playing with this problem and it is quite hard to find something that looks OK. The problem is that it is a tree that has branches going both way (up and down).
- rch 11y agoHow well does graphviz handle your trees?
- vidarh 11y agoHere's an example of part of my family tree with Graphviz [1] (using dot layout), and here's one with all my known ancestors [2] (using neato). A reasonably small subset works ok with dot (e.g. note that the first example excludes all siblings for example). [1] http://hokstad.com/family-tree-using-graphviz-and-ruby http://hokstad.com/family-tree-using-graphviz-and-ruby [2] http://hokstad.com/all-my-known-ancestors http://hokstad.com/all-my-known-ancestors
- rch 11y agoI see what you mean. Try grouping siblings into subgraphs, and adjusting the length of edges between generations to approximate shells. You might try NetworkX as well. I don't think it offers a better layout engine for you, but it supports graphviz and is awfully convenient for working with the graph itself.
- austinjp 11y agoI would be very interested in solutions to this. It strikes me that genealogy trees are multi-dimensional, and compressing them to two dimensions makes layout far less optimal.
- cm2187 11y agoPlus there are lots of constraints. People of the same generation have to appear on the same vertical level. And there are lots of configurations that are simply impossible to represent. For instance a couple with three kids, each of them marries someone, how do we represent the parents of who they marry without crossing lines? Or it is relatively easy to represent someone having children from two different wives but how about three different wives without crossing lines? And then it needs to look reasonably compact to be visually helpful. So it's a kind of a best effort basis.
- xtrm1 11y agoIf you look closely enough, John S Tilford is effing Hackerman!!! OMG he did hack time