1

我已经做了一个 MATLAB 版本的 push-relabel FIFO 代码（和维基百科上的完全一样并尝试过。放电功能和维基百科完全一样。

它非常适用于小图（例如节点数 = 7）。但是，当我增加图形大小（即节点/顶点数> 3500 或更多）时，“重新标记”函数运行非常缓慢，这在“放电”函数中被调用。我的图表很大（即 > 3000 个节点），所以我需要优化我的代码。

我尝试根据 WIKIPEDIA 关于全局重新标记/间隙重新标记的建议优化代码：1）为每个节点制作邻居列表，并让 index seen[u] 成为迭代器，而不是 range 。2）使用间隙启发式。

我被困在第一个，我不明白我到底要做什么，因为似乎遗漏了细节。（我制作了邻居列表，这样对于顶点 u，到 u 的任何连接节点 v(1..n) 都已经在邻居列表中，只是不确定如何使用 seen[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

结尾

有人可以指导，展示或帮助我吗？

4

0 回答 0