OCaml: draw binary trees

Question

I am working on some programs using trees. I was wondering if there is any piece of code to draw general trees in OCaml.

type Tree = Node of Tree * int * Tree | Child of int;;

All I find on internet uses Caml Light, not Objective Caml.
Thanks in advance.

I have edited your question for better formatting. Note that the name "Objective Caml" is now depreciated, people are encouraged to say only "OCaml" (because the "Objective" part is not exactly prominent in everyday use, and because of the somewhat-frequent confusion with "Objective C"). — gasche, Mar 04 '12 at 16:06
Well, a [tree is a graph][1], so [1]: http://stackoverflow.com/questions/8999557/how-to-visualize-draw-automata-in-ocaml/9011334#9011334 — lambdapower, Mar 05 '12 at 20:22

score 12 · Accepted Answer · answered Mar 04 '12 at 16:16

Could you clarify what you mean by "draw"? I assume you're thinking of a graphical visualization of the tree?

I have had reasonably good experience with generating graph/tree descriptions in the dot format, used by the tool graphviz. The idea is that your OCaml program generates a textual representation of the graph in this format, then you use external tools to render it (turn it into an image), and possibly display it on the screen.

Dot works for general graphs. While you may find specialized tools for binary trees that have more features, in my experience it works rather well with all kind of trees and display something that is usually what you'd like. Now the tool is not without its flaws, and I've hit bugs (calling dot segfaults) in some cases. Still I think that's a reasonable choice.

How to output in dot format concretely: pick any example of already-existing graph, the structure will be quite obvious : it is only a textual format. Then you write your code running over the graph structure, calling Printf with the right stuff for labels, etc., and voila. For example, this example looks good, and here is the source format. I quote the relevant part:

/* courtesy Ian Darwin and Geoff Collyer, Softquad Inc. */
digraph unix {
    size="6,6";
    node [color=lightblue2, style=filled];
    "5th Edition" -> "6th Edition";
    "5th Edition" -> "PWB 1.0";
    "6th Edition" -> "LSX";
    "6th Edition" -> "Interdata";
    "Interdata" -> "Unix/TS 3.0";
    "Interdata" -> "PWB 2.0";
    "Interdata" -> "7th Edition";
    "7th Edition" -> "8th Edition";
    "7th Edition" -> "32V";
    "7th Edition" -> "V7M";
    "V7M" -> "Ultrix-11";
    "8th Edition" -> "9th Edition";
    [...]
}

thanks, this is exactly what i need. But Unfortunately, it's not working for me. This is what i get after the instalation(i am using linux):Warning: Could not load "/usr/lib/graphviz/libgvplugin_neato_layout.so.6" - file not found Warning: Could not load "/usr/lib/graphviz/libgvplugin_xlib.so.6" - file not found /tmp/alpm_ygcg87/.INSTALL: line 1: 16840 Segmentation fault usr/bin/dot -c error: command failed to execute correctly — maroxe, Mar 04 '12 at 17:46
@maroxe: this looks like a distribution update problem; definitely not OCaml-related, and probably even not graphviz-related (probably a `libc` version problem or what the hell). On this specific issue, you should try your local archlinux help forum. — gasche, Mar 04 '12 at 19:50

Fabrice Le Fessant · Answer 2 · 2012-03-04T20:20:54.330

10

It is usually very easy and funny to use the Graphics library to draw your tree, if it is simple and not too deep.

If you want a textual representation:

type tree = Node of tree * int * tree | Child of int;;
let draw tree =
  let rec print indent tree =
    match tree with
       Child n -> 
        Printf.printf "%s%d\n" indent n
     | Node (left, n, right) ->
        Printf.printf "%s----\n" indent;
        print (indent ^ "| ") left;
        Printf.printf "%s%d\n" indent n;
        print (indent ^ "| ") right;
        Printf.printf "%s----\n" indent
  in
  print "" tree

edited Mar 04 '12 at 20:20

answered Mar 04 '12 at 16:26

Fabrice Le Fessant

4,222
23
36

i am looking for a tool that draws(no matter how, ascii representation is enough) autonatically the tree based on a textual description that can be easily generated. – maroxe Mar 04 '12 at 17:59
1

Very easy? Drawing binary trees looks quite messy to me. Rather than `Graphics`, I would try to use [mlpost](http://forge.ocamlcore.org/projects/mlpost/), an OCaml interface to `metapost` that provide a higher level of abstraction; or maybe at least a `cairo` binding. – gasche Mar 04 '12 at 19:53
2

@gashe: Drawing binary trees is actually very simple. You start from the upper-left corner `(x,y)`, and draw the "right" child on the right of the current position `(x+w,y)`, remember the height `h` of that box, and draw the "left" child below at `(x,y+h)` – Fabrice Le Fessant Mar 05 '12 at 13:39

OCaml: draw binary trees

2 Answers2