Drawing tree in OCaml GUI, best option?

Learning
41

Alright in that case something like this naive implementation could also work (but the output is not very pretty):

42

interesting project! in fact i my tree is also a biological one: cell lifetimes in a cell culture. i tried cloning an installing your repo but cannot build it.

File "tree/lib/draw.ml", line 69, characters 34-39:
Error: The function applied to this argument has type
         string -> w:float -> h:float -> Cairo.Surface.t
This argument cannot be applied with label ~fname

this appears after some warnings like this one:

File "tree/lib/tree.ml", line 15, characters 13-22:
Error (warning 49): no cmi file was found in path for module Tree__Sig
43

Famous last words.

I have a project that aims to collect algorithms to layout trees: GitHub - Drup/tree_layout: Algorithms to layout trees in a pretty manner.

I suspect the “Layered” algorithm would be sufficient for your purpose, but you can also find lot’s of different type of tree visualisation here. Formally, what you are looking for is an algorithm for layered trees where the rank of nodes is prescribed. There are several such algorithms.

If you end up implementing something from the literature (or improving on it), I would be happy to add it to the collection! :slight_smile:

1 Like
44

Yes, the rank is prescribed but i would also want to constrain the width; this may require bending some branches inwards, towards a straight centerline. What I would imagine could work is a constrained force-directed layout where only the width-coordinates are allowed to adapt in order to 1. keep edges non-overlapping and short and 2. keep vertices close to a centerline (in the width coordinate x) and 3. keep vertices separated.

45

I find force-based layouts usually unreliable and resulting in layouts that are not so nice in practice. What about [PDF] Compact Layout of Layered Trees | Semantic Scholar ?

We present two new drawing conventions which reduce the layout width to be less than some maximum width while still maintaining the essential layered drawing convention.

Stacktrees are also relevant: http://vis.cs.ucdavis.edu/papers/evevis-evolutionary-vis.pdf

2 Likes
46

Yes sorry the master branch is very behind right now.
If you want to build you can pull branch devel-john, but apparently there’s a problem with the Cairo version.
But I implemented this as a quick hack, so don’t hesitate to grab the code to adapt it to your needs, but otherwise Drup’s pointers might be more useful.

47

thanks for all the pointers. the stacktrees do look similar to what i was imagining; the first link you gave seems to deal mainly with integer ranks, which is not exactly my use case.

48

Yeah I was thinking something else entirely at the time of writing, that didn’t sound right at all. I think I meant to say for a very specific case the algorithm could be simple, but didn’t mean to suggest it’d be easy in general.

And interesting project - I recall seeing it quite recently, I was thinking about replacing Dagre with it as well, but I was too busy to commit to that.