एक .dot पेड़

Question

में क्षैतिज नोड ऑर्डरिंग लागू करना मैं ग्राफवीज़ के साथ एक बाइनरी खोज पेड़ के लिए एक उदाहरण आरेख को फिर से बनाने की कोशिश कर रहा हूं। यह अंत में देखना चाहिए कि कैसे:

यह मेरा पहला प्रयास है:

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

लेकिन दुर्भाग्य से Graphviz पेड़ की क्षैतिज स्थिति के बारे में परवाह नहीं करता, तो मैं मिलता है :

मैं कैसे की कमी में जोड़ सकते हैं ताकि कोने की क्षैतिज पदों उनके कुल आदेश को दर्शाता है?

Answer 1

graphviz FAQ about balanced trees पर प्रस्तावित अदृश्य नोड्स और अदृश्य किनारों को जोड़ने और किनारे के वजन के साथ खेलना सामान्य दृष्टिकोण का पालन कर सकते हैं। कुछ simple cases में, यह पर्याप्त है।

लेकिन वहाँ एक बेहतर समाधान है: Graphviz gvpr नामक एक उपकरण के साथ आता है (ग्राफ़ पैटर्न स्कैनिंग और प्रसंस्करण भाषा) जो संभवतः उनकी संरचना बदलने

प्रतिलिपि इनपुट इसके उत्पादन, करने के लिए रेखांकन के लिए अनुमति देता और विशेषताएँ, नई रेखांकन बनाने, या मुद्रण मनमाने ढंग से जानकारी

और Emden R. Gansner did all the work already by creating a script which does layout nicely binary trees के बाद से, यहाँ कैसे है कि करने के लिए करने के लिए (सभी क्रेडिट एर्ग को जाता है):

सहेजें एक फ़ाइल में निम्न gvpr स्क्रिप्ट tree.gv कहा जाता है:

BEGIN { 
    double tw[node_t]; // width of tree rooted at node 
    double nw[node_t]; // width of node 
    double xoff[node_t]; // x offset of root from left side of its tree 
    double sp = 36;  // extra space between left and 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 all children visited 
} 
N { 
    sscanf ($.width, "%f", &w); 
    w *= 72; // convert inches to 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, then 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); 
    } 
} 

मान लिया जाये कि आपके डॉट ग्राफ युक्त फ़ाइल binarytree.gv कहा जाता है, तो आप निम्न पंक्ति पर अमल हो सकता है:

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

परिणाम है :

स्क्रिप्ट में एक या दो पंक्तियों के चारों ओर स्विच करके, आपको दाएं तरफ के बजाय एक भी बच्चा नोड बाईं ओर जाना होगा।