max_flow — maximum flow between two nodes
[v,phi,flag] = max_flow(i,j,g)
integer, number of start node
integer, number of end node
value of the maximum flow it is exists
row vector of the value of the flow on the arcs
feasible problem flag (0 or 1)
max_flow returns the value of maximum flow
v from node number i to node number
j if it exists, and the value of the flow on each arc
as a row vector phi. All the computations are made with
integer numbers. The graph must be directed. If the problem is not
feasible, flag is equal to 0, otherwise it is equal to
1.
The bounds of the flow are given by the min_cap
and max_cap fields of the edges_data_structure. The value of
the maximum capacity must be greater than or equal to the value of the
minimum capacity. If the value of min_cap or
max_cap is not given, they are assumed to be equal to 0
on each edge.
ta=[1 1 2 2 3 3 4 4 5 5 5 5 6 6 6 7 7 15 15 15 15 15 15 15 8 9 10 11 12 13 14];
he=[10 13 9 14 8 11 9 11 8 10 12 13 8 9 12 8 11 1 2 3 4 5 6 7 16 16 16 16 16 16 16];
g=make_graph('foo',1,16,ta,he);
g.nodes.graphics.x=[53,430,202,374,116,250,325,176,373,34,330,233,114,429,208,206];
g.nodes.graphics.y=[86,114,115,129,118,122,133,222,222,221,214,219,218,246,40,301];
ma=edge_number(g);
g=add_edge_data(g,'max_cap',[2,4,3,3,3,2,3,3,5,2,3,1,2,1,4,1,2,2,2,2,4,1,5,3,2,1,5,4,3,4,2]);
g=add_edge_data(g,'min_cap',ones(1,ma))
source=15;g.nodes.graphics.type(source)=2; //source node
sink=16;g.nodes.graphics.type(sink)=1; //sink node
show_graph(g);
[v,phi,ierr]=max_flow(source,sink,g);
g.edges.graphics.foreground(phi<>0)=11;
g=add_edge_data(g,'flow',phi)
g.edges.graphics.display='flow';
show_graph(g);