← Back to branch summary

~ubuntu-branches/ubuntu/karmic/scilab/karmic

« back to all changes in this revision

Viewing changes to man/metanet/min_qcost_flow.man

  • Committer: Bazaar Package Importer
  • Author(s): Torsten Werner
  • Date: 2002-03-21 16:57:43 UTC
  • Revision ID: james.westby@ubuntu.com-20020321165743-e9mv12c1tb1plztg
Tags: upstream-2.6
Import upstream version 2.6

Show diffs side-by-side

added added

removed removed

Lines of Context:
man/metanet/min_qcost_flow.man
 
1
.TH min_qcost_flow 1 "September 1995" "Scilab Group" "Scilab function"
 
2
.so ../sci.an
 
3
.SH NAME
 
4
min_qcost_flow - minimum quadratic cost flow
 
5
.SH CALLING SEQUENCE
 
6
.nf
 
7
[c,phi,flag] = min_qcost_flow(eps,g)
 
8
.fi
 
9
.SH PARAMETERS
 
10
.TP 4
 
11
eps
 
12
: scalar, precision
 
13
.TP 2
 
14
g
 
15
: graph list
 
16
.TP 2
 
17
c 
 
18
: value of cost
 
19
.TP 4
 
20
phi
 
21
: row vector of the value of flow on the arcs
 
22
.TP 5
 
23
flag
 
24
: feasible problem flag (0 or 1)
 
25
.SH DESCRIPTION
 
26
\fVmin_qcost_flow\fR computes the minimum quadratic cost flow in the network 
 
27
\fVg\fR. It returns the total cost of the flows on the arcs \fVc\fR and
 
28
the row vector of the flows on the arcs \fVphi\fR. \fVeps\fR is the precision
 
29
of the iterative algorithm. If the problem is not feasible (impossible to 
 
30
find a compatible flow for instance), \fVflag\fR is equal to 0, otherwise it 
 
31
is equal to 1.
 
32
 
 
33
The bounds of the flow are given by the elements \fVedge_min_cap\fR and
 
34
\fVedge_max_cap\fR of the graph list. 
 
35
The value of the maximum capacity must be greater than or equal to the 
 
36
value of the minimum capacity.
 
37
If the value of \fVedge_min_cap\fR or \fVedge_max_cap\fR is not given (empty
 
38
row vector \fV[]\fR), it is assumed to be equal to 0 on each edge.
 
39
 
 
40
The costs on the edges are given by the elements \fVedge_q_orig\fR and
 
41
\fVedge_q_weight\fR of the graph list. The cost on arc \fVu\fR is given by:
 
42
 
 
43
\fV(1/2)*edge_q_weight[u](phi[u]-edge_q_orig[u])^2\fR
 
44
 
 
45
The costs must be non negative.
 
46
If the value of \fVedge_q_orig\fR or \fVedge_q_weight\fR is not given (empty 
 
47
row vector \fV[]\fR), it is assumed to be equal to 0 on each edge.
 
48
 
 
49
This function uses an algorithm due to M. Minoux.
 
50
.SH EXAMPLE
 
51
.nf
 
52
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 1 8];
 
53
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 12 14];
 
54
g=make_graph('foo',1,15,ta,he);
 
55
g('node_x')=[194 191 106 194 296 305 305 418 422 432 552 550 549 416 548];
 
56
g('node_y')=[56 221 316 318 316 143 214 321 217 126 215 80 330 437 439];
 
57
show_graph(g);
 
58
g1=g; ma=arc_number(g1);
 
59
rand('uniform');
 
60
while %T then
 
61
  g1('edge_min_cap')=round(5*rand(1,ma));
 
62
  g1('edge_max_cap')=round(20*rand(1,ma))+30*ones(1,ma);
 
63
  g1('edge_q_orig')=0*ones(1,ma);
 
64
  g1('edge_q_weight')=ones(1,ma);
 
65
  [c,phi,flag]=min_qcost_flow(0.001,g1);
 
66
 if flag==1 then break; end;
 
67
end;
 
68
x_message(['The cost is: '+string(c);
 
69
          'Showing the flow on the arcs']);
 
70
ii=find(phi<>0); edgecolor=phi; edgecolor(ii)=11*ones(ii);
 
71
g1('edge_color')=edgecolor;
 
72
edgefontsize=8*ones(1,ma); edgefontsize(ii)=18*ones(ii);
 
73
g1('edge_font_size')=edgefontsize;
 
74
g1('edge_label')=string(phi);
 
75
show_graph(g1);
 
76
.fi
 
77
.SH SEE ALSO
 
78
min_lcost_cflow, min_lcost_flow1, min_lcost_flow2