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.

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";
}