1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
function demo_multiflot()
// The Graph
demo_help demo_multiflot
win=edit_graph(editgraph_diagram(),1,[700,616]);
toolbar(0,'off');
//xset("wpos",500,16);xset("wdim",600*0.9,400*0.9);
ge_set_nodes_id('Label')
ge_set_arcs_id('Label')
G=load_graph('ex3');
G.default_font_size=14;
As=full(graph_2_mat(G)); //Node-Edge incidence Matrix
p=size(As,1); //Number of nodes
n=size(As,2); //Number of arcs
// Image The Multiflow problem on the graph
K=2; //number of flows
sources=[1,10]; // sources nodes index
sinks=[6,3]; // sink nodes index
colors=[3,10]; // color of sources and sink for each flows
values=[5,4]; // values of each flow
// set node source and sink nodes types in Graph data structure
source=2;sink=1;
G.node_type=zeros(1,p);
G.node_type(sources)=source;
G.node_type(sinks)=sink;
// set node source and sink nodes colors in Graph data structure
G.node_color(sources)=colors;
G.node_color(sinks)=colors;
//add label to the nodes
G.node_label=emptystr(1,p);
G.node_label(sources)=string(values)
G.node_label(sinks)=string(-values)
show_graph(G)
//add a title
xstringb(50,600,'Le graphe orient avec les sources et les puits',600, ...
80,'fill')
realtimeinit(0.1);for k=1:50,realtime(k),end // wait a little
// Definition of the LP problem (As,B,c,U)
//let X(i,k) the flow of commodity k on arc i and x=matrix(X,K*n;1)
//Min Cost'*x
//diag(As,As)*x = B = [b1;b2;...];
//[I,I]*x <= U
//Form the Linear Problem matrices
//Column k of B = rhs vector for flow k.
B=zeros(p,K);
for k=1:K
B(sources(k),k)=values(k);
B(sinks(k),k)=-values(k);
end
//Arcs costs
rand('seed',0);
c=rand(n,1); // random cost between 0 and 1
//Arcs capacities
umax=2;
U=umax*ones(n,1); // each arc as the same max capacity 2
//Min Cost'*x
//diag(As,As)*x = B = [b1;b2;...];
//[I,I]*x <= U
//Cost [c;c;...]
Cost=ones(K,1).*.c;
//diag(As,As,...)*x = B = [b1;b2;...];
bigA=eye(K,K).*.As;
//[I,I,...]*x <= U
Capacity=ones(1,K).*.eye(n,n);
Rhs=[B(:);U];lbounds=zeros(K*n,1);ubounds=10^30*ones(K*n,1);
A=full([bigA;Capacity]);mi=K*p;
[x,l,obj]=linpro(Cost,A,Rhs,lbounds,ubounds,mi);
X=matrix(x,n,K);
//Entry (i,k) of X = amount of commodity k circulating on edge i.
X=clean(X,0.0001);
x1=X(1:n);x2=X(n+1:$);
x1=clean(x1,0.0001);x2=clean(x2,0.000001);
I1=sign(x1);I2=sign(x2);
I=sign(X);
w1=find(I(:,1)==1&sum(I,2)~=2);
w2=find(I(:,2)==1&sum(I,2)~=2);
w3=find(sum(I,2)==2);
G.edge_color(w1)=colors(1);
G.edge_color(w2)=colors(2);
G.edge_label(n)=' ';
G.edge_label(w1)=part(string(x1(w1)),1:2);
G.edge_label(w2)=part(string(x2(w2)),1:2);
G.edge_label(w3)='SAT';
G.edge_label=G.edge_label';
ge_set_arcs_id('Label')
show_graph(G);
xstringb(50,600,'Les flots calcul sur les arcs',600, ...
80,'fill')
realtimeinit(0.1);for k=1:50,realtime(k),end // wait a little
ge_do_quit(%f)
xdel(win)
endfunction
|
