graphviz - Enforcing horizontal node ordering in a .dot tree -

i trying recreate example diagram binary search tree graphviz. how should in end:

this first attempt:

digraph g {     nodesep=0.3;     ranksep=0.2;     margin=0.1;     node [shape=circle];     edge [arrowsize=0.8];     6 -> 4;     6 -> 11;     4 -> 2;     4 -> 5;     2 -> 1;     2 -> 3;     11 -> 8;     11 -> 14;     8 -> 7;     8 -> 10;     10 -> 9;     14 -> 13;     14 -> 16;     13 -> 12;     16 -> 15;     16 -> 17; } 

but unfortunately graphviz doesn't care horizontal positions of tree, get:

how can add constraints horizontal positions of vertices reflects total ordering?

you follow usual approach of adding invisible nodes , invisible edges, , playing edge weight etc. proposed on graphviz faq balanced trees. in simple cases, enough.

but there better solution: graphviz comes tool called gvpr (graph pattern scanning , processing language) allows to

copy input graphs output, possibly transforming structure , attributes, creating new graphs, or printing arbitrary information

and since emden r. gansner did work creating script layout nicely binary trees, heres how to (all credit goes erg):

save following gvpr script file called tree.gv :

begin {   double tw[node_t];    // width of tree rooted @ node   double nw[node_t];    // width of node   double xoff[node_t];  // x offset of root left side of tree   double sp = 36;       // space between left , right subtrees   double wd, w, w1, w2;    double x, y, z;   edge_t e1, e2;   node_t n; } beg_g {   $.bb = "";   $tvtype=tv_postfwd;   // visit root after children visited } n {   sscanf ($.width, "%f", &w);   w *= 72;  // convert inches points   nw[$] = w;   if ($.outdegree == 0) {     tw[$] = w;     xoff[$] = w/2.0;   }   else if ($.outdegree == 1) {     e1 = fstout($);     w1 = tw[e1.head];         tw[$] = w1 + (sp+w)/2.0;     if (e1.side == "left")       xoff[$] = tw[$] - w/2.0;     else       xoff[$] = w/2.0;   }   else {     e1 = fstout($);     w1 = tw[e1.head];         e2 = nxtout(e1);     w2 = tw[e2.head];         wd = w1 + w2 + sp;     if (w > wd)       wd = w;     tw[$] = wd;     xoff[$] = w1 + sp/2.0;   } } beg_g {   $tvtype=tv_fwd;   // visit root first, children } n {   if ($.indegree == 0) {     sscanf ($.pos, "%f,%f", &x, &y);     $.pos = sprintf("0,%f", y);   }   if ($.outdegree == 0) return;   sscanf ($.pos, "%f,%f", &x, &y);   wd = tw[$];   e1 = fstout($);   n = e1.head;   sscanf (n.pos, "%f,%f", &z, &y);   if ($.outdegree == 1) {     if (e1.side == "left")       n.pos = sprintf("%f,%f",  x - tw[n] - sp/2.0 + xoff[n], y);     else       n.pos = sprintf("%f,%f", x + sp/2.0 + xoff[n], y);   }   else {     n.pos = sprintf("%f,%f", x - tw[n] - sp/2.0 + xoff[n], y);     e2 = nxtout(e1);     n = e2.head;     sscanf (n.pos, "%f,%f", &z, &y);     n.pos = sprintf("%f,%f", x + sp/2.0 + xoff[n], y);   } } 

assuming dot file containing graph called binarytree.gv, may execute following line:

dot binarytree.gv | gvpr -c -ftree.gv | neato -n -tpng -o binarytree.png 

the result is:

by switching around line or 2 in script, you'll have single child nodes go left instead of right side.