Алгоритм толкания

Question

Я сделал MATLAB-версию кода FIFO push-relbel (точно так же, как тот, что в Википедии, и попробовал его. Функция разряда точно так же, как Википедия.

Он отлично работает для небольших графиков (например, количество узлов = 7). Однако, когда я увеличиваю размер своего графа (то есть количество узлов / вершин> 3500 или более), функция "relbel" запускается очень медленно, которая вызывается в функции "разряда". Мои графики огромны (т.е. > 3000 узлов), поэтому мне нужно оптимизировать мой код.

Я попытался оптимизировать код в соответствии с предложениями WIKIPEDIA для глобальной перемаркировки / перемаркировки гэпов: 1) Создайте списки соседей для каждого узла, и пусть индекс видите [u] будет итератором по этому, а не по диапазону. 2) Используйте эвристический пробел.

Я застрял на первом, я не понимаю, что именно я должен делать, так как кажется, что детали не учтены. (Я создал списки соседей так, что для вершины u все связанные узлы v(1..n) с u уже есть в списке соседей, просто не знаю, как выполнить итерацию с видимым индексом [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

И функция разряда использует список структур окрестности 's':

while (extra (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

конец

Может кто-нибудь направить, показать или помочь мне, пожалуйста?