Generate a Random Flow Network

Question

I am trying to create a flow network for a given graph so that it can be used to test an algorithm. To provide clarity, I want the flow into each vertex to equal the flow out. All flow comes from the source and goes to the sink. Each edge has a maximum capacity and a direction. I would like to generate a flow through this network that equals the maximum flow (found by the min cut) that never exceeds the capacity for each edge.

Below is a graphical example of what I am given and what I am trying to obtain. Of course the "Desired Flow Graph" is not a unique example. I want this generated randomly.

Given Weighted Graph

Desired Flow Graph

I have this graph represented in MatLab with three arrays. The first array s gives the "from" vertex, the second array t gives the "to" vertex, and the third array w1 gives the maximum capacity from s to t. I would like to generate a random array such as w2 that represents the flow. (Note the letters in the pictures are equivalent to their corresponding numbers in the code where "A" = 1.

s =  [1  1  1  2  3  3  4  6  5  6];
t =  [2  3  4  5  5  6  6  5  7  7];
w1 = [10 15 10 8  5  7  6  5  18 15];
w2 = [8  12 6  8  5  7  6  0  13 13];

Any help with some sort of algorithm that can perform this task would be greatly appreciated. I would love a link to an algorithm, pseudocode, direct code, or even just a description of how such an algorithm may be implemented. Thanks in advance for the help.

Josh Meyer Josh Meyer · Accepted Answer · 2017-04-28T20:01:27

Check out the maxflow function in MATLAB: http://www.mathworks.com/help/matlab/ref/graph.maxflow.html

For the graph you posted, you can construct a directed graph with these commands:

s =  [1  1  1  2  3  3  4  6  5  6];
t =  [2  3  4  5  5  6  6  5  7  7];
w1 = [10 15 10 8  5  7  6  5  18 15];
g = digraph(s,t,w1);

Then you can use maxflow to calculate the flow values between node 1 and node 7 and return them in a new directed graph gf:

[mf,gf] = maxflow(g,1,7);

The w2 vector you refer to now just includes the edge weights of the gf graph, so you can extract it like this:

w2 = gf.Edges.Weight

Generate a Random Flow Network

1 Answers