कोई अतिरिक्त संकेत के बिना क्लोजर में चक्रीय (और अपरिवर्तनीय) डेटा संरचना कैसे बना सकता है?

Question

मुझे क्लोजर में निर्देशित ग्राफ का प्रतिनिधित्व करने की आवश्यकता है। मैं ग्राफ में प्रत्येक नोड को ऑब्जेक्ट (शायद एक रिकॉर्ड) के रूप में प्रस्तुत करना चाहता हूं जिसमें :edges नामक फ़ील्ड शामिल है जो नोड्स का संग्रह है जो सीधे वर्तमान नोड से पहुंच योग्य है। उम्मीद है कि यह बिना कहने के चला जाता है, लेकिन मैं इन ग्राफों को अपरिवर्तनीय बनाना चाहता हूं।

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

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

मैंने सुना है कि कुछ लिस्पस में उत्परिवर्तन कार्यों का उपयोग किए बिना चक्रीय सूचियां बनाने का एक तरीका है। क्लोजर में अपरिवर्तनीय चक्रीय डेटा संरचनाओं का निर्माण करने का कोई तरीका है?

Answer 1

आप प्रत्येक नोड को एक स्थिर संभाल देने के लिए एक स्थिर संभाल देने के लिए लपेट सकते हैं (और संदर्भ को संशोधित करने की अनुमति देता है जो शून्य के रूप में शुरू हो सकता है)। इस तरह चक्रीय ग्राफ बनाने के लिए संभव है। इसमें पाठ्यक्रम का "अतिरिक्त" संकेत है।

मुझे नहीं लगता कि यह एक बहुत अच्छा विचार है। आपका दूसरा विचार एक अधिक आम कार्यान्वयन है। हमने आरडीएफ ग्राफ को पकड़ने के लिए ऐसा कुछ बनाया है और बिना किसी प्रयास के इसे शीर्ष डेटा संरचनाओं और परत सूचकांक से इसे बनाना संभव है।

Answer 2

मैं इस चुनौती में पहले भाग गया और निष्कर्ष निकाला कि वर्तमान में क्लोजर में वास्तव में अपरिवर्तनीय डेटा संरचनाओं का उपयोग करना संभव नहीं है।

हालांकि आपके पास एक या स्वीकार्य निम्न विकल्पों में से अधिक जानकारी प्राप्त कर सकते हैं:

साथ

• उपयोग deftype प्रत्येक नोड है कि आप निर्माण के दौरान केवल एक बार बदलने में किनारों क्षेत्र: "अनसिंक्रनाइज़्ड-अस्थायी" एक परिवर्तनशील बनाने के लिए। आप इसे तब से केवल पढ़ने के लिए ही इलाज कर सकते हैं, बिना अतिरिक्त संकेत ओवरहेड। इस दृष्टिकोण में शायद सर्वश्रेष्ठ प्रदर्शन होगा लेकिन एक हैक का थोड़ा सा है।
• लागू करने के लिए परमाणु का उपयोग करें: किनारों। थोड़ा अतिरिक्त संकेत है, लेकिन मैंने व्यक्तिगत रूप से अत्यधिक परमाणु पढ़ने के लिए परमाणुओं को पढ़ा है।

Answer 3

मैं पिछले कुछ दिनों से खेल रहा हूं।

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

फिर मैंने एक और दृष्टिकोण की कोशिश की जो कहीं और संदर्भित मैट्रिक्स का एक भिन्नता है। ग्राफ एक क्लोजर नक्शा है, जहां कुंजी नोड्स (नोड्स से refs नहीं) हैं, और मान एक और नक्शा हैं जिसमें कुंजी पड़ोसी नोड्स हैं और प्रत्येक कुंजी का एकल मान उस नोड के किनारे है, या तो एक संख्यात्मक मूल्य किनारे की ताकत, या किनारे की संरचना को इंगित करता है जिसे मैंने कहीं और परिभाषित किया है।

यह इस तरह दिखता है, एक तरह से, 1->2, 1->3, 2->5, 5->2

(def graph {node-1 {node-2 edge12, node-3 edge13}, 
      node-2 {node-5 edge25}, 
      node-3 nil ;;no edge leaves from node 3 
      node-5 {node-2 edge52}) ;; nodes 2 and 5 have an undirected edge 

नोड -1 के पड़ोसियों तुम जाओ (keys (graph node-1)) पहुंच सकता है या समारोह कहीं परिभाषित (neighbors graph node-1) कॉल करने के लिए, या आप ((graph node-1) node-2) कहना से बढ़त पाने के लिए कर सकते हैं 1->2।

कई फायदे:

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

एकमात्र बड़ा-आश नुकसान मुझे लगता है कि किसी दिए गए ऑपरेशन (जोड़ने, निकालने, किसी भी एल्गोरिदम) के लिए, आप इसे केवल एक प्रारंभिक नोड पास नहीं कर सकते हैं। आपको पूरे ग्राफ मैप और एक शुरुआती नोड को पास करना होगा, जो शायद पूरी चीज की सादगी के लिए भुगतान करने के लिए एक उचित मूल्य है। एक और मामूली नुकसान (या शायद नहीं) यह है कि एक अप्रत्यक्ष किनारे के लिए आपको प्रत्येक दिशा में किनारे को परिभाषित करना होगा। यह वास्तव में ठीक है क्योंकि कभी-कभी किनारे के प्रत्येक दिशा के लिए एक अलग मूल्य होता है और यह योजना आपको ऐसा करने की अनुमति देती है।

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