Transitive Closure
সকর্মক আবরণ
`R⁺` — সবচেয়ে ছোট transitive relation যা `R` ধারণ করে। `a R⁺ b` মানে `a` থেকে `b`-তে এক বা একাধিক ধাপে পৌঁছানো যায়।
also: reachability
npm ls আপনাকে R দেখায় (সরাসরি dependency); npm ls --all
কার্যত R⁺ (সব dependency)।
Warshall’s algorithm — O(n³):
for k in range(n):
for i in range(n):
if not M[i][k]: continue
for j in range(n):
if M[k][j]: M[i][j] = Trueকাঠামোটা Floyd–Warshall shortest path-এর মতোই — পার্থক্য শুধু
operator-এ (OR/AND বনাম min/+)। একে বলে semiring
generalisation।
সতর্কতা — আকার বিস্ফোরিত হয়। n-node chain-এ R-এ n−1
edge, কিন্তু R⁺-এ n(n−1)/2। ১০০০ node মানে ৯৯৯ থেকে ৫ লক্ষ।
আর R⁺ তথ্য হারায় — “সরাসরি” আর “পরোক্ষ”-এর পার্থক্য মুছে
যায়। সেটাই supply chain ঝুঁকির মূল: আপনি ৫টা package বিশ্বাস
করেছেন, কিন্তু transitive closure-এ ৩০০ জন অজানা লেখকের কোড
চলছে (left-pad, event-stream)।
উল্টো operation — transitive reduction — সবচেয়ে কম edge রেখে একই reachability। DAG-এ এটা অনন্য, আর Hasse diagram সেটাই।