الگوریتم استور- واگنر

الگوریتم استور-واگنر یک الگوریتم بازگشتی برای حل مسئله برش کمینه در گراف‌های وزن‌دار بدون جهت با وزن‌های نامنفی است. این الگوریتم در سال ۱۹۹۵ توسط مکتیلد استور و فرانک واگنر پیشنهاد داده شد. همبندی گراف یکی از موضوعات کلاسیک در نظریه گراف‌ها می‌باشد و استفاده‌های کاربردی بسیاری مانند طراحی تراشه و مدار، قابل اعتماد بودن شبکات ارتباطی، برنامه‌ریزی حمل و نقل و خوشه بندی دارد. پیدا کردن برش کمینه یک گراف وزن‌دار یه مسئله اساسی الگوریتمی است. به‌طور دقیق این کار شامل پیدا کردن دو بخش مجزا از گراف بطوری که جمع وزن یال‌هایی که این دو بخش را به هم متصل می‌کنند کمینه شود می‌باشد. برش کمینه در یک گراف از موضوعات بسیار مهم در زمینه بهینه‌سازی شبکه است. برش، برداشتن شماری از یال‌های یک گراف همبند است، به گونه‌ای که گراف را به دو بخش ناهمبند تبدیل کند. حال اگر وزن هر یال هزینه برداشتن آن یال در نظر گرفته شود، برش کمینه برشی است که جمع هزینه ایجاد آن کمینه شود.

الگوریتم

فرض کنید $G=(V,E)$ یک گراف ساده وزن‌دار با وزن‌های نامنفی است. یک برش $C$ از گراف $G$ یک زیرمجموعه ناتهی و ناسره از $V$ است. وزن یک برش در واقع جمع وزن یال‌هایی است که از آن برش عبور می‌کنند.

الگوریتم استور-واگنر از تکرار فازهای مشابه تشکیل شده‌است. این الگوریتم در هر فاز ۲ راس از گراف مانند $s$ و $t$ را در نظر می‌گیرد و برش کمینه متناظر با این ۲ راس مانند برش $C$ را بدست می‌آورد. برش کمینه متناظر با ۲ راس، برشی است که حتماً شامل تنها یکی از آن ۲ راس باشد. حال اگر برشی کمینه از $G$ وجود داشته باشد که ۲ رأس $s$ و $t$ را از هم جدا کند آنگاه برش $C$ برش کمینه گراف $G$ است. در غیر این صورت هر برش کمینه از گراف $G$ آن را بطوری تقسیم می‌کند که ۲ رأس $s$ و $t$ در یک بخش می‌افتند. در نتیجه در این حالت اگر ۲ راس $s$ و $t$ را با یکدیگر ادغام کنیم و راسی جدید بجای آن دو بگذاریم گراف حاصل بعد از ادغام این ۲ راس، برشی کمینه مشابه برش کمینه گراف $G$ قبل از ادغام خواهد داشت. پس در هر فاز یک ادغام اتفاق می‌افتد و بعد از $|V|-1$ فاز گراف به یک راس تبدیل می‌شود. کم وزن‌ترین برش کمینه در بین برش‌های کمینه هر فاز برش کمینه گراف $G$ می‌باشد.

هر یک از فازهای الگوریتم استور-واگنر به الگوریتم پریم شباهت زیادی دارد.

• MinimumCutPhase$(G,w,a)$

   $A\gets \left\{a\right\}$
 while $\ A\neq V$
 add to $A$ the most tightly connected vertex
 store the cut-of-the-phase and shrink $G$ by merging the two vertices added last

ابتدا یک زیر مجموعه از راس‌های گراف مانند $A$ را که در ابتدا تنها شامل ۱ راس دلخواه از گراف است را در نظر می‌گیریم. در هر مرحله راسی خارج از $A$ را که مجموعه وزن یال‌هایی که آن‌را به $A$ متصل کرده‌است بیشینه است، به $A$ اضافه می‌کنیم و این کار را تا جایی ادامه می‌دهیم که $|A|=|V|$. در انتهای فاز آخرین ۲ راسی که باقی مانده‌اند را با یکدیگر ادغام می‌کنیم و رأس جدید بجای آن دو می‌گذاریم. هر یالی که از این ۲ راس به راس‌های دیگر متصل است را با یک یال با وزنی معادل مجموع وزن ۲ یال پیشین جایگزین می‌کنیم.

• MinimumCut$(G,w,a)$

 while $|V|>1$
 MinimumCutPhase$(G,w,a)$
 if the cut-of-the-phase is lighter than the current minimum cut
 then store the cut-of-the-phase as the current minimum cut

برشی از $V$ که در انتهای فاز، آخرین رأس باقی‌مانده را از بقیه گراف جدا می‌کند برش کمینه فاز نامیده می‌شود. بعد از اینکه $|V|-1$ بار برش کمینه فاز بدست آمد، کمترین مقدار از این $|V|-1$ مقدار برش کمینه گراف $G$ است.

زمان اجرا

زمان اجرای الگوریتم برش کمینه، در واقع زمان اجرای $|V|-1$ بار MinimumCutPhase است. زمان اجرای MinimumCutPhase حداکثر از $O(|E|+|V|log|V|)$ است. در نتیجه زمان اجرای کل الگوریتم از $O(|E||V|+|V|^{2}log|V|)$ بدست می‌آید.

انتخاب کردن رأس بعدی که باید به مجموعه $A$ اضافه شود می‌تواند در زمان اجرای الگوریتم تأثیر زیادی داشته باشد. برای بهینه کردن الگوریتم و آسان شدن پیدا کردن رأس مورد نظر در هر مرحله، در طول اجرای هر فاز همه راس‌هایی که در مجموعه $A$نیستند، درون یک صف اولویت درج می‌شوند. کلید$v$ هر راس از $V$ مجموع وزن همه یال‌هایی است که آن راس را به مجموعه $A$ متصل می‌کنند. هر بار که یک راس $v$ به $A$ اضافه می‌شود باید صف اولویت به‌روزرسانی شود. در به‌روزرسانی، راس $v$ را از صف حذف می‌کنیم و برای همه راس‌هایی که در $A$ نیستند کلید را به اندازه وزن یال بین آن راس و $v$ در صورت وجود چنین یالی، زیاد می‌کنیم. این عمل هر بار با زمان سرشکن $O(1)$، $|E|$ بار اجرا می‌شود. از طرفی پیدا کردن کلید بیشینه به کمک هیپ فیبوناتچی با زمان سرشکن $O(log|V|)$، $O(V)$ بار تکرار می‌شود. پس زمان اجرای مرحله پیدا کردن رأس مناسب برای اضافه کردن به $A$ حداکثر از $O(|E|+|V|log|V|)$ است.

کد الگوریتم

// Adjacency matrix implementation of Stoer–Wagner min cut algorithm.
//
// Running time:
//     O(|V|^3)
//
// INPUT: 
//     - graph, constructed using AddEdge()
//
// OUTPUT:
//     - (min cut value, nodes in half of min cut)
#include <cmath>
#include <vector>
#include <iostream>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

const int INF = 1000000000;

pair<int, VI> GetMinCut(VVI &weights) 
{
    int N = weights.size();
    VI used(N), cut, best_cut;
    int best_weight = -1;

    for (int phase = N-1; phase>= 0; phase--) 
    {
        VI w = weights[0];
        VI added = used;
        int prev, last = 0;
        for (int i = 0; i <phase; i++) 
        {
            prev = last;
            last = -1;
            for (int j = 1; j <N; j++)
            {
                if (!added[j] && (last == -1 || w[j]> w[last])) last = j;
            }
            if (i == phase-1) 
            {
                for (int j = 0; j <N; j++) weights[prev][j] += weights[last][j];
                for (int j = 0; j <N; j++) weights[j][prev] = weights[prev][j];
                used[last] = true;
                cut.push_back(last);
                if (best_weight == -1 || w[last] <best_weight) 
                {
                    best_cut = cut;
                    best_weight = w[last];
                }
            }
            else 
            {
                for (int j = 0; j <N; j++)
                {
                    w[j] += weights[last][j];
                    added[last] = true;
                }
            }
        }
    }
    return make_pair(best_weight, best_cut);
}

const int maxn = 550;  
const int inf = 1000000000;  
int n, r;  
int edge[maxn][maxn], dist[maxn];  
bool vis[maxn], bin[maxn];  
void init()  
{  
    memset(edge, 0, sizeof(edge));  
    memset(bin, false, sizeof(bin));  
}  
int contract( int &s, int &t )          // Find s,t  
{  
    memset(dist, 0, sizeof(dist));  
    memset(vis, false, sizeof(vis));  
    int i, j, k, mincut, maxc;  
    for(i = 1; i <= n; i++)  
    {  
        k = -1; maxc = -1;  
        for(j = 1; j <= n; j++)if(!bin[j] && !vis[j] && dist[j]> maxc)  
        {  
            k = j;  maxc = dist[j];  
        }  
        if(k == -1)return mincut;  
        s = t;  t = k;  
        mincut = maxc;  
        vis[k] = true;  
        for(j = 1; j <= n; j++)if(!bin[j] && !vis[j])  
            dist[j] += edge[k][j];  
    }  
    return mincut;  
}

int Stoer_Wagner()  
{  
    int mincut, i, j, s, t, ans;  
    for(mincut = inf, i = 1; i <n; i++)  
    {  
        ans = contract( s, t );  
        bin[t] = true;  
        if(mincut> ans)mincut = ans;  
        if(mincut == 0)return 0;  
        for(j = 1; j <= n; j++)if(!bin[j])  
            edge[s][j] = (edge[j][s] += edge[j][t]);  
    }  
    return mincut;  
}