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

-

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

enter image description here

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:

enter image description here

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:

binary tree nicely layouted graphiv , gvpr script emden r. gansner

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


Comments

Post a Comment

Popular posts from this blog

django - How can I change user group without delete record -

-
on website user have 1 group. , user can change group. it's made user.groups.clear() and user.groups.add(new_group) but it's not efficient, because there 2 sql query: delete, insert. how can change group update query? user , group related each other using manytomanyfield . means intersection table exists relating both entities, , if don't specify model map (using through attribute) django creates 1 you. looking @ sources django.contrib.auth.models see that's case. fortunatly, can access intermediary model using through attribute of manager (in case, user.groups.through ). can use regular model. example: >>> alice = user.objects.create_user('alice', 'alice@example.com', 'alicepw') >>> employee = group.objects.create(name='employee') >>> manager = group.objects.create(name='manager') >>> alice.groups.add(employee) >>> alice.groups.all() [<group: employee...
Read more

java - Need to add SOAP security token -

-
i need set custom soap header attribute on jax-ws generated webservice client. case webservice calls must go through proxy server requiring specific token (recieved web request header) present in soap request header. e.g.: 1 carserviceservice service = null; 2 service = new carserviceservice(new url(url), new qname(qname); 3 carserviceendpoint port = service.getcarserviceport(); it seems in line 3 wsdl retrieved , call fails due missing security token. 1 point direction on how done? a detailed example has been mentioned here: creating , deploying jax-ws web service on tomcat 6 this article shows how create , use security token .
Read more

java - EclipseLink JPA Object is not a known entity type -

-
i have strange problem eclipselink , object want persist. have 1 object (keypointlistimpl) stores object keypointimpl in list. persisting keypointimpl objects works great if try persist keypointlistimpl object java.lang.illegalargumentexception says object keypointimpl isn't known entity type. here keypointimpl code: @entity @table(name="keypoints") public class keypointimpl implements keypoint { @id @generatedvalue(strategy = generationtype.identity) private int id; @enumerated(enumtype.string) private detectortype keypointtype; private float x; private float y; private float size; private float angle; private float response; private int octave; private int classid; ... } here keypointlistimpl code: @entity @table(name="keypointlists") public class keypointlistimpl implements keypointlist { @id @generatedvalue(strategy = generationtype.identity) private int id; @onetoone(cascade={ca...
Read more