टोपोलॉजिकल सॉर्ट

जब भी आप सॉफ़्टवेयर इंस्टॉल करते हैं, कोई प्रोग्राम बिल्ड करते हैं या कोई प्रोजेक्ट प्लान करते हैं, किसी को तय करना होता है कि पहले क्या हो। अगर काम B को काम A की ज़रूरत है, तो A पहले आना चाहिए। टोपोलॉजिकल सॉर्ट ऐसे नियमों के जाल को एक सीधी रेखा में बदल देता है।

एकतरफ़ा तीरों से जुड़े नोड का ग्राफ़, रखे गए नोड हरे रंग में, और अब तक का क्रम नीचे एक पंक्ति में बना हुआ
एकतरफ़ा तीरों से जुड़े नोड का ग्राफ़, रखे गए नोड हरे रंग में, और अब तक का क्रम नीचे एक पंक्ति में बना हुआ

मूल विचार

हर काम को एक नोड और हर नियम “A, B से पहले” को A से B तक के तीर की तरह बनाएँ। टोपोलॉजिकल क्रम सभी नोड की एक पंक्ति है जिसमें हर तीर दाईं ओर जाता है। इसे सॉर्ट इसलिए कहते हैं क्योंकि यह चीज़ों को क्रम में रखता है, लेकिन संख्याओं को सॉर्ट करने से अलग, इसे सिर्फ़ तीरों का ध्यान रखना होता है: जिन नोड को तीरों की कोई श्रृंखला नहीं जोड़ती, वे किसी भी क्रम में आ सकते हैं।

कब यह असंभव है

अगर तीर साइकिल बनाते हैं, जैसे A, B से पहले, B, C से पहले और C, A से पहले, तो A को खुद से पहले आना होगा। इसलिए टोपोलॉजिकल क्रम ठीक तभी मौजूद होता है जब ग्राफ़ में कोई डायरेक्टेड साइकिल न हो। ऐसे ग्राफ़ को डायरेक्टेड एसाइक्लिक ग्राफ़, या DAG कहते हैं। नीचे के दोनों तरीके साइकिल हो तो उसे ढूँढ लेते हैं, इसलिए ये साइकिल जाँचने के भी काम आते हैं।

एक उदाहरण

तीर A → C, B → C, B → D, C → E और D → E लें। काह्न एल्गोरिदम आने वाले तीर गिनता है: A और B में कोई नहीं, इसलिए पहले A, फिर B। B के तीर हटाने से C और D मुक्त होते हैं, जो इसके बाद आते हैं, और फिर E: क्रम A, B, C, D, E। DFS तरीका A, फिर C, फिर E को विज़िट करता है; E सबसे पहले पूरा होता है, फिर C, फिर A, और हर एक सबसे आगे जाता है। फिर यह B और D को विज़िट करता है, जो पूरे होकर उनके आगे आते हैं: क्रम B, D, A, C, E। दोनों क्रम सही हैं।

काह्न या DFS?

काह्न एल्गोरिदम, जिसे Arthur Kahn ने 1962 में प्रकाशित किया, आगे की ओर काम करता है: इसे हमेशा पता होता है कि कौन-से काम अभी शुरू हो सकते हैं, जो शेड्यूलिंग के लिए अच्छा है, और यह मुक्त कामों में से किसी भी नियम से चुन सकता है, जैसे वर्णमाला क्रम। DFS तरीका, जिसे Robert Tarjan ने 1976 में लोकप्रिय बनाया, अंत से पीछे की ओर काम करता है और इसे बस एक डेप्थ-फ़र्स्ट सर्च चाहिए। दोनों में समय नोड और एज की संख्या के जोड़ के साथ बढ़ता है।

रॉबर्ट टार्जन, जिन्होंने 1972–73 में जॉन हॉपकॉफ़्ट के साथ दिखाया कि गहराई-प्रथम खोज कई ग्राफ़ समस्याओं को रैखिक समय में हल करती है; उन्हें 1986 का ट्यूरिंग पुरस्कार आंशिक रूप से उसी कार्य के लिए मिला।
रॉबर्ट टार्जन, जिन्होंने 1972–73 में जॉन हॉपकॉफ़्ट के साथ दिखाया कि गहराई-प्रथम खोज कई ग्राफ़ समस्याओं को रैखिक समय में हल करती है; उन्हें 1986 का ट्यूरिंग पुरस्कार आंशिक रूप से उसी कार्य के लिए मिला।

उपयोग

make जैसे बिल्ड टूल किसी फ़ाइल को उन फ़ाइलों के बाद कंपाइल करते हैं जिन पर वह निर्भर है। पैकेज मैनेजर लाइब्रेरी को निर्भरता के क्रम में इंस्टॉल करते हैं। स्प्रेडशीट किसी सेल को उन सेल के बाद फिर से गिनती है जिन्हें उसका फ़ॉर्मूला इस्तेमाल करता है। विश्वविद्यालय जाँचते हैं कि कोर्स की पूर्व-आवश्यकताएँ पूरी हो सकती हैं या नहीं, कंपाइलर निर्देशों का क्रम तय करते हैं, और डेटा पाइपलाइन हर चरण को उसके इनपुट तैयार होने के बाद चलाती हैं। Unix कमांड tsort अपने आप में टोपोलॉजिकल सॉर्ट करती है।

खुद आज़माएँ

ऐप खोलें और “आगे” दबाएँ। तीर बताते हैं कि कौन-सा नोड किससे पहले आना चाहिए। काह्न एल्गोरिदम में हर नोड पर लिखी संख्या उसके बचे आने वाले तीर गिनती है, और मुक्त नोड नीले होते हैं। DFS तरीके में नीले नोड विज़िट हो रहे हैं और हरे नोड रखे जा चुके हैं। क्रम ग्राफ़ के नीचे की पंक्ति में बढ़ता है। “साइकिल जोड़ें” पर टिक करें और देखें कि दोनों तरीके कैसे पता लगाते हैं कि कोई क्रम नहीं है।

अक्सर पूछे जाने वाले प्रश्न

यहाँ टोपोलॉजिकल का क्या मतलब है?

यह नाम टोपोलॉजी से आया है, जो इस बात का अध्ययन है कि चीज़ें कैसे जुड़ी हैं, न कि उनका ठीक-ठीक आकार क्या है। क्रम सिर्फ़ इस पर निर्भर करता है कि कौन-से नोड तीरों से जुड़े हैं, इस पर नहीं कि वे कहाँ बने हैं।

जब कोई क्रम न हो, तो साइकिल कैसे ढूँढूँ?

DFS तरीका इसे सीधे दिखाता है: अभी विज़िट हो रहे नोड की ओर जाने वाला एज, विज़िट हो रहे नोड के रास्ते के साथ मिलकर, साइकिल है। काह्न एल्गोरिदम सिर्फ़ बताता है कि कौन-से नोड अटके हैं; उनमें सर्च करने से साइकिल मिल जाती है।

क्या मैं सही क्रमों में से कोई खास क्रम चुन सकता हूँ?

हाँ। काह्न एल्गोरिदम में, जब कई नोड मुक्त हों, तो जो आपको पसंद हो वह चुनें, जैसे सबसे छोटा लेबल या सबसे ज़रूरी काम। प्रायोरिटी क्यू इस्तेमाल करने से वह क्रम मिलता है जो वर्णमाला में सबसे पहले आता है।

टोपोलॉजिकल सॉर्ट का सबसे छोटे रास्तों में कैसे इस्तेमाल होता है?

डायरेक्टेड एसाइक्लिक ग्राफ़ पर, हर नोड के एज को टोपोलॉजिकल क्रम में रिलैक्स करने से एक शुरुआत से सारे सबसे छोटे रास्ते एक ही बार में मिल जाते हैं, नेगेटिव एज होने पर भी, और यह डाइक्स्ट्रा या बेलमैन–फ़ोर्ड से तेज़ है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

टोपोलॉजिकल सॉर्ट आज़माएँ