global - プッシュ再ラベルアルゴリズム

Question

push-relabel FIFO コードの MATLAB バージョンを実行しました (wikipedia のものとまったく同じで、試してみました。放電関数は wikipedia とまったく同じです。

これは、小さなグラフ (ノード数 = 7 など) に最適です。ただし、グラフのサイズを大きくすると (つまり、ノード/頂点の数 > 3500 以上)、「ディスチャージ」関数で呼び出される「再ラベル付け」関数の実行が非常に遅くなります。グラフが巨大 (つまり > 3000 ノード) であるため、コードを最適化する必要があります。

グローバルな再ラベル付け/ギャップの再ラベル付けに関する WIKIPEDIA の提案に従って、コードを最適化しようとしました。2) ギャップヒューリスティックを使用します。

私は最初のもので立ち往生しています。詳細が省略されているように見えるので、正確に何をしなければならないのかわかりません。(頂点 u の場合、u に接続されたノード v(1..n) が既に隣接リストにあるように隣接リストを作成しましたが、見た [u] インデックスで反復する方法がわからないだけです)。

[r,c] = find(C);
uc = unique(c);
s = struct;

for i=1:length(uc)
    ind = find(c == uc(i));
    s(uc(i)).n = [r(ind)];
end

AND 放電関数は、「s」近傍構造体リストを使用します。

while (excess(u) > 0) %現在のノードの超過が >0 かどうかをテストし、そうであれば...

if (seen(u) <= length(s(u).n))  %check next neighbor

        v = s(u).n(seen(u));

        resC = C(u,v) - F(u,v);
        if ((resC > 0) && (height(u) == height(v) + 1)) %and if not all neighbours have been tried since last relabel
            [C, F, excess] = push(C, F, excess, u, v); %push into untried neighbour
        else
                seen(u) = seen(u) + 1;
                height = relabel(C, F, height, u, N);

        end

else
    height = relabel(C, F, height, u, N);
    seen(u) = 1; %relabel start of queue

end

終わり

誰かが私を指示したり、見せたり、助けてくれませんか?