1

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?

Douglas B. Staple
  • 10,510
  • 8
  • 31
  • 58
vpakwong
  • 105
  • 5
  • I don't think people are willing to read such long code. Please paste relevant parts of the code that people can quickly read and reply. – mmtauqir Jan 25 '13 at 21:40
  • I have fixed it now. Can you take a look? I really need to figure out how to do push relabel gap relabeling or global heuristics. – vpakwong Jan 25 '13 at 23:29
  • @user2012431 It is also a good idea to keep the full code somewhere at pastebin so that some users can run the code in matlab and fix the error. – Dilawar Apr 12 '13 at 12:09

0 Answers0