ग्राफ ड्राइंग

This article is about आलेख आरेखण का सामान्य विषय. For वार्षिक अनुसंधान संगोष्ठी, see आलेख आरेखण पर अंतर्राष्ट्रीय संगोष्ठी.

File:WorldWideWebAroundWikipedia.png

हाइपरलिंक प्रदर्शित करते हुए डब्ल्यूडब्ल्यूडब्ल्यू के एक मिनट के अंश का आलेखीय निरूपण।

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

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

आलेखीय परिपाटी

File:4node-digraph-natural.svg

कोरों की दिशाओं को दर्शाने वाले तीर-शीर्षों के साथ निर्देशित आलेख

आलेख को प्रायः नोड-लिंक आरेख के रूप में चित्रित किया जाता है जिसमें शीर्षों को डिस्क, बक्से, या शाब्दिक लेबल के रूप में दर्शाया जाता है और कोरों को यूक्लिडीय तल में रेखा खण्डों, बहुभुजीय श्रृंखलाओं या वक्रों के रूप में दर्शाया जाता है। नोड-लिंक आरेखों को 14वीं-16वीं शताब्दी के स्यूडो-लुल के कार्यों में देखा जा सकता है, जो 13वीं शताब्दी के बहुज्ञ रेमन लुल के नाम से प्रकाशित हुए थे। तात्विक अवधारणाओं के समुच्चयों के बीच सभी युग्मवार संयोजनों का विश्लेषण करने के लिए स्यूडो-लुल ने पूर्ण आलेखों के लिए इस प्रकार के आरेख खींचे।

निर्देशित आलेखों की स्थिति में, तीर के शीर्ष अपनी उन्मुखता को प्रदर्शित के लिए सामान्यतः उपयोग की जाने वाली आलेखीय परिपाटी का निर्माण करते हैं; हालांकि, उपयोगकर्ताओं के अध्ययनों से जानकारी प्राप्त हुई है कि टेपरिंग जैसी अन्य परिपाटियाँ इस जानकारी को अधिक प्रभावी ढंग से प्रदान करती हैं। ऊर्ध्वाधर तलीय आरेखण इस परिपाटी का उपयोग करता है कि प्रत्येक कोर एक निचले शीर्ष से उच्च शीर्ष की ओर उन्मुख होता है, जिससे तीर के शीर्ष अनावश्यक हो जाते हैं।

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

गुणवत्ता मापदण्ड

इनके सौंदर्यशास्त्र और प्रयोज्यता के मूल्यांकन के वस्तुनिष्ठ साधनों को खोजने के प्रयास में, आलेख आरेखणों के लिए कई अलग-अलग गुणवत्ता मापदंडों को परिभाषित किया गया है। एक ही आलेख के लिए अलग-अलग विन्यास विधियों के बीच चयन को निर्देशित करने के अतिरिक्त, कुछ विन्यास विधियाँ इन मापदंडों को सीधे अनुकूलित करने का प्रयास करती हैं।

File:4node-digraph-embed.svg

कोरों को अधिव्यापित किए बिना खींचा गया समतलीय आलेख

• एक आरेख की क्रॉसिंग संख्या, एक दूसरे को पार करने वाले कोरों के युग्मों की संख्या है। यदि आलेख समतलीय है, तो इसे बिना किसी कोर के प्रतिच्छेदों के खींचना प्रायः सुविधाजनक होता है; अर्थात्, इस स्थिति में, आलेख आरेखण एक आलेख अंतःस्थापन को निरूपित करता है। हालांकि, असमतलीय आलेख प्रायः अनुप्रयोगों में उत्पन्न होते हैं, इसलिए आलेख आरेखण एल्गोरिदम को सामान्यतः कोर प्रतिच्छेदन की सुविधा देनी चाहिए।
• एक आरेख का क्षेत्रफल, उसके सबसे छोटे परिबद्ध बॉक्स का आकार है, जो किन्हीं भी दो शीर्षों के बीच की निकटतम दूरी के सापेक्ष है। छोटे क्षेत्रफल वाले आरेख सामान्यतः बड़े क्षेत्रफल वाले आरेखों से बेहतर होते हैं, क्योंकि ये आरेख की विशेषताओं को बड़े आकार में और इस प्रकार अधिक पठनीय रूप से दिखाने की सुविधा प्रदान करते हैं। परिबद्ध बॉक्स का अभिमुखता अनुपात भी महत्वपूर्ण हो सकता है।
• समरूपता प्रदर्शन किसी दिए गए आलेख के भीतर समरूपता समूहों को प्राप्त करने की समस्या है, और एक आरेख की प्राप्ति यथासंभव समरूपता को प्रदर्शित करती है। कुछ विन्यास विधियाँ स्वचालित रूप से सममित आरेखों की ओर प्रेरित करती हैं; वैकल्पिक रूप से, कुछ आरेखण विधियाँ इनपुट आलेख में सममिति को खोजकर और उनका उपयोग करके आरेखण का निर्माण करती हैं।
• यह महत्वपूर्ण है कि कोरों का आकार यथासंभव सरल हो, जिससे आँख के लिए उनका अनुसरण करना आसान हो सके। पॉलीलाइन आरेखण में, कोरों की जटिलता को उसके मोड़ों की संख्या से मापा जा सकता है, और कई विधियों का उद्देश्य केवल कुछ कुल मोड़ों या कुछ मोड़ प्रति कोर के साथ आरेख प्रदान करना है। इसी प्रकार स्प्लाइन वक्रों के लिए एक कोर की जटिलता को कोर पर नियंत्रण बिंदुओं की संख्या से मापा जा सकता है।
• सामान्यतः उपयोग किए जाने वाले कई गुणवत्ता मापदण्ड कोरों की लंबाई से संबंधित हैं: सामान्यतः कोरों की कुल लंबाई के साथ-साथ किसी भी कोर की अधिकतम लंबाई को कम करना वांछनीय होता है। इसके अतिरिक्त, यह बेहतर हो सकता है कि कोरों की लंबाई अत्यधिक विविधता के स्थान पर एक समान हो।
• कोणीय विभेदन, एक आलेख आरेखण में सबसे तीक्ष्ण कोणों का एक मापदण्ड है। यदि किसी आलेख में उच्च कोटि के शीर्ष हैं, तो इसका कोणीय विभेदन आवश्यक रूप से छोटा होगा, लेकिन कोणीय विभेदन को कोटि के फलन द्वारा नीचे परिबद्ध किया जा सकता है।
• एक आलेख की ढाल संख्या, सरल रेखाखंड कोरों (क्रॉसिंग की सुविधा के साथ) के साथ आरेख में आवश्यक विशिष्ट कोर ढालों की न्यूनतम संख्या है। घनाकार आलेख में ढाल संख्या अधिकतम चार होती है, लेकिन कोटि पाँच के आलेख में ढाल संख्या असीमित हो सकती है; यह खुला रहता है यदि कोटि-4 आलेख की ढाल संख्या सीमित होती है।

विन्यास की विधियाँ

Error creating thumbnail:

एक बल-आधारित नेटवर्क दृश्यकरण।

कई विभिन्न आलेख विन्यास रणनीतियाँ निम्न हैं:

• बल-आधारित विन्यास प्रणाली में, आलेख आरेखण सॉफ़्टवेयर स्प्रिंग या आणविक यांत्रिकी की प्रणाली से संबंधित भौतिक रूपकों के आधार पर बलों की एक प्रणाली के अनुसार ऊर्ध्वाधर को लगातार घुमाकर एक प्रारंभिक शीर्ष स्थापन को संशोधित करता है। विशिष्ट रूप से, ये प्रणालियाँ आसन्न शीर्षों के बीच आकर्षक बलों को सभी युग्मों के बीच प्रतिकारक बलों के साथ जोड़ती हैं, जिससे एक ऐसे विन्यास को प्राप्त किया जा सके जिसमें कोर की लंबाई छोटी हो जबकि शीर्ष अच्छी तरह से पृथक हों। ये प्रणालियाँ एक ऊर्जा फलन के क्रमिक अवरोहण के आधार पर न्यूनीकरण कर सकती हैं, या ये गतिमान शीर्षों के लिए सीधे वेग या त्वरण में बलों का रूपान्तरण कर सकती हैं।
• स्पेक्ट्रमी विन्यास विधियों का उपयोग आलेख के आसन्न आव्यूह से प्राप्त लाप्लासियन जैसे एक आव्यूह के अभिलक्षणिक सदिश के निर्देशांकों के रूप में किया जाता है।
• लम्बकोणीय विन्यास विधियाँ, जो आलेख के कोरों को विन्यास के निर्देशांक अक्षों के समानांतर क्षैतिज या लंबवत रूप से चलाने की सुविधा देती हैं। इन विधियों को मूल रूप से वीएलएसआई और मुद्रित परिपथ बोर्ड विन्यास समस्याओं के लिए संरचित किया गया था लेकिन इन्हें आलेख आरेखण के लिए भी अनुकूलित किया गया है। ये सामान्यतः एक बहुचरणीय दृष्टिकोण को सम्मिलित करते हैं जिसमें एक इनपुट आलेख को ऊर्ध्वाधर द्वारा प्रतिच्छेदन बिन्दुओं को बदलकर समतलीकृत किया जाता है, और समतलीकृत आलेख का एक सांस्थितीय अंतःस्थापन प्राप्त होता है, कोर उन्मुखीकरण को मोड़ों को कम करने के लिए चुना जाता है, ऊर्ध्वाधर को इन उन्मुखों के साथ सतत रूप से रखा जाता है, और अंत में एक विन्यास संघनन चरण आरेख के क्षेत्रफल को कम करता है।
• वृक्ष विन्यास एल्गोरिदम, ये वृक्षों के लिए उपयुक्त एक जड़दार पेड़ सदृश संरचना को प्रदर्शित करते हैं। प्रायः, "गुब्बारा विन्यास" नामक तकनीक में, वृक्ष में प्रत्येक नोड के बच्चों को नोड के चारों ओर एक चक्र पर चित्रित किया जाता है, इन वृत्तों की त्रिज्यायें वृक्ष के निचले स्तर पर कम हो जाती है जिससे ये वृत्त अतिव्यापित न हों।
• स्तरीय आलेख आरेखण, (जिसे प्रायः सुगियामा-शैली आरेख कहते हैं) सॉफ़्टवेयर प्रणाली में मॉड्यूल या क्रियाओं के बीच निर्भरता के आलेख जैसे निर्देशित अचक्रीय आलेख या लगभग अचक्रीय आलेखों के लिए सबसे उपयुक्त हैं। इन विधियों में, आलेख के नोड को कॉफ़मैन-ग्राहम एल्गोरिथम जैसी विधियों का उपयोग करके क्षैतिज परतों में इस प्रकार से व्यवस्थित किया जाता है, कि अधिकांश कोर एक परत से दूसरी परत तक नीचे जाते हैं; इस चरण के बाद, क्रॉसिंग को कम करने के लिए प्रत्येक परत के भीतर नोड की व्यवस्था की जाती है।
• चाप आरेख, 1960 के दशक की एक विन्यास शैली, शीर्षों को एक रेखा पर व्यवस्थित करते हैं; कोरों को रेखा के ऊपर या नीचे अर्धवृत्त के रूप में या कई अर्धवृत्तों से परस्पर जुड़े सरल वक्र के रूप में चित्रित किया जा सकता है।

File:Goldner-Harary-linear.svg

चाप आरेख

• वृत्ताकार विन्यास विधियाँ आलेख के शीर्षों को एक वृत्त पर रखती हैं, क्रॉसिंग को कम करने के लिए वृत्त के चारों ओर के शीर्षों के क्रम को सावधानीपूर्वक चुनती हैं और आसन्न शीर्षों को एक दूसरे के समीप रखती हैं। कोरों को या तो वृत्त की जीवा के रूप में या वृत्त के अंदर या बाहर चाप के रूप में खींचा जा सकता है। कुछ स्थितियों में, कई वृत्तों का उपयोग किया जा सकता है।
• डोमिनेंस आरेखण, शीर्षों को इस प्रकार से व्यवस्थित करता है कि एक शीर्ष ऊपर की ओर, दाईं ओर, या दोनों ओर हो, यदि और केवल यदि इस तक दूसरे शीर्ष से पहुँचा जा सकता है। इस प्रकार, विन्यास शैली आलेख के अभिगम्यता संबंध को पारदर्शी रूप से स्पष्ट करती है।

अनुप्रयोग-विशिष्ट आलेख चित्र

अनुप्रयोग के अन्य क्षेत्रों में उत्पन्न होने वाले आलेख और आलेख आरेखणों में सम्मिलित हैं:

• समाज आलेख, एक सामाजिक नेटवर्क के आरेख, जैसा कि प्रायः सामाजिक नेटवर्क विश्लेषण सॉफ़्टवेयर द्वारा प्रस्तुत किया जाता है
• हैस आरेख, एक प्रकार का आलेख चित्र जो आंशिक क्रमों के लिए विशेषीकृत है
• डेसिन डी'एनफैंट्स, बीजगणितीय ज्यामिति में उपयोग किया जाने वाला एक प्रकार का आलेख आरेखण
• स्थिति आरेख, परिमित-अवस्था यंत्रों का चित्रमय निरूपण
• कंप्यूटर नेटवर्क आरेख, कंप्यूटर नेटवर्क में नोड और संयोजनों का चित्रण
• प्रवाह चित्र और ड्रैकन-चार्ट, इसमें नोड एक एल्गोरिदम के चरणों का निरूपण करते हैं और कोर चरणों के बीच नियंत्रण प्रवाह का निरूपण करते हैं।
• डेटा-प्रवाह आरेख, इसमें नोड एक सूचना प्रणाली के घटकों का निरूपण करते हैं और कोर एक घटक से दूसरे घटक में सूचना के संचलन का निरूपण करते हैं।
• जैव-सूचना विज्ञान, जिसमें वंशावली वृक्ष, प्रोटीन-प्रोटीन अंतःक्रिया नेटवर्क और उपापचयी मार्ग सम्मिलित हैं।

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

सॉफ्टवेयर

File:Gephi 0.9.1 Network Analysis and Visualization Software.png

एक आलेख चित्र अंतर्पृष्ठ (गेफी 0.9.1)

आलेख बनाने के लिए सॉफ़्टवेयर, प्रणाली और प्रणाली के प्रदाताओं में सम्मिलित हैं:

• बायोफैब्रिक, क्षैतिज रेखाओं के रूप में नोड को खींचकर बड़े नेटवर्क को दृश्यमान करने के लिए खुला-स्रोत सॉफ्टवेयर।
• साइटोस्केप, आणविक अंतःक्रिया नेटवर्क को दृश्यमान करने के लिए खुला-स्रोत सॉफ्टवेयर
• गेफी, खुला-स्रोत नेटवर्क विश्लेषण और दृश्यकरण सॉफ़्टवेयर
• ग्राफ-टूल, आलेख के विश्लेषण के लिए मुफ़्त पाइथन पुस्तकालय।
• ग्राफ्विज़, एटी एंड टी कॉर्पोरेशन द्वारा एक खुल-स्रोत आलेख आरेखण प्रणाली
• लिंक्यूरियस, एक वाणिज्यिक नेटवर्क विश्लेषण और ग्राफ डेटाबेस के लिए दृश्यकरण सॉफ़्टवेयर
• मैथेमेटिका, एक सामान्य उद्देश्य गणना उपकरण जिसमें 2डी और 3डी आलेख दृश्यकरण और आलेख विश्लेषण उपकरण सम्मिलित हैं।
• माइक्रोसॉफ्ट स्वचालित आलेख विन्यास, आलेख खींचने के लिए खुला-स्रोत डॉटनेट पुस्तकालय (जिसे पहले जीएलईई कहा जाता था)
• नेटवर्कएक्स आलेखों और नेटवर्क का अध्ययन करने के लिए एक पायथन पुस्तकालय है।
• ट्यूलिप, एक खुला स्रोत डेटा दृश्यकरण उपकरण
• वाईईडी (yEd), आलेख विन्यास कार्यक्षमता वाला एक आलेख संपादक
• पीजीएफ़/टिकज़ेड 3.0 के साथ आलेख आरेखण पैकेज (इसमें ल्युआटेक्स (LuaTeX) की आवश्यकता होती है)।
• लानेट-वी (LaNet-vi), एक खुला-स्रोत बड़ा नेटवर्क दृश्यकरण सॉफ़्टवेयर
• एड्रॉ मैक्स 2डी व्यापार तकनीकी आरेखण सॉफ्टवेयर

यह भी देखें

• आलेख आरेखण पर अंतर्राष्ट्रीय संगोष्ठी
• एकीकृत मॉडलिंग भाषा उपकरणों की सूची

संदर्भ

Footnotes

General references

• Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1994), "Algorithms for Drawing Graphs: an Annotated Bibliography", Computational Geometry: Theory and Applications, 4 (5): 235–282, doi:10.1016/0925-7721(94)00014-x.
• Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, ISBN 978-0-13-301615-4.
• Herman, Ivan; Melançon, Guy; Marshall, M. Scott (2000), "Graph Visualization and Navigation in Information Visualization: A Survey", IEEE Transactions on Visualization and Computer Graphics, 6 (1): 24–43, doi:10.1109/2945.841119.
• Jünger, Michael; Mutzel, Petra (2004), Graph Drawing Software, Springer-Verlag, ISBN 978-3-540-00881-1.
• Kaufmann, Michael; Wagner, Dorothea, eds. (2001), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, doi:10.1007/3-540-44969-8, ISBN 978-3-540-42062-0, S2CID 1808286.
• Tamassia, Roberto, ed. (2014), Handbook of Graph Drawing and Visualization, CRC Press, archived from the original on 2013-08-15, retrieved 2013-08-28.

Specialized subtopics

• Anderson, James Andrew; Head, Thomas J. (2006), Automata Theory with Modern Applications, Cambridge University Press, pp. 38–41, ISBN 978-0-521-84887-9.
• Bachmaier, Christian; Brandes, Ulrik; Schreiber, Falk (2014), "Biological Networks", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 621–651.
• Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, pp. 87–120, doi:10.1007/3-540-44969-8_5, ISBN 978-3-540-42062-0.
• Beckman, Brian (1994), Theory of Spectral Graph Layout, Tech. Report MSR-TR-94-04, Microsoft Research.
• Brandes, Ulrik; Freeman, Linton C.; Wagner, Dorothea (2014), "Social Networks", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 805–839.
• Di Battista, Giuseppe; Rimondini, Massimo (2014), "Computer Networks", in Tamassia, Roberto (ed.), Handbook of Graph Drawing and Visualization, CRC Press, pp. 763–803.
• Doğrusöz, Uğur; Madden, Brendan; Madden, Patrick (1997), "Circular layout in the Graph Layout toolkit", in North, Stephen (ed.), Symposium on Graph Drawing, GD '96 Berkeley, California, USA, September 18–20, 1996, Proceedings, Lecture Notes in Computer Science, vol. 1190, Springer-Verlag, pp. 92–100, doi:10.1007/3-540-62495-3_40, ISBN 978-3-540-62495-0.
• Eiglsperger, Markus; Fekete, Sándor; Klau, Gunnar (2001), "Orthogonal graph drawing", in Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs, Lecture Notes in Computer Science, vol. 2025, Springer Berlin / Heidelberg, pp. 121–171, doi:10.1007/3-540-44969-8_6, ISBN 978-3-540-42062-0.
• Freese, Ralph (2004), "Automated lattice drawing", in Eklund, Peter (ed.), Concept Lattices: Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, February 23-26, 2004, Proceedings (PDF), Lecture Notes in Computer Science, vol. 2961, Springer-Verlag, pp. 589–590, CiteSeerX 10.1.1.69.6245, doi:10.1007/978-3-540-24651-0_12, ISBN 978-3-540-21043-6.
• Garg, Ashim; Tamassia, Roberto (1995), "Upward planarity testing", Order, 12 (2): 109–133,