Drawing & Rendering Multiway Tree in Python

Question

Does somebody know how do I plot a multiway-tree in a aesthetically plausible way? info:

• more or less 100 items
• each level have approximately the same number of items
• 10 levels
• each node have between 0(leaf) and 6 childs
• each node specify it's own level, no matter his roots.

I'm currently using PIL, dividing each "line" in img.size()[0]/number of nodes, and drawing lines with draw.line to represent edges, but it is completely messed up

I hope you can help me =], any information needed I'll post.

Palacios

Answer 1

So, rendering graphs is the particular genius of graphviz, which also happens to have several libraries that provide python bindings. In my opinion, the best of these bindings libraries is pygraphviz. Graphviz is probably the best solution and also likely the simplest.

The particular layout you describe in your Question, a hierarchical, layered scheme, is performed effortlessly by graphviz' dot layout engine. Dot performs the rendering to ensure that the graph is laid out in a natural tree configuration--i.e., parent nodes are positioned above their children; nodes of equal rank (levels from the root) are equi-positioned w/r/t the y-axis when possible, and natural symmetry is preserved when possible.

(Note: confusingly, dot refers to one of several layout engines that comprise graphviz, but dot is also the name and file extension of the file format for all graphviz documents regardless of how they are rendered).

As you can see in my code that follows, using pygraphviz, it's simple to select dot as layout engine for your graph, though it's not actually the default (neato is).

Here's a quick graph i made and then rendered using dot--created and rendered using graphviz via pygraphviz.

Notice that the graph has perfect layout--nodes of the same degree are on the same level along a vertical axis, children are rendered below parents and natural 'symmetry' is preserved when possible (e.g., a parent node is positioned between and above its two child nodes. And as you can see, none of my code manually controls the layout--graphviz, i.e., dot, handles it automatically.

import pygraphviz as PG

A = PG.AGraph(directed=True, strict=True)

A.add_edge("7th Edition", "32V")
A.add_edge("7th Edition", "Xenix")
# etc., etc.

# save the graph in dot format
A.write('ademo.dot')

# pygraphviz renders graphs in neato by default, 
# so you need to specify dot as the layout engine
A.layout(prog='dot')


# opening the dot file in a text editor shows the graph's syntax:
digraph unix {
  size="7,5";
  node [color=goldenrod2, style=filled];
  "7th Edition" -> "32V";
  "7th Edition" -> "V7M";
  "7th Edition" -> "Xenix";
  "7th Edition" -> "UniPlus+";
  "V7M" -> "Ultrix-11";
  "8th Edition" -> "9th Edition";
  "1 BSD" -> "2 BSD";
  "2 BSD" -> "2.8 BSD";
  "2.8 BSD" -> "Ultrix-11";
  "2.8 BSD" -> "2.9 BSD";
  "32V" -> "3 BSD";
  "3 BSD" -> "4 BSD";
  "4 BSD" -> "4.1 BSD";
  "4.1 BSD" -> "4.2 BSD";
  "4.1 BSD" -> "2.8 BSD";
  "4.1 BSD" -> "8th Edition";
  "4.2 BSD" -> "4.3 BSD";
  "4.2 BSD" -> "Ultrix-32";
}

Memo

just perfect, i just have to optimize layouts, colors, blood of jesus... thanks. =] – Palacios

@doug, would you tell me how do I set the node level(line) with a parameter? just for aesthetics. – Palacios

@BrainStorm: well, dot usually takes care of that without any additional config. To force this node configuration--set an explicit constraint--is not difficult, but requires two steps: (i) define a 'subgraph' (group of nodes in your graph to have equal horizontal position); and (ii) in the subgraph definition, set the 'rank' attribute, like this: rank=same. Insufficient space in comments to further explain subgraph, but this page gives straightforward example: graphviz.org/content/cluster – Memo

There's one place where Dot (Graphviz) falls down here: If you want to have some sort of ordering besides topological you have to really hack it. For example, if you want to draw a binary tree, it matters which child node goes left and which goes right. You can make that happen with subgraphs, invisible edges, rank=same constraints, ... but it's not pretty. – Marcelina

pygraphviz is impossible to install on Windows. I ended up using pydot. – Deckhouse