ग्राफविज़ डॉट एल्गोरिदम

Question

क्या ग्राफ़विज़ लाइब्रेरी के भीतर डॉट से एल्गोरिदम पर कोई प्रलेखन (पूर्ण छद्म कोड?) है?

मुझे केवल कुछ आंशिक छद्म कोड प्रलेखन मिला।

Answer 1

यहां आपके लिए कुछ संदर्भ दिए गए हैं। सबसे पूर्ण (डॉट स्रोत कोड से कम) शायद # 2 है, पेपर "ड्रॉइंग डायरेक्टेड ग्राफ्स के लिए एक तकनीक" जो कि कई ग्राफिक्स योगदानकर्ताओं द्वारा लिखी गई है।

(1)

Drawing graphs with dot में "डॉट के साथ रेखांकन आकर्षित", डॉट के लेआउट एल्गोरिथ्म इस तरह वर्णित है:

डॉट चार मुख्य चरणों में रेखांकन खींचता है। यह जानने से आपको यह समझने में मदद मिलती है कि किस तरह के लेआउट डॉट बनाता है और आप उन्हें कैसे नियंत्रित कर सकते हैं। डॉट द्वारा उपयोग की जाने वाली लेआउट प्रक्रिया ग्राफ पर विश्वकोश पर निर्भर करती है। इस प्रकार, पहला कदम कुछ चक्रीय किनारों की आंतरिक दिशा को उलट कर इनपुट ग्राफ़ में होने वाले किसी भी चक्र को तोड़ना है। अगला चरण रैंक या स्तर को अलग करने के लिए नोड्स को असाइन करता है। शीर्ष-से-नीचे ड्राइंग में, रैंक वाई निर्देशांक निर्धारित करते हैं। एक से अधिक रैंक तक फैले किनारों को "आभासी" नोड्स और इकाई-लंबाई किनारों की श्रृंखला में विभाजित किया जाता है। तीसरे चरण क्रॉसिंग से बचने के लिए रैंक के भीतर नोड्स ऑर्डर करते हैं। चौथा चरण किनारों को छोटा रखने के लिए नोड्स के एक्स निर्देशांक सेट करता है, और अंतिम चरण मार्ग किनारे splines। वॉरफील्ड [वार 77], कार्पैनो [कार 80] और सुगियामा [एसटीटी 81] के काम के आधार पर यह अधिकांश पदानुक्रमित ग्राफ ड्राइंग प्रोग्राम के समान सामान्य दृष्टिकोण है। हम डॉट के एल्गोरिदम का पूरी तरह से विवरण के लिए [GKNV93] के लिए पाठक उल्लेख

कागजात कि पैरा में उद्धृत ये हैं:

• [Car80] एम Carpano। कम्प्यूटर सहायता प्राप्त निर्णय विश्लेषण के लिए पदानुक्रमित ग्राफ का स्वचालित प्रदर्शन। सॉफ्टवेयर इंजीनियरिंग पर आईईईई लेनदेन, एसई 12 (4): (। जाहिर है खरीद here के लिए उपलब्ध) 538-546 अप्रैल 1980

• [GKNV93] Emden आर Gansner, Eleftherios Koutsofios, स्टीफन सी उत्तर, और केएम-फोंग वीओ। ड्राइंग निर्देशित ग्राफ के लिए एक तकनीक। आईईईई ट्रांस। सोफवेयर इंग्लैंड, 1 9 (3): 214-230, मई 1 99 3। (here ग्राफवीज़.org साइट पर उपलब्ध।)

• [एसटीटी 81] के। सुगियामा, एस टैगवा, और एम। टोडा। पदानुक्रमित प्रणाली संरचनाओं की दृश्य समझ के लिए तरीके। पर सिस्टम, यार, और साइबरनेटिक्स आईईईई लेनदेन, एसएमसी -11 (2): (। खरीद here के लिए जाहिर उपलब्ध है) 109-125, फरवरी 1981

• [War77] जॉन Warfield। क्रॉसिंग थ्योरी और पदानुक्रम मैपिंग। सिस्टम, यार, और साइबरनेटिक्स एसएमसी-7 पर आईईईई लेनदेन (7): (। जाहिर है खरीद here के लिए उपलब्ध) 505-523, जुलाई 1977

(2) "आहरण निर्देशित रेखांकन के लिए एक तकनीक"

डॉट एल्गोरिथ्म कागज "A Technique for Drawing Directed Graphs", (Graphviz.org साइट पर उपलब्ध मुक्त करने के लिए) 1993 में सॉफ्टवेयर इंजीनियरिंग पर पत्रिका आईईईई लेनदेन में प्रकाशित में विस्तार से वर्णित किया गया है। यह उपरोक्त उद्धृत "[GKNV93]" स्रोत है।

हम निर्देशित रेखांकन ड्राइंग के लिए एक चार-पास एल्गोरिथ्म का वर्णन:

सार, क्या यह लायक है के लिए, यह है। पहला पास नेटवर्क सिम्प्लेक्स एल्गोरिदम का उपयोग करके इष्टतम रैंक असाइनमेंट पाता है। दूसरा पास क्रेटिंग को कम करने के लिए एक उपन्यास वजन समारोह और स्थानीय पारदर्शिता को शामिल करने वाले एक पुनरावृत्त ह्युरिस्टिक द्वारा रैंक के भीतर कशेरुक क्रम सेट करता है। तीसरे पास एक सहायक ग्राफ का निर्माण और रैंकिंग करके नोड्स के लिए इष्टतम निर्देशांक पाता है। चौथा पास किनारों को खींचने के लिए splines बनाता है। एल्गोरिदम अच्छा चित्र बनाता है और तेजी से चलता है।

(3)

"Using Graphviz as a Library" "Graphviz एक पुस्तकालय के रूप में उपयोग करना" धारा 3.1 में प्रत्येक लेआउट इंजन के algorithim का एक सारांश प्रदान करता है। डॉट के लिए विवरण का हिस्सा यह है:

डॉट एल्गोरिदम यदि संभव हो तो ग्राफ़ सम्मानित किनारे दिशाओं का एक रैंक लेआउट तैयार करता है। यह पदानुक्रम प्रदर्शित करने या आधिकारिक ग्राफ निर्देशित करने के लिए विशेष रूप से उपयुक्त है। मूल लेआउट योजना को सुगियामा एट अल के लिए जिम्मेदार ठहराया गया है। [एसटीटी 81] डॉट द्वारा उपयोग किए गए विशिष्ट एल्गोरिदम गांसनर एट अल द्वारा वर्णित चरणों का पालन करता है। [जीकेएनवी 9 3]

डॉट लेआउट में चरण हैं: 1) प्रारंभिक 2) रैंक 3) mincross 4) स्थिति 5) समानता 6) splines 7) compoundEdges

प्रारंभ करने के बाद, एल्गोरिदम प्रत्येक नोड को एक अलग रैंक (रैंक) में एक पूर्णांक रैंक (रैंक) में निर्दिष्ट करता है ताकि (असतत) किनारों की लंबाई को कम किया जा सके। अगला चरण (मिनक्रॉस) बढ़त क्रॉसिंग को कम करने के लिए रैंक के भीतर नोड्स को पुनर्व्यवस्थित करता है। इसके बाद ग्राफ को कॉम्पैक्ट करने और किनारों को सीधा करने के लिए एक और पूर्णांक प्रोग्राम का उपयोग करके नोड्स को वास्तविक निर्देशांक की असाइनमेंट (स्थिति) का पालन किया जाता है। इस बिंदु पर, सभी नोड्स में समन्वय विशेषता में एक स्थिति सेट होगी। इसके अलावा, सभी क्लस्टर के बाउंडिंग बॉक्स बीबी विशेषता सेट हैं।

"[जीकेएनवी 9 3]" संदर्भ "उपरोक्त लिंक के रूप में निर्देशित ग्राफ के लिए एक तकनीक" है।

"[STT81]" संदर्भ उपरोक्त उद्धृत के अनुसार "पदानुक्रमित सिस्टम संरचनाओं की दृश्य समझ के लिए तरीके" है।

(4) आप भी रुचि हो सकती है:

• Graphviz's Documentation Index, जो विस्तृत प्रलेखन और अतिरिक्त पृष्ठभूमि सामग्री के लिंक हों।

• Graphviz's "Theory" page जो और भी पृष्ठभूमि सामग्री से जुड़ा हुआ है।

• raw source code for dot, जो कि गिटहब पर उपलब्ध है।

• d3.js Google Group पर कुछ संबंधित चर्चा।