Parameters

Description

min_lcost_cflow computes the minimum cost flow in the network g, with the value of the flow from source node i to sink node j constrained to be equal to cv.

min_lcost_cflow returns the total cost of the flows on the arcs c, the row vector of the flows on the arcs phi and the value of the flow v on the virtual arc from sink to source. If v is less than cv, a message is issued, but the computation is done: in this case flag is equal to 0, otherwise it is equal to 1.

The bounds of the flows are given by the elements edge_min_cap and edge_max_cap of the graph list. The value of the minimum capacity must be equal to zero, and the value of the maximum capacity must be non negative and must be integer numbers. If the value of edge_min_cap or edge_max_cap is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

The costs on the edges are given by the element edge_cost of the graph list. The costs must be non negative. If the value of edge_cost is not given (empty row vector []), it is assumed to be equal to 0 on each edge.

The demands, element node_demand of the graph list, must be equal to zero.

This function uses the algorithm of Busacker and Goven.

Examples

ta=[1 1 2 2 2 3 4 4 5 6 6 6 7 7 7 8 9 10 12 12 13 13 13 14 15 14 9 11 10];
he=[2 6 3 4 5 1 3 5 1 7 10 11 5 8 9 5 8 11 10 11 9 11 15 13 14 4 6 9 1];
g=make_graph('foo',1,15,ta,he);
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
g('node_y')=[56 181 276 278 276 103 174 281 177 86 175 90 290 397 399];
show_graph(g);
g1=g; ma=arc_number(g1); n=g1('node_number');
g1('edge_min_cap')=0*ones(1,ma);
rand('uniform');
g1('edge_max_cap')=round(20*rand(1,ma))+ones(1,ma);
g1('edge_cost')=10*rand(1,ma)+ones(1,ma);
source=15; sink=1; cv=5;
[c,phi,v]=min_lcost_cflow(source,sink,cv,g1);
x_message(['The cost is: '+string(c);
           'Showing the flow on the arcs']);
nodetype=0*ones(1,n); nodetype(source)=2; nodetype(sink)=1;
g1('node_type')=nodetype;
ii=find(phi<>0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
g1('edge_color')=edgecolor;
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
nodecolor=0*ones(1,n); nodecolor(source)=11; nodecolor(sink)=11;
g1('node_color')=nodecolor;
g1('edge_font_size')=edgefontsize;
g1('edge_label')=string(phi);
show_graph(g1);
 
  

See also