push relabel algorithm

Question

I have done a MATLAB version of the push-relabel FIFO code (exactly like the one on wikipedia and tried it. The discharge function is exactly like wikipedia.

It works perfectly for small graphs (e.g. number of Nodes = 7). However, when I increase my graph size (i.e. number of nodes/vertices > 3500 or more) the "relabel" function runs very slowly, which is called in the "discharge" function. My graphs are huge (i.e. > 3000nodes) so I need to optimize my code.

I tried to optimize the code according to WIKIPEDIA suggestions for global relabeling/gap relabeling: 1) Make neighbour lists for each node, and let the index seen[u] be an iterator over this, instead of the range . 2) Use a gap heuristic.

I'm stuck at the first one , I don't understand what exactly I have to do since it seems there's details left out. (I made neighbor lists such that for vertex u, any connected nodes v(1..n) to u is in the neighbor list already, just not sure how to iterate with the seen[u] index).

[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 the discharge function uses the 's' neighborhood struct list:

while (excess(u) > 0) %test if excess of current node is >0, if so...

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

end

Can someone direct, show or help me please?