min_lcost_cflow — minimum linear cost constrained flow
[c,phi,v,flag] = min_lcost_cflow(i,j,cv,g)
integer, source node number
integer, sink node number
scalar, value of constrained flow
value of cost
row vector of the values of flow on the arcs
value of flow from source to sink
feasible constrained flow flag (0 or 1)
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
max_cap fields of the
edges_data_structure. The value of the maximum
capacity must be non negative and must be integer numbers. If the
values of max_cap is not
given, they are assumed to be equal to 0 on each edge.
The costs on the edges are given by the cost field
of the edges_data_structure. The costs must be non
negative. If the value of cost is not given, it is
assumed to be equal to 0 on each edge.
This function uses the algorithm of Busacker and Goven.
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.nodes.graphics.x=[155,153,85,155,237,244,244,334,338,346,442,440,439,333,438];
g.nodes.graphics.y=[45,145,221,222,221,82,139,225,142,69,140,72,232,318,319];
source=15;g.nodes.graphics.type(source)=2; //source node
sink=1;g.nodes.graphics.type(sink)=1; //sink node
show_graph(g);
g=add_edge_data(g,'max_cap',[11,8,9,19,20,8,9,16,6,11,6,12,12,3,6,14,16,2,14,5,9,18,13,11,5,18,3,7,18]);
g=add_edge_data(g,'cost',[9,6,11,7,11,2,8,5,7,10,2,9,10,7,7,9,2,7,2,8,4,6,11,8,1,7,4,4,7]);
flow_constraint=5;
[c,phi,v,flag]=min_lcost_cflow(source,sink,flow_constraint,g);
g.edges.graphics.foreground(find(phi<>0))=color('red');
g=add_edge_data(g,'flow',phi)
g.edges.graphics.display='flow';
show_graph(g);