নেটওয়ার্ক ফ্লো৭ মিনিট পড়া

এডমন্ডস-কার্প (Edmonds-Karp)

BFS সহকারে ফোর্ড-ফুলকারসন (Ford-Fulkerson) — গ্যারান্টিযুক্ত পলিনোমিয়াল টাইম বা বহুপদী সময় (polynomial time), যেখানে কোনো অসীম চক্র বা ইনফিনিট লুপ (infinite loops) থাকে না
total:\(O(VE^2)\)augmentations:সর্বাধিক (At most) \(O(VE)\)per BFS:\(O(E)\)

ফোর্ড-ফুলকারসন (Ford-Fulkerson) মূলত কোনো অ্যালগরিদম নয়, বরং এটি হলো একটি মেথড (method) বা পদ্ধতি — যা আসলে ঠিক কীভাবে অগমেন্টিং পাথগুলো বা বৃদ্ধি পাওয়ার পথগুলো (augmenting paths) খুঁজে বের করতে হয় তা উল্লেখ না করেই শুধু বলে দেয় যে "যতক্ষণ পর্যন্ত বিদ্যমান থাকে ততক্ষণ অগমেন্টিং পাথগুলো বা বৃদ্ধি পাওয়ার পথগুলো খুঁজে বের করুন (find augmenting paths until none exist)"। এটি DFS-এর মাধ্যমে ব্যবহার করা হলে কোনো ক্ষেত্রে আপনার কপাল খুব ভালোও হতে পারে, বা আবার আপনি কোনো একটি খুব খারাপ পাথ বা পথে (bad paths) ঘুরতে ঘুরতে নিজের অসীম (forever) পরিমাণ সময়ও নষ্ট করে ফেলতে পারেন।

এডমন্ডস-কার্প (Edmonds-Karp) মূলত এই মেথডটিতে খুব সহজ একটি কিন্তু পাওয়ারফুল বা শক্তিশালী পরিবর্তন নিয়ে আসে আর তা হলো: সর্বদা সবচেয়ে ছোট অগমেন্টিং পাথ (shortest augmenting path) (অর্থাৎ যেটিতে এজের সংখ্যা সবচেয়ে কম থাকে) খুঁজতে গিয়ে BFS-কে ব্যবহার করুন। ব্যস, এইটুকুই। শুধুমাত্র একটি লাইনে আনা এই ছোট্ট পার্থক্যটি এটির সক্ষমতাগুলো (capacities) যেমনই হোক না কেন, আপনাকে একটি গ্যারান্টিযুক্ত পলিনোমিয়াল ওয়ার্স্ট-কেসের বা সবচেয়ে খারাপ অবস্থার গ্যারান্টি (polynomial worst-case guarantee) প্রদান করে।

DFS ব্যবহার করাটা কেন ভয়ানক বা বেশ খারাপ একটি বিকল্প হতে পারে (Why DFS Can Be Terrible)

কখনো s থেকে t পর্যন্ত যাওয়া দুটি ভিন্ন পাথের বা পথের কথা কল্পনা করুন: যার মধ্যে একটি যায় 1 ক্ষমতা বা ক্যাপাসিটির (capacity) একটি খুব সরু ব্রিজের (bridge) বা সেতুর মধ্য দিয়ে, এবং অপরটি যায় তার চারপাশ দিয়ে যার ক্ষমতা বা ক্যাপাসিটি থাকে 1,000,000। আপনি যদি DFS ব্যবহার করে এদের মধ্যে বারবার যাতায়াত করতে থাকেন, তবে প্রতিবারই আপনি সেখানে মাত্র 1 ইউনিট করে জিনিস পাঠাতে পারবেন। এবং এর প্রায় 2,000,000 ইটারেশন (iterations) বা বার পুনরাবৃত্তির পরেই মূলত আপনি এমন একটি ফলাফল পাবেন যা BFS-এর সাহায্যে আপনি হয়তো মাত্র দুটি ধাপেই বা স্টেপেই (steps) সম্পন্ন করতে পারতেন।

এর এই ক্ষমতা বা ক্যাপাসিটিগুলো মূলত অযৌক্তিক বা মূলদ (irrational capacities) হওয়ার কারণে, DFS-ভিত্তিক ফোর্ড-ফুলকারসন শেষপর্যন্ত গিয়ে টার্মিনেট (terminate) করতে বা সম্পূর্ণ হতেও ব্যর্থ হতে পারে — যা সঠিক উত্তরের কাছাকাছি পৌঁছানোর আগেই এমন দোলনাময় বা অসিল্যাটিং (oscillating) আচরণ করতে থাকে।

BFS-এর দিন বাঁচানোর উপায়: মনোটোনিসিটি বা অপরিবর্তনীয় আর্গুমেন্ট (The Monotonicity Argument)

আপনি যখন সবসময় এর সবচেয়ে ছোট পাথ বা শর্টেস্ট পাথটি (shortest path) (এজের সংখ্যা বা edge count দ্বারা) ব্যবহার করে বারবার একে বৃদ্ধি বা অগমেন্ট (augment) করবেন, তখন এর এই অগমেন্টিং পাথের (augmenting path) দৈর্ঘ্যগুলো হয় আগের মতো একই থাকবে নতুবা সেটা বাড়তে থাকবে — সেগুলো কখনোই কমবে না। এই ধরনের মনোটোনিসিটি বা অপরিবর্তনীয় বৈশিষ্ট্যটিই (monotonicity) হলো এই পলিনোমিয়াল বাউন্ড (polynomial bound) বা পলিনোমিয়াল সীমার পেছনের মূল চাবিকাঠি।

কেন এটি এত গুরুত্বপূর্ণ: একবার যখন আপনি L (L length) দৈর্ঘ্যের একটি পাথ বা পথ বারবার ব্যবহার করা শুরু করবেন, তখন স্বভাবতই এক পর্যায়ে গিয়ে এর বটলনেক এজটি (bottleneck edge) বা সেই সংকীর্ণ অংশটি স্যাচুরেট (saturated) বা ভর্তি হয়ে যাবে এবং পরবর্তীতে সেটিকে রিমুভ (removed) বা সরিয়ে ফেলতে হবে। সেই এজটি (edge) হয়তো পরে কোনো ব্যাকওয়ার্ড এজ (backward edge) বা পেছনের প্রান্ত হয়ে ঠিকই ফিরে আসতে পারে — কিন্তু তখন তা কেবল একটি দীর্ঘতর পাথের বা লম্বা পথের কোনো অংশ হিসেবেই ফেরত আসবে। আর যেহেতু পাথের (path) দৈর্ঘ্যটিকে V-এর পরিমাণ দিয়ে সীমাবদ্ধ করা থাকে, তাই এখানকার সর্বমোট অগমেন্টেশনগুলোর (augmentations) সংখ্যাও সীমিত হয়ে থাকে।

এর \(O(VE^2)\) টাইমের প্রুফ স্কেচ (The \(O(VE^2)\) Proof Sketch)

প্রতিটি এজ বা প্রান্ত (edge) মূলত একটি শর্টেস্ট পাথের দৈর্ঘ্য (shortest path) এর ভেতর দিয়ে পার হয়ে যাওয়ার আগে সর্বাধিক \(O(V)\) সংখ্যক বার বটলনেক (bottleneck) হিসেবে কাজ করতে পারে বা সেটিতে রূপান্তরিত হতে পারে। একটি গ্রাফে (graph) ঠিক E সংখ্যক এজ থাকে। তাহলে: প্রতিটি এজের জন্য \(O(V)\) বটলনেক (bottleneck) ইভেন্ট × E এজ = সর্বমোট \(O(VE)\) অগমেন্টেশন বা বৃদ্ধি। প্রতিটি অগমেন্টেশন (augmentations) একটি BFS কল বা রান (runs) করে যার খরচ বা ব্যয় হয় \(O(E)\)। তাই মিলে সর্বমোট: \(O(VE)\) × \(O(E)\) = \(O(VE^2)\) হয়।

এটি এর ম্যাক্সিমাম ফ্লো ভ্যালু (maximum flow value) বা সর্বোচ্চ প্রবাহ থেকে অনেকটাই স্বাধীন — এটি হলো ফ্লো ম্যাগনিচ্যুড (flow magnitude) বা ফ্লোয়ের মাত্রায় নয়, বরং একটি গ্রাফের সাইজ বা আকারে থাকা একটি সত্যিকার পলিনোমিয়াল বাউন্ড বা সীমা।

উপযোগিতা বা ইমপ্লিমেন্টেশন (Implementation)

আসল ফোর্ড-ফুলকারসনের (Ford-Fulkerson) পদ্ধতিটি থেকে এটি ভিন্ন হওয়ার একমাত্র কারণ হলো অগমেন্টিং পাথগুলো বা বৃদ্ধি পাওয়ার পথগুলো (augmenting paths) খুঁজে বের করার জন্য এখানে স্ট্যাক/রিকার্সন বা stack/recursion (DFS)-এর পরিবর্তে মূলত কিউ বা queue (BFS) ব্যবহার করা হয়। আর অবশিষ্ট রেসিডুয়াল গ্রাফগুলোর (residual graph management) ক্ষেত্রে এই ব্যবস্থাপনাটি থাকে সম্পূর্ণ একই রকমের: প্রতিটি এজের বা প্রান্তের (u→v) জন্য, এর সামনের দিকের ফরোয়ার্ড ক্যাপাসিটি (forward capacity) এবং পেছনের দিকের ব্যাকওয়ার্ড ক্যাপাসিটিকে (backward capacity) একত্রে জোড় মিলিয়ে বা পেয়ার (pair) হিসেবে স্টোর বা সংরক্ষণ করা হয়।

দ্রষ্টব্য: স্ট্যাকের পরিবর্তে কিউ-এর (queue) ব্যবহার — ড্যাটা স্ট্রাকচারে (data structure) আনা এমন একটি সাধারণ পরিবর্তনই একটি সম্ভাব্য টার্মিনেট-না হওয়া বা সমাপ্তিহীন পদ্ধতিকে সহজেই একটি পলিনোমিয়াল অ্যালগরিদমে রূপান্তরিত করে দেয়। আর এটিই জানান দেয় যে, মাঝেমাঝে এ ধরনের একটি সাধারণ পরিবর্তন বা ছোট জিনিসও কোনো কোনো অ্যালগরিদমে কতটা বিশাল পার্থক্য তৈরি করতে পারে।

এডমন্ডস-কার্প (Edmonds-Karp)

from collections import deque


def edmonds_karp(cap, s, t):
    n = len(cap)
    total = 0


    while True:
        # BFS for shortest augmenting path
        parent = [-1] * n
        parent[s] = s
        q = deque([s])
        while q and parent[t] < 0:
            u = q.popleft()
            for v in range(n):
                if parent[v] < 0 and cap[u][v] > 0:
                    parent[v] = u
                    q.append(v)
        if parent[t] < 0:
            break


        # Bottleneck
        path_flow = float('inf')
        v = t
        while v != s:
            u = parent[v]
            path_flow = min(path_flow, cap[u][v])
            v = u


        # Update residual
        v = t
        while v != s:
            u = parent[v]
            cap[u][v] -= path_flow
            cap[v][u] += path_flow
            v = u
        total += path_flow


    return total


# Example network
cap = [
    [0, 10, 10, 0,  0,  0],
    [0,  0,  0, 5,  0,  0],
    [0,  0,  0, 0, 10,  0],
    [0,  0,  0, 0,  5, 10],
    [0,  0,  0, 0,  0, 10],
    [0,  0,  0, 0,  0,  0],
]
print(edmonds_karp(cap, 0, 5))  # 15
Output
15

Complexity

⏱️ মোট সময় (Total time)
\(O(VE)\) সংখ্যক অগমেন্টেশন (augmentations) × প্রতি BFS-এ \(O(E)\); ফ্লো বা ফ্লোয়ের পরিমাণ যখন অনেক বেশি হয় তখন এটি \(O(E·|f|)\) এর থেকে অনেক ভালো কাজ করে
পলিনোমিয়াল (Polynomial) — ফ্লো-র মাত্রার (flow magnitude) থেকে স্বাধীন \(O(VE^2)\)
🔄 অগমেন্টেশনের বা বৃদ্ধির সংখ্যা (Number of augmentations)
সবচেয়ে ছোট পাথের (shortest path) দৈর্ঘ্য বৃদ্ধি পাওয়ার আগে প্রতিটি এজ বা প্রান্ত সর্বাধিক \(O(V)\) বার একটি বটলনেক-এ (bottleneck) পরিণত হতে পারে
সর্বাধিক V×E সংখ্যক রাউন্ড (At most V×E rounds) \(O(VE)\)
🔍 প্রতি BFS রাউন্ডে (Each BFS)
অটোমেটেড বা স্ট্যান্ডার্ড (Standard) BFS এজ কাউন্ট বা এজের সংখ্যা ব্যবহার করে সবচেয়ে ছোট বা শর্টেস্ট অগমেন্টিং পাথটি (augmenting path) খুঁজে বের করে
এজের (edges) সাপেক্ষে লিনিয়ার (Linear) \(O(E)\)
⚡ বনাম ডিনিকের অ্যালগরিদম (vs Dinic's Algorithm)
ডিনিকের (Dinic's) অ্যালগরিদম প্রতি BFS পর্যায়ে (phase) একটি একটি করার পরিবর্তে একই সাথে সমস্ত ব্লকিং ফ্লো-গুলোকে (blocking flows) — বা অনেকগুলো পাথকে (paths) একসাথে পাঠিয়ে দেয়
বড় বা লার্জ স্পার্স গ্রাফের (large sparse graphs) জন্য এর কাজ বেশ ধীরগতির (Slower) \(O(VE^2)\) বনাম \(O(V^2E)\)

ছোট কুইজ

এডমন্ডস-কার্প (Edmonds-Karp) এবং একটি বেসিক বা সাধারণ ফোর্ড-ফুলকারসনের (Ford-Fulkerson) মধ্যে একমাত্র অ্যালগরিদমিক পার্থক্য কোনটি?

পড়া চালিয়ে যান

ম্যাক্স ফ্লো / মিন কাট (Max Flow / Min Cut)
আপনার পাইপের নেটওয়ার্ক দিয়ে কতটুকু পানি যেতে পারবে? সেটির সিদ্ধান্ত নেবে বটলনেক (bottleneck) বা সরু পথটি
→
ডিনিকের অ্যালগরিদম (Dinic's Algorithm)
এক ধাপে সমস্ত ক্ষুদ্রতম অগমেন্টিং পাথগুলো (augmenting paths) একসাথে বা ব্যাচে (batch) সম্পন্ন করে — যা একটি একটি করে বের করার চেয়ে নাটকীয়ভাবে দ্রুতগতির
→
বিএফএস এবং ডিএফএস পুনর্বিবেচনা (BFS & DFS Revisited)
গ্রাফ অন্বেষণের দুটি উপায় — স্তর অনুযায়ী, অথবা একদম গভীরে গিয়ে
→