Advertisement
Guest User

Untitled

a guest
Jun 19th, 2019
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.27 KB | None | 0 0
  1. const compare = (a, b) => a[0] - b[0];
  2. const amount_to_node = amount => [amount];
  3.  
  4. /* Single commodity, maximum flow, minimum cost optimizer, msand@seaber.io */
  5. function optimize(supplies, demands, costs) {
  6. const supply_nodes = supplies.map(amount_to_node);
  7. const demand_nodes = demands.map(amount_to_node);
  8.  
  9. const num_supplies = supplies.length;
  10. const num_demands = demands.length;
  11. const edges = [];
  12.  
  13. for (let from = 0; from < num_supplies; from++) {
  14. const f = costs[from];
  15. const supply = supply_nodes[from];
  16. for (let to = 0; to < num_demands; to++) {
  17. const demand = demand_nodes[to];
  18. const cost = f[to];
  19. edges.push([
  20. cost,
  21. supply,
  22. demand,
  23. from,
  24. to,
  25. ]);
  26. }
  27. }
  28.  
  29. edges.sort(compare); // Most expensive part of the function
  30.  
  31. const num_edges = edges.length; // = num_supplies * num_demands;
  32. for (let e = 0; e < num_edges; e++) {
  33. const edge = edges[e];
  34. const supply = edge[1];
  35. const demand = edge[2];
  36. const amount = Math.min(supply[0], demand[0]);
  37. supply[0] -= amount;
  38. demand[0] -= amount;
  39. edge[5] = amount;
  40. }
  41.  
  42. return edges;
  43. }
  44.  
  45. const supplies = [12, 23];
  46. const demands = [7, 17];
  47. const costs = [[3, 6], [5, 7]];
  48. console.log(optimize(supplies, demands, costs));
  49. ```
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement