ম্যাক্সিমাম ফ্লো - পুশ-রিলেবেল অ্যালগরিদম#

পুশ-রিলেবেল অ্যালগরিদম (যা প্রিফ্লো-পুশ অ্যালগরিদম নামেও পরিচিত) হলো একটি ফ্লো নেটওয়ার্কের ম্যাক্সিমাম ফ্লো গণনার একটি অ্যালগরিদম। আমরা যে সমস্যা সমাধান করতে চাই তার সুনির্দিষ্ট সংজ্ঞা ম্যাক্সিমাম ফ্লো - ফোর্ড-ফুলকারসন ও এডমন্ডস-কার্প নিবন্ধে পাওয়া যাবে।

এই নিবন্ধে আমরা নেটওয়ার্কের মধ্য দিয়ে একটি প্রিফ্লো পুশ করে সমস্যা সমাধান করব, যেটি $O(V^4)$, বা আরো সুনির্দিষ্টভাবে $O(V^2 E)$ সময়ে চলবে। অ্যালগরিদমটি ১৯৮৫ সালে অ্যান্ড্রু গোল্ডবার্গ এবং রবার্ট টারজান ডিজাইন করেছিলেন।

সংজ্ঞাসমূহ#

অ্যালগরিদমের সময় আমাদের একটি প্রিফ্লো হ্যান্ডেল করতে হবে - অর্থাৎ একটি ফাংশন $f$ যা ফ্লো ফাংশনের মতো, কিন্তু অগত্যা ফ্লো সংরক্ষণ শর্ত পূরণ করে না। এর জন্য শুধু

এবং

শর্তগুলো পূরণ হতে হবে।

তাই কোনো ভার্টেক্সের পক্ষে যতটুকু ফ্লো বিতরণ করে তার চেয়ে বেশি ফ্লো গ্রহণ করা সম্ভব। আমরা বলি এই ভার্টেক্সে কিছু এক্সেস ফ্লো আছে, এবং এক্সেস ফাংশন $x(u) =\sum_{(v, u) \in E} f((v, u)) - \sum_{(u, v) \in E} f((u, v))$ দিয়ে এর পরিমাণ সংজ্ঞায়িত করি।

ফ্লো ফাংশনের মতোই, আমরা প্রিফ্লো ফাংশন দিয়ে রেসিডুয়াল ক্যাপাসিটি এবং রেসিডুয়াল গ্রাফ সংজ্ঞায়িত করতে পারি।

অ্যালগরিদম একটি প্রাথমিক প্রিফ্লো দিয়ে শুরু হবে (কিছু ভার্টেক্সে এক্সেস থাকবে), এবং এক্সিকিউশনের সময় প্রিফ্লো হ্যান্ডেল ও পরিবর্তন করা হবে। কিছু বিস্তারিত আগে থেকে বলে দিলে, অ্যালগরিদম একটি এক্সেসযুক্ত ভার্টেক্স বেছে নেবে এবং এক্সেসকে প্রতিবেশী ভার্টেক্সে পুশ করবে। সোর্স এবং সিঙ্ক ছাড়া সব ভার্টেক্স এক্সেসমুক্ত না হওয়া পর্যন্ত এটি পুনরাবৃত্তি করবে। সহজেই দেখা যায় যে, এক্সেসবিহীন প্রিফ্লো একটি ভ্যালিড ফ্লো। এটি অ্যালগরিদমকে একটি প্রকৃত ফ্লো দিয়ে শেষ করায়।

এখনো দুটি সমস্যা আছে যেগুলো সামলাতে হবে। প্রথমত, এটি আসলেই শেষ হবে তা আমরা কীভাবে নিশ্চিত করি? এবং দ্বিতীয়ত, এটি আসলেই ম্যাক্সিমাম ফ্লো দেবে, এবং যেকোনো র‍্যান্ডম ফ্লো নয়, তা কীভাবে নিশ্চিত করি?

এই সমস্যাগুলো সমাধানের জন্য আমাদের আরেকটি ফাংশনের সাহায্য দরকার, সেটি হলো লেবেলিং ফাংশন $h$, যাকে প্রায়ই হাইট ফাংশনও বলা হয়, যেটি প্রতিটি ভার্টেক্সে একটি পূর্ণ সংখ্যা অ্যাসাইন করে। আমরা একটি লেবেলিংকে ভ্যালিড বলি, যদি $h(s) = |V|$, $h(t) = 0$, এবং $h(u) \le h(v) + 1$ হয় যদি রেসিডুয়াল গ্রাফে $(u, v)$ এজ থাকে - অর্থাৎ $(u, v)$ এজের রেসিডুয়াল গ্রাফে পজিটিভ ক্যাপাসিটি থাকে। অন্যভাবে বলতে গেলে, যদি $u$ থেকে $v$-তে ফ্লো বাড়ানো সম্ভব হয়, তাহলে $v$-এর উচ্চতা $u$-এর উচ্চতার চেয়ে সর্বোচ্চ এক কম হতে পারে, কিন্তু সমান বা আরো বেশিও হতে পারে।

একটি গুরুত্বপূর্ণ বিষয় লক্ষ্য করুন, যদি একটি ভ্যালিড লেবেলিং ফাংশন বিদ্যমান থাকে, তাহলে রেসিডুয়াল গ্রাফে $s$ থেকে $t$-তে কোনো অগমেন্টিং পাথ থাকে না। কারণ এরকম একটি পাথের দৈর্ঘ্য সর্বোচ্চ $|V| - 1$ এজ হবে, এবং প্রতিটি এজ উচ্চতা সর্বোচ্চ এক কমাতে পারে, যেটি অসম্ভব যদি প্রথম উচ্চতা $h(s) = |V|$ এবং শেষ উচ্চতা $h(t) = 0$ হয়।

এই লেবেলিং ফাংশন ব্যবহার করে আমরা পুশ-রিলেবেল অ্যালগরিদমের কৌশল বলতে পারি: আমরা একটি ভ্যালিড প্রিফ্লো এবং একটি ভ্যালিড লেবেলিং ফাংশন দিয়ে শুরু করি। প্রতিটি ধাপে আমরা ভার্টেক্সগুলোর মধ্যে কিছু এক্সেস পুশ করি এবং ভার্টেক্সগুলোর লেবেল আপডেট করি। আমাদের নিশ্চিত করতে হবে যে, প্রতিটি ধাপের পর প্রিফ্লো এবং লেবেলিং এখনো ভ্যালিড আছে। তারপর যদি অ্যালগরিদম নির্ধারণ করে, প্রিফ্লোটি একটি ভ্যালিড ফ্লো। এবং যেহেতু আমাদের কাছে একটি ভ্যালিড লেবেলিংও আছে, রেসিডুয়াল গ্রাফে $s$ এবং $t$-এর মধ্যে কোনো পাথ নেই, যার মানে ফ্লোটি আসলেই একটি ম্যাক্সিমাম ফ্লো।

ফোর্ড-ফুলকারসন অ্যালগরিদমের সাথে পুশ-রিলেবেল অ্যালগরিদমের তুলনা করলে মনে হয় অ্যালগরিদমগুলো একে অপরের ডুয়াল। ফোর্ড-ফুলকারসন অ্যালগরিদম সব সময় একটি ভ্যালিড ফ্লো বজায় রাখে এবং অগমেন্টিং পাথ না থাকা পর্যন্ত এটি উন্নত করে, অপরদিকে পুশ-রিলেবেল অ্যালগরিদমে কোনো সময়ই অগমেন্টিং পাথ থাকে না, এবং আমরা প্রিফ্লোকে ভ্যালিড ফ্লো না হওয়া পর্যন্ত উন্নত করি।

অ্যালগরিদম#

প্রথমে আমাদের গ্রাফকে একটি ভ্যালিড প্রিফ্লো এবং লেবেলিং ফাংশন দিয়ে ইনিশিয়ালাইজ করতে হবে।

ফোর্ড-ফুলকারসন অ্যালগরিদমের মতো খালি প্রিফ্লো ব্যবহার করা সম্ভব নয়, কারণ তখন একটি অগমেন্টিং পাথ থাকবে এবং এর মানে কোনো ভ্যালিড লেবেলিং বিদ্যমান নেই। তাই আমরা $s$ থেকে বের হওয়া প্রতিটি এজকে তার সর্বোচ্চ ক্যাপাসিটি দিয়ে ইনিশিয়ালাইজ করব: $f((s, u)) = c((s, u))$। এবং অন্য সব এজ শূন্য দিয়ে। এক্ষেত্রে একটি ভ্যালিড লেবেলিং বিদ্যমান, সেটি হলো সোর্স ভার্টেক্সের জন্য $h(s) = |V|$ এবং অন্য সবার জন্য $h(u) = 0$।

এখন আসুন দুটি অপারেশন আরো বিস্তারিতভাবে বর্ণনা করি।

push অপারেশন দিয়ে আমরা একটি ভার্টেক্স $u$ থেকে প্রতিবেশী ভার্টেক্স $v$-তে যতটা সম্ভব এক্সেস ফ্লো পুশ করার চেষ্টা করি। আমাদের একটি নিয়ম আছে: আমরা $u$ থেকে $v$-তে তখনই ফ্লো পুশ করতে পারি যখন $h(u) = h(v) + 1$। সহজ ভাষায়, এক্সেস ফ্লো নিচে প্রবাহিত হতে হবে, কিন্তু খুব খাড়াভাবে নয়। অবশ্যই আমরা শুধু $\min(x(u), c((u, v)) - f((u, v)))$ পরিমাণ ফ্লো পুশ করতে পারি।

যদি কোনো ভার্টেক্সে এক্সেস থাকে, কিন্তু কোনো সংলগ্ন ভার্টেক্সে এক্সেস পুশ করা সম্ভব না হয়, তাহলে আমাদের এই ভার্টেক্সের উচ্চতা বাড়াতে হবে। আমরা এই অপারেশনকে relabel বলি। লেবেলিং-এর ভ্যালিডিটি বজায় রেখে যতটুকু সম্ভব বাড়াব।

সংক্ষেপে, অ্যালগরিদমটি হলো: আমরা একটি ভ্যালিড প্রিফ্লো এবং একটি ভ্যালিড লেবেলিং ইনিশিয়ালাইজ করি। যতক্ষণ পুশ বা রিলেবেল অপারেশন করা যায়, আমরা সেগুলো করি। এরপর প্রিফ্লো আসলেই একটি ফ্লো হয়ে যায় এবং আমরা এটি রিটার্ন করি।

কমপ্লেক্সিটি#

সহজেই দেখানো যায় যে, একটি ভার্টেক্সের সর্বোচ্চ লেবেল $2|V| - 1$। এই পর্যায়ে সব অবশিষ্ট এক্সেস সোর্সে পুশ ব্যাক করা যায় এবং করা হবে। এতে সর্বোচ্চ $O(V^2)$ রিলেবেল অপারেশন হয়।

এটিও দেখানো যায় যে, সর্বোচ্চ $O(V E)$ স্যাচুরেটিং পুশ (যেখানে এজের সম্পূর্ণ ক্যাপাসিটি ব্যবহৃত হয়) এবং সর্বোচ্চ $O(V^2 E)$ নন-স্যাচুরেটিং পুশ (যেখানে এজের ক্যাপাসিটি পুরোপুরি ব্যবহৃত হয় না) সম্পাদিত হবে। যদি আমরা এমন একটি ডেটা স্ট্রাকচার বেছে নিই যেটি $O(1)$ সময়ে পরবর্তী এক্সেসযুক্ত ভার্টেক্স খুঁজতে পারে, তাহলে অ্যালগরিদমের মোট কমপ্লেক্সিটি $O(V^2 E)$।

ইমপ্লিমেন্টেশন#

const int inf = 1000000000;

int n;
vector<vector<int>> capacity, flow;
vector<int> height, excess, seen;
queue<int> excess_vertices;

void push(int u, int v) {
    int d = min(excess[u], capacity[u][v] - flow[u][v]);
    flow[u][v] += d;
    flow[v][u] -= d;
    excess[u] -= d;
    excess[v] += d;
    if (d && excess[v] == d)
        excess_vertices.push(v);
}

void relabel(int u) {
    int d = inf;
    for (int i = 0; i < n; i++) {
        if (capacity[u][i] - flow[u][i] > 0)
            d = min(d, height[i]);
    }
    if (d < inf)
        height[u] = d + 1;
}

void discharge(int u) {
    while (excess[u] > 0) {
        if (seen[u] < n) {
            int v = seen[u];
            if (capacity[u][v] - flow[u][v] > 0 && height[u] > height[v])
                push(u, v);
            else
                seen[u]++;
        } else {
            relabel(u);
            seen[u] = 0;
        }
    }
}

int max_flow(int s, int t) {
    height.assign(n, 0);
    height[s] = n;
    flow.assign(n, vector<int>(n, 0));
    excess.assign(n, 0);
    excess[s] = inf;
    for (int i = 0; i < n; i++) {
    	if (i != s)
	        push(s, i);
    }
    seen.assign(n, 0);

    while (!excess_vertices.empty()) {
        int u = excess_vertices.front();
        excess_vertices.pop();
        if (u != s && u != t)
            discharge(u);
    }

    int max_flow = 0;
    for (int i = 0; i < n; i++)
        max_flow += flow[i][t];
    return max_flow;
}

এখানে আমরা excess_vertices কিউ ব্যবহার করি বর্তমানে এক্সেসযুক্ত সব ভার্টেক্স সংরক্ষণ করতে। এভাবে আমরা ধ্রুব সময়ে পুশ বা রিলেবেল অপারেশনের জন্য পরবর্তী ভার্টেক্স বেছে নিতে পারি।

এবং আমরা সংলগ্ন ভার্টেক্স খুঁজতে খুব বেশি সময় ব্যয় না করি তা নিশ্চিত করতে, আমরা কারেন্ট-আর্ক নামে একটি ডেটা স্ট্রাকচার ব্যবহার করি। মূলত আমরা এজগুলোতে বৃত্তাকার ক্রমে ইটারেট করব এবং সর্বদা শেষ ব্যবহৃত এজ সংরক্ষণ করব। এভাবে, একটি নির্দিষ্ট লেবেলিং মানের জন্য, আমরা কারেন্ট এজ শুধু $O(n)$ বার পরিবর্তন করব। এবং যেহেতু রিলেবেলিং ইতোমধ্যে $O(n)$ সময় নেয়, আমরা কমপ্লেক্সিটি খারাপ করি না।