Class: MinCostFlow
- Inherits:
-
Object
- Object
- MinCostFlow
- Defined in:
- lib/min_cost_flow.rb
Overview
Min Cost Flow Grapsh
Instance Method Summary collapse
- #add(x, to = nil, cap = nil, cost = nil) ⇒ Object
- #add_edge(from, to, cap, cost) ⇒ Object
- #add_edges(edges) ⇒ Object
- #dual_ref(s, t) ⇒ Object
- #edges ⇒ Object
- #flow(s, t, flow_limit = Float::MAX) ⇒ Object (also: #min_cost_max_flow)
- #get_edge(i) ⇒ Object (also: #edge, #[])
-
#initialize(n) ⇒ MinCostFlow
constructor
A new instance of MinCostFlow.
- #slope(s, t, flow_limit = Float::MAX) ⇒ Object (also: #min_cost_slop)
Constructor Details
#initialize(n) ⇒ MinCostFlow
Returns a new instance of MinCostFlow.
5 6 7 8 9 10 11 12 13 14 15 |
# File 'lib/min_cost_flow.rb', line 5 def initialize(n) @n = n @pos = [] @g_to = Array.new(n) { [] } @g_rev = Array.new(n) { [] } @g_cap = Array.new(n) { [] } @g_cost = Array.new(n) { [] } @pv = Array.new(n) @pe = Array.new(n) @dual = Array.new(n, 0) end |
Instance Method Details
#add(x, to = nil, cap = nil, cost = nil) ⇒ Object
44 45 46 |
# File 'lib/min_cost_flow.rb', line 44 def add(x, to = nil, cap = nil, cost = nil) cost ? add_edge(x, to, cap, cost) : add_edges(x) end |
#add_edge(from, to, cap, cost) ⇒ Object
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
# File 'lib/min_cost_flow.rb', line 17 def add_edge(from, to, cap, cost) edge_number = @pos.size @pos << [from, @g_to[from].size] from_id = @g_to[from].size to_id = @g_to[to].size to_id += 1 if from == to @g_to[from] << to @g_rev[from] << to_id @g_cap[from] << cap @g_cost[from] << cost @g_to[to] << from @g_rev[to] << from_id @g_cap[to] << 0 @g_cost[to] << -cost edge_number end |
#add_edges(edges) ⇒ Object
39 40 41 42 |
# File 'lib/min_cost_flow.rb', line 39 def add_edges(edges) edges.each{ |from, to, cap, cost| add_edge(from, to, cap, cost) } self end |
#dual_ref(s, t) ⇒ Object
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 |
# File 'lib/min_cost_flow.rb', line 70 def dual_ref(s, t) dist = Array.new(@n, Float::MAX) @pv.fill(-1) @pe.fill(-1) vis = Array.new(@n, false) que = PriorityQueue.new { |par, chi| par[0] < chi[0] } dist[s] = 0 que.push([0, s]) while (v = que.pop) v = v[1] next if vis[v] vis[v] = true break if v == t @g_to[v].size.times do |i| to = @g_to[v][i] next if vis[to] || @g_cap[v][i] == 0 cost = @g_cost[v][i] - @dual[to] + @dual[v] next unless dist[to] - dist[v] > cost dist[to] = dist[v] + cost @pv[to] = v @pe[to] = i que.push([dist[to], to]) end end return false unless vis[t] @n.times do |i| next unless vis[i] @dual[i] -= dist[t] - dist[i] end true end |
#edges ⇒ Object
57 58 59 60 61 62 63 |
# File 'lib/min_cost_flow.rb', line 57 def edges @pos.map do |(from, id)| to = @g_to[from][id] rid = @g_rev[from][id] [from, to, @g_cap[from][id] + @g_cap[to][rid], @g_cap[to][rid], @g_cost[from][id]] end end |
#flow(s, t, flow_limit = Float::MAX) ⇒ Object Also known as: min_cost_max_flow
65 66 67 |
# File 'lib/min_cost_flow.rb', line 65 def flow(s, t, flow_limit = Float::MAX) slope(s, t, flow_limit).last end |
#get_edge(i) ⇒ Object Also known as: edge, []
48 49 50 51 52 53 |
# File 'lib/min_cost_flow.rb', line 48 def get_edge(i) from, id = @pos[i] to = @g_to[from][id] rid = @g_rev[from][id] [from, to, @g_cap[from][id] + @g_cap[to][rid], @g_cap[to][rid], @g_cost[from][id]] end |
#slope(s, t, flow_limit = Float::MAX) ⇒ Object Also known as: min_cost_slop
113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 |
# File 'lib/min_cost_flow.rb', line 113 def slope(s, t, flow_limit = Float::MAX) flow = 0 cost = 0 prev_cost_per_flow = -1 result = [[flow, cost]] while flow < flow_limit break unless dual_ref(s, t) c = flow_limit - flow v = t while v != s c = @g_cap[@pv[v]][@pe[v]] if c > @g_cap[@pv[v]][@pe[v]] v = @pv[v] end v = t while v != s nv = @pv[v] id = @pe[v] @g_cap[nv][id] -= c @g_cap[v][@g_rev[nv][id]] += c v = nv end d = -@dual[s] flow += c cost += c * d result.pop if prev_cost_per_flow == d result << [flow, cost] prev_cost_per_flow = d end result end |