30 lines
1.3 KiB
Text
30 lines
1.3 KiB
Text
fcn vogel(costs,supply,demand){
|
|
// a Dictionary can be created via a list of (k,v) pairs
|
|
res:= Dictionary(costs.pump(List,fcn([(k,_)]){ return(k,D()) }));
|
|
g := Dictionary(); // cross index costs and make writable
|
|
supply.pump(Void,'wrap([(k,_)]){ g[k] =
|
|
costs[k].keys.sort('wrap(a,b){ costs[k][a]<costs[k][b] }).copy() });
|
|
demand.pump(Void,'wrap([(k,_)]){ g[k] =
|
|
costs.keys.sort('wrap(a,b){ costs[a][k]<costs[b][k] }).copy() });
|
|
|
|
while(g){
|
|
d:=Dictionary(demand.pump(List,'wrap([(k,_)]){ return(k,
|
|
g[k][0,2].apply('wrap(gk){ costs[gk][k] }).reverse().reduce('-)) }));
|
|
s:=Dictionary(supply.pump(List,'wrap([(k,_)]){ return(k,
|
|
g[k][0,2].apply('wrap(gk){ costs[k][gk] }).reverse().reduce('-)) }));
|
|
f:=(0).max(d.values); f=d.filter('wrap([(_,v)]){ v==f })[-1][0];
|
|
t:=(0).max(s.values); t=s.filter('wrap([(_,v)]){ v==t })[-1][0];
|
|
t,f=(if(d[f]>s[t]) T(f,g[f][0]) else T(g[t][0],t));
|
|
v:=supply[f].min(demand[t]);
|
|
res[f].appendV(t,v); // create t:(v) or append v to t:(...)
|
|
if(0 == (demand[t]-=v)){
|
|
supply.pump(Void,'wrap([(k,n)]){ if(n!=0) g[k].remove(t) });
|
|
g.del(t); demand.del(t);
|
|
}
|
|
if(0 == (supply[f]-=v)){
|
|
demand.pump(Void,'wrap([(k,n)]){ if(n!=0) g[k].remove(f) });
|
|
g.del(f); supply.del(f);
|
|
}
|
|
}//while
|
|
res
|
|
}
|