All pair maximum flow in Matlab

Question

Is there a way to find the maximum flow between each pair of vertices in matlab?

c = sparse([1 1 2 2 3 4 4 5 5 6 7 8 9 9],[2 3 3 4 5 6 7 6 7 8 9 10 8 10],[15 10 3 8 9 7 5 6 2 12 10 6 10 8],10,10)

a = [2 3 4 5 6 7 8 9 10]

b = arrayfun(@(x)max_flow(c,1,x),a)

OR

b = arrayfun(@(x)graphmaxflow(c,1,x),a)

b =  
        15 13 8 9 13 7 16 7 13

So, I can take a sparse matrix and get the maximum flow from one vertex to all others. Is there a way to continue this to obtain the max flow for all of the pairs?

I'd eventually like to be able to find the all-pair max flow for a directed, weighted graph. . .

check out that [post](http://stackoverflow.com/questions/13990689/all-pair-maximum-flow?rq=1) — ironzionlion, Jul 16 '14 at 08:51
@RobertP. for example, if you do `graphmaxflow(c,1,2) ans = 15` or `graphmaxflow(c,1,10) ans = 13`. I think the result being identical to sum for the nearer flows is because it's a simple graph. — userABC123, Jul 16 '14 at 09:49

score 0 · Accepted Answer · answered Apr 01 '15 at 20:31

Got it to work:

c = sparse([1 1 2 2 3 4 4 5 5 6 7 8 9 9],[2 3 3 4 5 6 7 6 7 8 9 10 8 10],[15 10 3 8 9 7 5 6 2 12 10 6 10 8],10,10)

for a=1:10
for b=1:10
    if a==b
        continue
    end
    t(b,a)=graphmaxflow(c,a,b);
    p=t(:);
end
end

I couldn't figure out a way to use arrayfun to do this.

Each maximum flow value:

t =

0   0   0   0   0   0   0   0   0   0
15  0   0   0   0   0   0   0   0   0
13  3   0   0   0   0   0   0   0   0
8   8   0   0   0   0   0   0   0   0
9   3   9   0   0   0   0   0   0   0
13  10  6   7   6   0   0   0   0   0
7   7   2   5   2   0   0   0   0   0
16  11  8   12  8   12  10  0   10  0
7   7   2   5   2   0   10  0   0   0
13  11  8   11  8   6   10  6   14  0

p = 
0
15
13
8
9
13
7
...

All pair maximum flow in Matlab

1 Answers1