- Donald Knuth ने 2024 के Stanford Christmas lecture में directed graph के strong components और weak components पर चर्चा की, और Tarjan के strong components algorithm को अपना सबसे पसंदीदा algorithm बताया
- Strong component को एक vertex में contract करने पर cycle-रहित DAG बनता है, और algorithm sink strong component को खोजकर हटाने के flow में काम करता है
- यहां weak component का मतलब directions को ignore करके बने connected component से नहीं है; यह strong components को फिर से group करके linear order बनाने वाला अधिक सामान्य partition है
- Tarjan algorithm DFS के दौरान tree arc, back arc, loop, forward arc, cross arc में फर्क करता है, और strong components के साथ उनका topological sorting भी देता है
- Knuth ने जिस आकर्षण पर जोर दिया, वह सिर्फ procedure में नहीं, बल्कि ऐसी गहरी data structure में है जिसमें जरूरी decision information ठीक उसी समय accessible होती है जब उसकी जरूरत होती है
Lecture की शुरुआत और Knuth की नई किताब
- Lecture की शुरुआत में हाल की बातें नई किताब Constraint Satisfaction के इर्द-गिर्द रहीं
- उन्होंने internal manuscript पिछले दिन publisher को भेज दिया था, और pre-order भी उपलब्ध हो गया था
- Christmas से पहले printing मुश्किल हो सकती है, और official publication date 3 फरवरी दिखती है
- किताब के अंदर January printing लिखा है, और यह पिछले 5 वर्षों से Knuth का मुख्य project रहा है
- इस topic Strong Components and Weak Components की अधिक detail pre-fascicle 12A में है
- मौजूदा किताब volume 4 Fascicle 7 है, और इससे पहले के fascicles volume 4A और 4B के रूप में hardcover में प्रकाशित हुए हैं
- यह सामग्री आगे चलकर volume 4C का पहला एक-तिहाई हिस्सा बनेगी
- Lecture का subtitle “Which algorithm do you love the most?” के करीब है
- Knuth आम तौर पर “सबसे पसंदीदा algorithm” चुनने के सवाल को पसंद नहीं करते, लेकिन इस मामले में Tarjan का strong components algorithm साफ जवाब है
- 1973 में इस procedure को सीखते समय उन्होंने पहली बार समझा कि data structure भी theorem या algorithm की तरह “गहरी” हो सकती है
Strong component और weak component का अंतर
- Directed graph vertices और directed arrows से बना होता है
- अगर दो vertices u, v एक-दूसरे तक पहुंच सकते हैं, तो वे उसी strong component में आते हैं
- cycle में मौजूद सभी vertices उसी strong component में शामिल होते हैं
- ऐसा vertex जिसके पास कई जगहों से आने वाले paths हों लेकिन बाहर जाने का रास्ता न हो, अकेले भी एक strong component हो सकता है
- Knuth जिस weak component का इस्तेमाल करते हैं, वह directions ignore करके बनने वाले undirected component से अलग है
- उनका मत है कि directions ignore करके connected बनने वाले component को “undirected component” कहना चाहिए
- weak component वह concept है जिसमें strong components को contract करके बने DAG को फिर से partition किया जाता है, ताकि पूरा structure एक सीधा order बन जाए
- हर strong component को एक “super vertex” में contract करने पर cycle-रहित graph बनता है
- इसे partial order के रूप में देखा जा सकता है
- weak components तक contract करने पर total order या linear order बनता है
- इसका topological sorting से भी सीधा संबंध है
- अगर कोई x हर topological sorting में हमेशा y से पहले आता है, तो दोनों अलग weak components में हैं
- अगर किसी sorting में x, y से पहले आ सकता है और दूसरी sorting में y, x से पहले आ सकता है, तो दोनों एक ही weak component में हैं
- Knuth इसे mutual incomparability से जोड़ते हैं
Concepts और algorithms का इतिहास
- weak component का concept Knuth, Ron Graham, और Mazkin के रूप में लिखे गए एक professor के बीच किसी दूसरे problem पर हुई पत्राचार प्रक्रिया से निकला
- 28 फरवरी 1970 को Mazkin ने Graham को भेजे पत्र में partition के जरिए total order पाने की बात लिखी थी
- दिसंबर 1970 में Knuth ने Graham को लिखा कि तीनों ने अलग-अलग approaches से एक अधिक general result prove किया है
- Knuth ने Mazkin को co-author के रूप में शामिल करने का फैसला किया, लेकिन उसके तुरंत बाद उन्हें खबर मिली कि Mazkin की heart attack से अचानक मौत हो गई
- संबंधित paper 1972 में Discrete Mathematics volume 2 number 1 में प्रकाशित हुआ
- उस समय Discrete Mathematics अभी-अभी शुरू हुआ journal था, और कोई नहीं जानता था कि आगे इसमें कितने शानदार papers छपेंगे
- Tarjan का strong components algorithm 1972 में SIAM Journal on Computing volume 1 number 2 में प्रकाशित हुआ
- Tarjan उस समय graduate student थे, और यह paper उनकी publication list में छठा था
- Knuth ने जनवरी 1973 में यह paper पढ़ा और algorithm को पसंद करने लगे
- Aho, Hopcroft, Ullman की algorithms textbook में भी Tarjan algorithm अच्छी तरह समझाया गया है
- Hopcroft ने Stanford में sabbatical के दौरान Tarjan के साथ office share करते हुए कई algorithms बनाए
- Hopcroft के पास undirected graph के biconnected components algorithm का idea था, और Tarjan ने मिलता-जुलता idea directed graph के strong components पर लागू किया
- Shimon Even की किताब Tarjan algorithm के low point को cover करती है
- Component खोजने के लिए low point चाहिए और low point calculate करने के लिए component जानना पड़ता है — ऐसी circular situation को Tarjan ने हल किया
DFS से strong components खोजने का तरीका
- Knuth graph search की तुलना cave exploration से करते हैं
- हर room एक vertex है, और हर room से जिन दूसरे rooms में जाया जा सकता है उनकी list outgoing arc है
- Computer चित्र नहीं देखता, बल्कि सिर्फ vertex list और arc list देखकर search करता है
- Basic search method depth-first search है
- अभी तक न देखे गए outgoing arc को follow करते हुए गहराई में जाता है
- आगे जाने की जगह न बचे तो पिछली position पर लौटता है
- पहले से visited vertex मिले तो उस arc का type determine करता है
- DFS में arcs पांच तरह के होते हैं
- tree arc: नया vertex पहली बार discover करते हुए बना DFS tree का arc
- back arc: ancestor की ओर वापस जाने वाला arc
- loop: खुद उसी vertex की ओर जाने वाला arc, जिसका strong components पर असर नहीं पड़ता
- forward arc: descendant की ओर जाने वाला arc
- cross arc: ऐसे vertex की ओर जाने वाला arc जो न ancestor है न descendant
- Algorithm हर बार strong component discover करते समय बचे हुए graph का sink component खोजता है
- finite DAG में हमेशा sink होता है
- sink strong component को हटाकर बाकी graph में फिर से खोजने के तरीके से आगे बढ़ता है
- इस process में strong components खोजने के साथ उनका topological sort भी मिल जाता है
- Performance बहुत तेज बताई गई है
- M arcs और N vertices के लिए worst case में memory access लगभग 5M + 17N के स्तर का है
- इसमें arc list का end check करना और pointer update जैसे operations भी शामिल हैं
Weak components, improved versions, implementation
- weak components algorithm भी strong components खोजने की process के साथ चल सकता है
- इसका फायदा उठाया जाता है कि strong components दाईं से बाईं ओर, यानी sink से शुरू होकर discover होते हैं
- जब नया strong component बाईं ओर जुड़ता है, तो यह determine किया जाता है कि वह existing weak components के साथ कैसे merge होगा
- weak component के determination में हर component के अंदर के source और sink महत्वपूर्ण हैं
- किसी weak component के सभी sinks के पास अगले weak component के सभी sources तक arc होना चाहिए
- यह condition weak components होने की necessary और sufficient condition है
- Programming में सिर्फ source track करके भी update किया जा सकता है
- Tarjan ने 1974 में Information Processing Letters volume 3 number 1 में weak components खोजने पर 3-page algorithm paper प्रकाशित किया
- Knuth ने इस सामग्री को अपने pre-fascicle 12A में व्यवस्थित किया
- worst-case linear time guarantee करने के लिए पर्याप्त data structure maintain करना आसान नहीं है
- Dijkstra ने भी strong components problem को cover किया
- Dijkstra की किताब का chapter 25 “Finding the maximal strong components in a directed graph” पर है
- Dijkstra ने sink strong component हटाते जाने वाली structure का इस्तेमाल किया, लेकिन Tarjan के low point simplification तक नहीं पहुंचे
- Dijkstra के solution ने structure tracking के लिए चार नए arrays introduce किए
- Knuth और Tarjan ने हाल में पुराने algorithm को फिर से देखते हुए बेहतर definitions और improved version बनाए
- उन्होंने Kurki-Suonio के 1970s के idea के आधार पर सुधार किया, लेकिन original paper में fallacy थी
- पुराने तरीके में प्रति arc लगभग 7 accesses थे, जिन्हें घटाकर लगभग 5 कर दिया गया
- कुछ fields को merge करके उसे ज्यादा complex लेकिन तेज रूप दिया, और मजाक में इसे “premature optimization” नहीं बल्कि “post-mature optimization” कहा
- Implementation CWEB programs के रूप में उपलब्ध है
- Program names के रूप में Tarjan strong and weak, Tarjan strong का उल्लेख किया गया
- Input Stanford GraphBase format का graph है
- Knuth ने कहा कि वे अपनी website के programs को ज्यादा आसानी से खोजने लायक organize करेंगे, और 2022 के बाद से update न हुई स्थिति को ठीक करेंगे
- Stanford GraphBase में एक directed graph example है, जिसमें Roget के thesaurus categories के करीब 1,000 items को vertices बनाया गया है और synonym या antonym relations को arcs बनाया गया है
1 टिप्पणियां
Hacker News की राय
2022 में San Francisco जाने पर Stanford कैंपस घूमते हुए, शांत और खाली गर्मियों वाली इमारत के कॉरिडोर से बाहर निकलने ही वाला था कि संयोग से Knuth का ऑफिस दिख गया
उनकी प्रसिद्धि के मुकाबले वह हैरान करने वाला छोटा था, इसलिए दोबारा देखा, लेकिन उल्टा लगा कि यह जगह उनके सादे स्वभाव से अच्छी तरह मेल खाती है
https://janvandenberg.blog/wp-content/img_1813-scaled.jpg
मेरे पास इनाम के चेक भी एक नहीं, दो हैं। वे छोटी-छोटी typos के लिए थे, लेकिन ये दो दस्तावेज़ मेरे पास होना वाकई शानदार लगता है
कोई इसका गलत इस्तेमाल तो नहीं करेगा, लेकिन अगर मुझे पता चले कि मेरे ऑफिस की फोटो मेरी जानकारी के बिना ऑनलाइन डाल दी गई है, तो मुझे काफ़ी डरावना लगेगा
खाली समय में मैं TAOCP 4A और 4B पढ़ रहा हूं, और ये सचमुच शानदार हैं—ज़ोरदार सिफारिश
ज़्यादातर programmers के लिए ये practical नहीं हैं, लेकिन Knuth जिस तरह algorithms design और explain करते हैं, वह हैरान करने वाला और बेजोड़ है
खासकर 4B में Dancing Links implementation मशहूर paper के बाद काफी update हुई है, और यह एक नाज़ुक व खूबसूरत data structure होने के साथ-साथ बहुत तेज़ भी है। 80s में भी वे अब भी कमाल हैं
हमारे scale के लिए लागत calculate की तो करोड़ों dollars निकले, लेकिन Route 53 का कुल infrastructure budget सिर्फ़ tens of thousands of dollars के आसपास था। Edge पर हमने उन CloudFront servers को nameserver के रूप में reuse किया जिनकी hard disk fail हो गई थी, API servers भी साधारण थे, और team करीब 6 लोगों की थी। AWS-style “scrappy काम करना” मतलब था लगभग पैसा खर्च किए बिना, downside risk घटाकर, तेजी से काम पूरा करना
इसलिए हम packet scrubbers के लिए करोड़ों dollars नहीं मांग सकते थे; उनके आने में भी बहुत समय लगता और किसी खास vendor पर बहुत ज़्यादा निर्भरता हो सकती थी
शुरुआत में हमने Route 53 nameservers को dedicated IP range में चलाकर कुछ isolation करने का फैसला किया, और dedicated network links से Amazon के बाकी infrastructure को प्रभावित होने से बचा सकते थे। लेकिन इससे Route 53 customers के बीच fate sharing की समस्या हल नहीं हुई, और असल plan बस इतना था कि “अगर समस्या आए तो मौजूदा network और system tools से बहुत अच्छी filtering कर देंगे”
उसी साल गर्मियों की शुरुआत में मैं Knuth की 4A से जुड़ी नई fascicle पढ़ते हुए combinatorial algorithms में डूबा हुआ था, और एक रात अचानक विचार आया कि अगर बहुत सारे virtual nameservers बनाए जाएं, तो हर customer को चार virtual nameservers का एक unique combination assign किया जा सकता है। overlap की मात्रा भी control की जा सकती थी, और मैंने जल्दी से calculate किया कि करीब 2,000 nameservers से यह guarantee दी जा सकती है कि कोई भी दो customers दो से ज़्यादा nameservers share नहीं करेंगे। Experiments में domains तब भी ठीक resolve होते हैं जब दो nameservers unreachable हों, लेकिन उससे ज़्यादा पर समस्या होने लगती है, इसलिए यह संख्या महत्वपूर्ण थी
IP assign करने वाला recursive search algorithm सीधे 4A के algorithms से inspired था, और customer domains को दो और independent isolation dimensions देता था। Customer को चार independent “stripes” से चार nameservers मिलते हैं, जो nameserver names में इस्तेमाल होने वाले अलग-अलग top-level domains (co.uk, com, net, org) से correspond करते हैं। इसलिए उनमें से किसी एक top-level domain में DNSSEC mistake जैसी समस्या हो भी जाए, तो सिर्फ़ एक nameserver प्रभावित होता है
साथ ही उन्हें चार independent “braids” से निकाला गया, जिससे guarantee की जा सकती थी कि कोई भी दो nameservers कोई specific network path या physical hardware share नहीं करेंगे। Statistics और cryptography background की वजह से मुझे combinatorics पता था, फिर भी अगर मैंने 4A नहीं पढ़ी होती तो ऐसा design नहीं कर पाता
मैं किसी solution को लेकर इतना excited कभी नहीं हुआ था। वजह यह थी कि practically extra infrastructure cost के बिना customer domains के बीच provable network IP-level isolation मिलता था। यह maths था। पूरी तरह free नहीं था, क्योंकि 2,000 anycast IP addresses इस्तेमाल करने पड़े, और कई top-level domains जिस तरह nameserver registration और glue records मांगते हैं, उसकी वजह से 512 domains भी register करने पड़े। Registrar के साथ यह process काफी मज़ेदार था, लेकिन आखिरकार हो गया
हमने इस तरीके का नाम Shuffle Sharding रखा, और यह invention से ज़्यादा discovery जैसा था। Random placement इस्तेमाल करने वाले कई multi-tenant systems किसी न किसी तरह का shuffle sharding हासिल कर लेते हैं, और Stochastic Fair Blue जैसी network filtering techniques भी time-based hashing से वैसा ही effect देती हैं। लेकिन उतने control वाला वही तरीका मैंने नहीं देखा था जितना हम apply कर सकते थे, और इसे recursive nested shuffle sharding तक extend किया जा सकता था, जहां सिर्फ़ caller नहीं बल्कि “call on behalf of” patterns में caller के caller तक—और भी कई levels पर—isolation मिलता था
कई साल बाद आभार के तौर पर मैं Knuth की Christmas lecture live देखने गया और front row में बैठा। पता नहीं क्या inspiration दे जाए, इसलिए आज भी Knuth जो भी material निकालते हैं, सब पढ़ता हूं—organ pieces तक
इसलिए मेरी नज़र में Knuth की किताबें programmers के लिए हैरान करने वाली हद तक practical हैं। वे सोच को फैलाती हैं और समझ को गहरा करती हैं; इससे ज़्यादा और क्या चाहिए
original Dancing Links paper मेरे पसंदीदा papers में से एक है। “यह प्रक्रिया global data structure के pointer variables से एक सावधानी से choreographed dance करवाती है” जैसी पंक्तियां Knuth के algorithms के प्रति प्यार को साफ़ दिखाती हैं
मैं इसे crossword generation में इस्तेमाल कर रहा हूं, इस तरह कि horizontal और vertical words grid का exact cover बनाते हैं
जानना चाहूंगा कि updated algorithm कम memory इस्तेमाल करता है या नहीं
इस बड़े problem में लगभग 100 million solutions होने का अनुमान है, और अगर प्रति सेकंड 100 भी मिलें तो खत्म करने में करीब दस दिन लगेंगे
जिस problem पर मैं काम कर रहा हूं वह ‘Fancy Tetris Houten Puzzel’ में उन cases की गिनती करना है जहां एक ही रंग के pieces कम से कम एक edge share करते हुए सभी connected हों
इस exact cover problem को solve करने के लिए memory पर कम sensitive दूसरे algorithms पर भी विचार कर रहा हूं
मैं यह इसलिए पूछ रहा हूं क्योंकि मैंने हाल ही में computer science literature पढ़ना शुरू किया है
कुछ साल पहले जब मैं San Francisco गया, तो यह जानकर हैरान हुआ कि Donald Knuth न सिर्फ़ अभी जीवित हैं, बल्कि Stanford में हर साल lectures देना जारी रखते हैं
Campus में building ढूंढकर जाना, और जिस topic को follow करना लगभग मुश्किल था उस पर उन्हें live बोलते देखना—वह रात लंबे समय तक याद रहेगी। Donald Knuth सचमुच एक legend हैं
मेरी team के एक सदस्य ने पिछले महीने Seminumerical Algorithms में एक error ढूंढा और 1 hexadecimal dollar का reward cheque पाया, जो original email printout पर handwritten comments के साथ आया था
Donald Knuth से मुझे सबसे ज़्यादा inspiration उनकी दशकों तक चली dedication और discipline से मिलती है
मैं projects, languages और distributions लगातार बदलता रहता हूं, इसलिए उनसे सीखने को वाकई बहुत कुछ है
कपड़े बहुत चमकीले और जीवंत हैं, पुराने गांवों में पहने जाने वाले विश्व/लोक परिधानों जैसे लगते हैं, लेकिन यह ईरानी है या Slavic या इनके बीच कहीं, ठीक समझ नहीं आ रहा
क्या कोई बेहतर अंदाज़ा लगा सकता है?
याद थोड़ी धुंधली है और शायद उनकी पत्नी से भी इसका संबंध रहा हो। 2010 के दशक के मध्य के बाद की lectures में वे इसे अक्सर पहनते लगते हैं, और कहीं न कहीं इसका explanation होगा
2012 में Manchester Town Hall के सामने वाले square में Olympic torch को आते देखने के लिए खिड़की की चौखट पर चढ़ने की कोशिश कर रहे Knuth के पास मैं खड़ा था। उनसे बात की, और एक पल को लगा कि कहीं वे खिड़की से बाहर न गिर जाएं, इसलिए हाथ बढ़ाया, लेकिन सब ठीक था। मुझे वे बहुत जिज्ञासु लगे, जिनके सवाल और बुद्धि चमकते हैं, और जो अपनी उम्र से जवान दिखते हैं
हम दोनों Alan Turing की जन्म-शताब्दी के आयोजन में शामिल थे, और उसी room में Knuth, Gary Kasparov, Fred Brooks, Vint Cerf जैसे computer science के दिग्गजों का होना अद्भुत था। lunch break में बाहर square में Olympic torch आई, और वे खुद को रोक नहीं पाए और देखने चले गए। ऐसा लग रहा था कि उसे लेकर उत्साहित बस वही थे
उस शाम dinner में उन्होंने lecture दिया, और बाद में जब 4B अभी-अभी प्रकाशित हुई थी और Manchester में उनसे दोबारा मिला, तो किताब पर signature मांगने पर उन्होंने मुझे पिछले event से धुंधला-सा पहचान लिया
यह कहानी इसलिए बता रहा हूं क्योंकि मुझे लगता है कि उनकी शर्ट कहीं ज़्यादा eclectic और जिज्ञासु मन का संकेत देती है। ऐसी बातों के सबूत मैंने दूसरी जगहों पर भी साफ देखे हैं
इसलिए पारंपरिक Sami पोशाक के प्रति लगाव शायद वहीं से आया हो
[0]: https://youtu.be/jB0aeePskBg
https://www.youtube.com/playlist?list=PLoROMvodv4rOAvKVR_dyC...
जांचा तो वे 87 साल के हैं। Donald Knuth का जन्म 10 जनवरी 1938 को हुआ था
वाह
Knuth अब भी चकित करते हैं
लेकिन Stanford में इस स्तर की सामग्री के लायक audio recording का ठीक से ध्यान किसी ने नहीं रखा, यह बहुत हैरान और निराश करने वाला है। ऐसा लगता है जैसे किसी ने जेब में रखे recorder से record किया हो
मैं Knuth की बुज़ुर्ग आवाज़ की बात नहीं कर रहा, बल्कि जब वे रुकते हैं और audience के सवाल लेते हैं तब sound quality कितनी खराब है, बस वह सुन लीजिए
ऐसे video मुझे याद दिलाते हैं कि शुरुआत में मुझे computers से प्यार क्यों हुआ था
यह काफी आश्चर्यजनक है कि वे अब भी इतने sharp हैं। अफसोस, जब मैं 20 से कुछ साल पहले undergraduate था, तब तक वे अब lecture नहीं देते थे
सवालों को handle करने का उनका तरीका अच्छा है: https://youtu.be/Hi8r_63LGyg?t=827
वे यह समझने में समय लगाते हैं कि पूछा क्या जा रहा है, और बहुत स्पष्ट जवाब देते हैं