<< Flows Flows min_lcost_cflow >>

metanet >> metanet > Flows > max_flow

max_flow

maximum flow between two nodes

Calling Sequence

[v,phi,flag] = max_flow(i,j,g)

Parameters

i

integer, number of start node

j

integer, number of end node

g

a graph_data_structure.

v

value of the maximum flow it is exists

phi

row vector of the value of the flow on the arcs

flag

feasible problem flag (0 or 1)

Description

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 g.edges.data.min_cap and g.edges.data.max_cap fields of the graph.

The value of the minimum capacity and of the maximum capacity must be non negative. 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 it is assumed to be equal to 0 on each edge.

If the min_cap or max_cap data fields are not present in the graph structure they can be added and set using the add_edge_data function.

Examples

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);

See Also


Report an issue
<< Flows Flows min_lcost_cflow >>