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