🙍🏾 🙄 👨‍👧‍👧 ग्राफ़िक्स पर डीबगिंग एल्गोरिदम

पहले वर्ष में एक विशिष्ट स्थिति की कल्पना करें: आपने डिनिट्स एल्गोरिथ्म के बारे में पढ़ा, इसे लागू किया, लेकिन यह काम नहीं किया, और आप यह नहीं जानते कि क्यों। मानक समाधान कदमों में डिबगिंग शुरू करने के लिए है, हर बार ग्राफ की वर्तमान स्थिति को कागज के एक टुकड़े पर खींचना है, लेकिन यह बहुत असुविधाजनक है। मैंने सॉफ्टवेयर इंजीनियरिंग पर एक सेमेस्टर परियोजना के हिस्से के रूप में स्थिति को ठीक करने की कोशिश की, और एक पोस्ट में मैं आपको बताऊंगा कि मैंने विज़ुअल स्टूडियो के लिए प्लग-इन के साथ कैसे समाप्त किया। आप इसे यहां डाउनलोड कर सकते हैं , स्रोत कोड और प्रलेखन यहां पाया जा सकता है । यहाँ डिनिट्स एल्गोरिथ्म के लिए प्राप्त ग्राफ का एक स्क्रीनशॉट है।

अपने बारे में

मेरा नाम ओल्गा है, मैंने सॉफ्टवेयर इंजीनियरिंग में डिग्री के साथ सेंट पीटर्सबर्ग एचएसई में दिशा "एप्लाइड गणित और कंप्यूटर विज्ञान" के तीसरे वर्ष से स्नातक किया है। विश्वविद्यालय में प्रवेश करने से पहले, मैं प्रोग्रामिंग में शामिल नहीं था।

अनुसंधान: आवश्यकताओं

हमारे संकाय में सेमेस्टर अनुसंधान कार्य का अभ्यास करते हैं। आमतौर पर यह इस तरह होता है: सेमेस्टर की शुरुआत में, शोध कार्यों की एक प्रस्तुति होती है - विभिन्न कंपनियों के प्रतिनिधि विभिन्न परियोजनाओं की पेशकश करते हैं। फिर छात्र अपनी पसंदीदा परियोजनाएं चुनते हैं, पर्यवेक्षक अपने पसंदीदा छात्रों को चुनते हैं, और इसी तरह। अंत में, प्रत्येक छात्र अपने लिए एक प्रोजेक्ट ढूंढता है।

लेकिन एक और तरीका है: आप स्वतंत्र रूप से एक पर्यवेक्षक और एक परियोजना पा सकते हैं, और फिर क्यूरेटर को मना सकते हैं कि यह परियोजना वास्तव में एक पूर्ण आरएंडडी हो सकती है। ऐसा करने के लिए, यह साबित करें:

आप कुछ नया करने जा रहे हैं। बेशक, परियोजना में एनालॉग्स हो सकते हैं, लेकिन आपके विकल्प को उन पर कुछ फायदे होने चाहिए।
कार्य काफी कठिन होना चाहिए, अर्थात्, वहां काम एक सेमेस्टर के लिए होना चाहिए, और एक दिन के लिए नहीं। उसी समय, यह आवश्यक है कि परियोजना वास्तव में एक सेमेस्टर में की गई थी।
आपका प्रोजेक्ट दुनिया के लिए उपयोगी होना चाहिए। यही है, जब पूछा गया कि यह क्यों आवश्यक है, तो आपको जवाब नहीं देना चाहिए: "ठीक है, मुझे किसी तरह का शोध करने की आवश्यकता है।"

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

प्रोजेक्ट कार्य योजना

परियोजना पर मेरे काम में निम्नलिखित चरण शामिल थे:

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

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

विषय अनुसंधान

शुरुआत के लिए, हमारे नेतृत्व को आश्वस्त होना चाहिए था कि यह विषय मेरे शोध कार्य का हकदार है। और पहले बिंदु से शुरू करने के लिए: एनालॉग्स की खोज।

जैसा कि यह निकला, कई एनालॉग हैं। लेकिन उनमें से अधिकांश को स्मृति के दृश्य के लिए डिज़ाइन किया गया था। यही है, उन्होंने कार्टेशियन वृक्ष के दृश्य के साथ बहुत अच्छा काम किया होगा, लेकिन वे यह नहीं समझ सकते कि सरणी पर ढेर को एक सरणी के रूप में नहीं, बल्कि एक पेड़ के रूप में खींचा जाना चाहिए। इनमें gdbgui , डेटा डिस्प्ले डीबगर , ग्रहण jGRASP के लिए प्लग-इन और Visual Studio डेटा स्ट्रक्चर्स विज़ुअलाइज़र के लिए प्लग-इन शामिल थे। बाद को ओलंपियाड प्रोग्रामिंग की समस्याओं के लिए भी बनाया गया था, लेकिन संकेत पर केवल डेटा संरचनाओं की कल्पना करने में सक्षम था।

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

इसलिए, कुछ शोधों के बाद यह पाया गया कि तुला, जो हम चाहते थे, और आधुनिक मशीनों पर एक ही समय में काम करेंगे, वह अभी तक प्रकृति में नहीं है।

कार्यात्मकता परिभाषा

दूसरा कदम यह साबित करना था कि यह कार्य काफी जटिल है, लेकिन उल्लेखनीय है। ऐसा करने के लिए, "मुझे एक सुंदर तस्वीर चाहिए, और यह सब तुरंत से स्पष्ट हो जाता है" की तुलना में कुछ अधिक विशिष्ट प्रस्ताव करना आवश्यक था।

इस परियोजना में, हमने केवल ग्राफ़ की कल्पना करने पर ध्यान केंद्रित करने का निर्णय लिया: ग्राफ़ पर कई एल्गोरिदम हैं जिन्हें अलग-अलग तरीकों से लागू किया जा सकता है, और अगर संकुचित भी हो, तो भी कार्य गैर-तुच्छ बना रहता है।

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

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

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

उपयोगकर्ता इंटरफ़ेस प्रोटोटाइप

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

जैसा कि मैंने डीएफएस के लिए सेटिंग्स की कल्पना की थी। ग्राफ़ को आसन्न सूची के रूप में संग्रहीत किया जाता है, इसलिए कोने i और j के बीच की धार स्थिति g[i].find() != g[i].end() ( g[i].find() != g[i].end() (वास्तव में, किनारों को डुप्लिकेट नहीं करने के लिए निर्धारित की जाती है, हमें यह जांचने की आवश्यकता है कि i <= j )। DFS पथ को अलग से दिखाया गया है: p[j] == i । ये किनारे उन्मुख होंगे।

मैंने माना कि फ्लॉयड के एल्गोरिथ्म के लिए, सरणी c में संग्रहीत वास्तविक किनारों को काले रंग से खींचना आवश्यक होगा, और ग्रे - इस चरण में पाए जाने वाले सबसे छोटे पथ, सरणी d में संग्रहीत। प्रत्येक किनारे और सबसे छोटे रास्ते के लिए, इसका वजन लिखा है।

निर्भरता का चयन

अगले चरण के लिए, यह समझना आवश्यक था कि यह सब कैसे करना है। सबसे पहले, डिबगर के साथ एकीकरण की आवश्यकता थी। पहली बात जो दिमाग में आती है जब "डीबगर" शब्द gdb होता है, लेकिन तब आपको स्क्रैच से पूरे ग्राफिकल इंटरफ़ेस को बनाना होगा, जो एक छात्र के लिए सेमेस्टर में करना बहुत मुश्किल है। दूसरा स्पष्ट विचार कुछ मौजूदा विकास पर्यावरण के लिए एक प्लगइन बनाना है। विकल्पों के रूप में मैंने QTCreator, CLion और Visual Studio पर विचार किया।

CLion विकल्प को लगभग तुरंत ही छोड़ दिया गया था, क्योंकि, सबसे पहले, यह स्रोत कोड बंद कर दिया है, और दूसरी बात, प्रलेखन के साथ सब कुछ बहुत खराब है (और किसी को अतिरिक्त कठिनाइयों की आवश्यकता नहीं है)। QTCreator, Visual Studio के विपरीत, क्रॉस-प्लेटफ़ॉर्म और ओपन सोर्स है, और इसलिए, सबसे पहले हमने इस पर ध्यान केंद्रित करने का निर्णय लिया।

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

और यह सही निर्णय निकला: विजुअल स्टूडियो के पास न केवल एक महान एपीआई है, बल्कि इसके लिए उत्कृष्ट दस्तावेज भी हैं। अभिव्यक्ति का _debugger.GetExpression(...).Value कहकर सरल किया _debugger.GetExpression(...).Value । विज़ुअल स्टूडियो फ़्रेमों पर पुनरावृति करने की क्षमता भी प्रदान करता है, और उनमें से किसी के संदर्भ में अभिव्यक्ति का मूल्यांकन करता है। ऐसा करने के लिए, संपत्ति CurrentStackFrame को आवश्यक एक में बदलें। जब आप छवि को बदलने के लिए डिबगर प्रतियोगिता में अपडेट का ट्रैक रख सकते हैं।

बेशक, यह नहीं माना जाता था कि मैं खरोंच से रेखांकन के दृश्य में लगा रहूंगा - इसके लिए बहुत सारे विशेष पुस्तकालय हैं। उनमें से सबसे प्रसिद्ध ग्रेविज़ है , और हमने इसे पहली बार उपयोग करने की योजना बनाई है। लेकिन विज़ुअल स्टूडियो के लिए प्लग-इन के लिए, C # के लिए लाइब्रेरी का उपयोग करना अधिक तर्कसंगत होगा, क्योंकि मैं इस पर लिखने जा रहा था। मैंने एक छोटा सा googled और MSAGL लाइब्रेरी पाया: इसमें सभी आवश्यक कार्यक्षमता थी और एक सरल और सहज इंटरफ़ेस था।

सबूत अवधारणा-का-

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

इस ग्राफ़ पर, वर्तमान मिलान किनारों को बैंगनी रंग में दिखाया गया है, वर्तमान dfs शीर्ष को लाल रंग में दिखाया गया है, विज़िट किए गए कोने ग्रे हैं, मिलान से नहीं एक वैकल्पिक श्रृंखला के किनारों को लाल रंग में दिखाया गया है।

मैंने एल्गोरिथ्म कोड को थोड़ा सा संशोधित करने की अनुमति दी, ताकि इसे कल्पना करना आसान हो सके। उदाहरण के लिए, कार्टेशियन के पेड़ के मामले में, यह पता चला है कि प्लगइन के अंदर पेड़ को बायपास करने की तुलना में वेक्टर के सभी बनाए गए नोड्स को जोड़ना आसान है।

एक अप्रिय खोज यह थी कि विज़ुअल स्टूडियो में डीबगर एसटीएल से कॉलिंग के तरीकों और कार्यों का समर्थन नहीं करता है। इसका मतलब यह था कि मूल रूप से ग्रहण किए गए std::find का उपयोग करके कंटेनर में एक तत्व की उपस्थिति की जांच करना संभव नहीं था। यह समस्या या तो उपयोगकर्ता द्वारा परिभाषित फ़ंक्शन बनाकर या बूलियन सरणी में "तत्व कंटेनर में निहित है" संपत्ति की नकल करके हल किया जा सकता है।

मेरे परीक्षण प्लगइन्स में, निम्न जैसा कुछ हुआ (यदि ग्राफ को आसन्न सूची के रूप में संग्रहीत किया गया था):

पहले लूप के for 0 से _debugger.GetExpression("n").Value , जिसने ग्राफ़ में सभी कोने जोड़े, प्रत्येक की अपनी संख्या के साथ।
फिर दो _debugger.GetExpression($"g[{i}].size()").Value for नेस्टेड हैं, i लिए पहला - 0 से n , दूसरा j - 0 से _debugger.GetExpression($"g[{i}].size()").Value और किनारे {i, _debugger.GetExpression($"g[{i}][{j}]").Value} ।
यदि आवश्यक हो, तो कोने और किनारों के लेबल में कुछ अतिरिक्त जानकारी जोड़ी गई थी। उदाहरण के लिए, सरणी d का मान, जो चयनित शीर्ष पर दूरी के लिए जिम्मेदार है।
यदि एल्गोरिथ्म dfs पर आधारित था, तो एक लूप सभी फ़्रेमों के माध्यम से चला गया, और स्टैक में सभी कोने ( stackFrame.FunctionName.Equals("dfs") && stackFrame.Arguments.Item(1) == v ) को ग्रे में हाइलाइट किया गया था।
फिर, प्रत्येक के लिए 0 से n , कोने की संख्याओं को दर्शाते हुए, कुछ शर्तों की जाँच की गई, और यदि वे संतुष्ट थे, तो कुछ गुण शीर्ष पर बदल गए, सबसे अधिक बार रंग।

उस समय, मैंने सभी एल्गोरिदम के लिए एक सामान्य योजना के साथ आने की कोशिश किए बिना कोड "आवश्यक" लिखा था, या कोड को कम से कम किसी भी तरह खूबसूरती से लिखा था। प्रत्येक नए प्लगइन का निर्माण पिछले एक की कॉपी-पेस्ट के साथ शुरू हुआ।

ग्राफ विन्यास

शोध के बाद, एक सामान्य योजना तैयार करना आवश्यक था जिसे सभी एल्गोरिदम पर लागू किया जा सकता है। पहली चीज जो पेश की गई थी वह कोने और किनारों के लिए अनुक्रमित थी। प्रत्येक इंडेक्स का एक अनूठा नाम और श्रेणी सिरा है, _debugger.GetExpression गणना _debugger.GetExpression का उपयोग करके की _debugger.GetExpression । सूचकांक के मूल्य तक पहुंचने के लिए, __ (यानी __x__) से घिरे उसके नाम का उपयोग करें। सूचकांक मूल्यों को स्थान देने के साथ-साथ वर्तमान फ़ंक्शन (__CURRENT_FUNCTION__) और इसके तर्कों (__ARG1__, __ARG2__, ...) के मानों को अभिव्यक्त किया जाता है।

इंडेक्स को प्रत्येक शीर्ष या किनारे के लिए प्रतिस्थापित किया जाता है, और उसके बाद डीबगर में इसकी गणना की जाती है। कुछ इंडेक्स वैल्यू को फ़िल्टर करने के लिए टेम्प्लेट्स का उपयोग किया गया था (यदि ग्राफ को आसन्न मैट्रिक्स c रूप में संग्रहीत किया जाता है, तो सूचकांक 0 से n तक बी और बी होगा, और सत्यापन के लिए टेम्पलेट c[__a__][__b__] । इंडेक्स रेंज की सीमाएं भी टेम्प्लेट हैं, क्योंकि उनमें पिछले इंडेक्स हो सकते हैं।

एक ग्राफ में विभिन्न प्रकार के कोने और किनारे हो सकते हैं। उदाहरण के लिए, एक द्विदलीय ग्राफ में अधिकतम मिलान की खोज के मामले में, प्रत्येक अंश को अलग से अनुक्रमित किया जा सकता है। इसलिए, एक परिवार की अवधारणा को कोने और किनारों के लिए पेश किया गया था। प्रत्येक परिवार के लिए, अनुक्रमण और सभी गुण स्वतंत्र रूप से निर्धारित किए जाते हैं। इस मामले में, किनारे विभिन्न परिवारों से कोने जोड़ सकते हैं।

आप एक वर्टेक्स या एज परिवार के लिए विशिष्ट गुण असाइन कर सकते हैं जो परिवार में तत्वों पर चुनिंदा रूप से लागू होंगे। शर्त पूरी होने पर संपत्ति को लागू किया जाता है। शर्त में एक टेम्पलेट शामिल होता है जो true या false और फ़ंक्शन नाम के लिए एक नियमित अभिव्यक्ति का मूल्यांकन करता है। स्थिति की जाँच या तो केवल वर्तमान ग्लास फ़्रेम के लिए की जाती है, या सभी ग्लास फ़्रेमों के लिए (और फिर इसे पूरा माना जाता है यदि यह कम से कम एक के लिए संतुष्ट हो)।

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

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

ग्राफ विन्यास का विस्तृत विवरण यहां पाया जा सकता है ।

उपयोगकर्ता इंटरफ़ेस

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

प्लगइन

ग्राफ को कॉन्फ़िगर करने के लिए, प्लगइन में एक यूजर इंटरफेस है और JSON में कॉन्फिगरेशन को (डी) करने की क्षमता है। सभी घटकों के संपर्क की सामान्य योजना इस प्रकार है:

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

उदाहरण

नतीजतन, मैंने एक उपकरण बनाया जो आपको ग्राफ़ एल्गोरिदम की कल्पना करने की अनुमति देता है और कोड में छोटे बदलाव की आवश्यकता होती है। आठ अलग-अलग कार्यों पर इसका परीक्षण किया गया है। यहाँ कुछ परिणामी तस्वीरें हैं:

Ford-Bellman एल्गोरिथ्म : जिस शीर्ष पर हम सबसे छोटे रास्तों की गणना करते हैं, वह एक घर द्वारा इंगित किया जाता है, कोने के लिए मिली वर्तमान सबसे छोटी दूरी d है, और किनारे जिसके साथ विश्राम मार्ग लाल है।

डीएफएस के साथ एनीमेशन - वर्तमान वर्टेक्स को लाल रंग में दिखाया गया है, स्टैक में कोने ग्रे हैं, और अन्य विज़िट किए गए कोने हरे हैं। रास्पबेरी पसलियां बाईपास की दिशा का संकेत देती हैं।

अधिक नमूना एल्गोरिदम यहां उपलब्ध हैं।

एनआईआर सुरक्षा

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

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

ग्राफ़िक्स पर डीबगिंग एल्गोरिदम - अब चित्रों के साथ