Class: CPP
- Inherits:
-
Object
- Object
- CPP
- Defined in:
- lib/spekmachine/runner/path.rb
Instance Attribute Summary collapse
-
#c ⇒ Object
readonly
Returns the value of attribute c.
-
#path ⇒ Object
readonly
Returns the value of attribute path.
Instance Method Summary collapse
- #addArc(lab, a, b, cost = 1) ⇒ Object
- #checkValid ⇒ Object
- #convert(index) ⇒ Object
- #convert_to_index(name) ⇒ Object
- #cost ⇒ Object
- #findFeasible ⇒ Object
- #findPath(from) ⇒ Object
- #findUnbalanced ⇒ Object
- #improvements ⇒ Object
-
#initialize ⇒ CPP
constructor
A new instance of CPP.
- #leastCostPaths ⇒ Object
- #phi ⇒ Object
- #printCPT(startVertex) ⇒ Object
- #solve ⇒ Object
- #updateMap(a) ⇒ Object
Constructor Details
#initialize ⇒ CPP
Returns a new instance of CPP.
3 4 5 6 7 8 9 10 11 12 13 14 15 |
# File 'lib/spekmachine/runner/path.rb', line 3 def initialize @delta = Hash.new(0) @defined = Hash.new {|h,k|h[k] = {}} @label = Hash.new {|h,k|h[k] = {}} @c = Hash.new {|h,k|h[k] = Hash.new(0)} @f = Hash.new {|h,k|h[k] = Hash.new(0.0)} @pos = [] @neg = [] @arcs = Hash.new {|h,k|h[k] = Hash.new(0) } @cheapestLabel = Hash.new {|h,k|h[k] = {}} @path = Hash.new {|h,k|h[k] = {}} @basicCost = 0; end |
Instance Attribute Details
#c ⇒ Object (readonly)
Returns the value of attribute c.
2 3 4 |
# File 'lib/spekmachine/runner/path.rb', line 2 def c @c end |
#path ⇒ Object (readonly)
Returns the value of attribute path.
2 3 4 |
# File 'lib/spekmachine/runner/path.rb', line 2 def path @path end |
Instance Method Details
#addArc(lab, a, b, cost = 1) ⇒ Object
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
# File 'lib/spekmachine/runner/path.rb', line 46 def addArc(lab, a, b, cost = 1) u = updateMap a v = updateMap b @n = @nodeList.size @label[u][v] = [] if !@defined[u][v] @label[u][v] << lab @basicCost += cost if !@defined[u][v] or @c[u][v] > cost @c[u][v] = cost @cheapestLabel[u][v] = lab @defined[u][v] = true @path[u][v] = v end @arcs[u][v] += 1 @delta[u] += 1 @delta[v] -= 1; self end |
#checkValid ⇒ Object
82 83 84 85 86 87 88 89 |
# File 'lib/spekmachine/runner/path.rb', line 82 def checkValid @n.times do |i| @n.times do |j| raise "Graph is not strongly connected for #{convert i} and #{convert j}" if !@defined[i][j] end raise "Graph has a negative cycle" if( @c[i][i] < 0 ) end end |
#convert(index) ⇒ Object
25 26 27 |
# File 'lib/spekmachine/runner/path.rb', line 25 def convert(index) @nodeList[index] end |
#convert_to_index(name) ⇒ Object
29 30 31 |
# File 'lib/spekmachine/runner/path.rb', line 29 def convert_to_index(name) @nodeMap[name] end |
#cost ⇒ Object
91 92 93 |
# File 'lib/spekmachine/runner/path.rb', line 91 def cost @basicCost + phi end |
#findFeasible ⇒ Object
122 123 124 125 126 127 128 129 130 131 132 |
# File 'lib/spekmachine/runner/path.rb', line 122 def findFeasible @neg.length.times do |u| i = @neg[u]; @pos.length.times do |v| j = @pos[v]; @f[i][j] = -@delta[i] < @delta[j] ? -@delta[i] : @delta[j]; @delta[i] += @f[i][j]; @delta[j] -= @f[i][j]; end end end |
#findPath(from) ⇒ Object
173 174 175 |
# File 'lib/spekmachine/runner/path.rb', line 173 def findPath(from) ((0...@n).detect {|i| @f[from][i] > 0 }) or -1 end |
#findUnbalanced ⇒ Object
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
# File 'lib/spekmachine/runner/path.rb', line 105 def findUnbalanced nn = np = 0 @n.times do |i| nn += 1 if @delta[i] < 0 np += 1 if @delta[i] > 0 end @neg = [] @pos = [] nn = np = 0; @n.times do |i| @neg[nn] = i and nn += 1 if @delta[i] < 0 @pos[np] = i and np += 1 if @delta[i] > 0 end end |
#improvements ⇒ Object
134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 |
# File 'lib/spekmachine/runner/path.rb', line 134 def improvements residual = CPP.new @neg.length.times do |u| i = @neg[u] @pos.length.times do |v| j = @pos[v] residual.addArc(nil, i, j, @c[i][j]) residual.addArc(nil, j, i, -@c[i][j]) if @f[i][j] != 0 end end residual.leastCostPaths() @n.times do |i| if residual.c[i][i] < 0 k = 0 kunset = true; u = i loop do v = residual.path[u][i]; if residual.c[u][v] < 0 and (kunset || k > @f[v][u]) k = @f[v][u] kunset = false end break if (u = v) == i end u = i; loop do v = residual.path[u][i]; if residual.c[u][v] < 0 @f[v][u] -= k; else @f[u][v] += k; end return true if (u = v) == i end end end false; end |
#leastCostPaths ⇒ Object
65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
# File 'lib/spekmachine/runner/path.rb', line 65 def leastCostPaths @n.times do |k| @n.times do |i| if @defined[i][k] @n.times do |j| if @defined[k][j] and (!@defined[i][j] || @c[i][j] > @c[i][k]+@c[k][j]) @path[i][j] = @path[i][k]; @c[i][j] = @c[i][k]+@c[k][j]; @defined[i][j] = true; return if i == j and @c[i][j] < 0 end end end end end end |
#phi ⇒ Object
95 96 97 98 99 100 101 102 103 |
# File 'lib/spekmachine/runner/path.rb', line 95 def phi phi = 0.0 @n.times do |i| @n.times do |j| phi += @c[i][j]*@f[i][j]; end end phi end |
#printCPT(startVertex) ⇒ Object
177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 |
# File 'lib/spekmachine/runner/path.rb', line 177 def printCPT(startVertex) result = [] v = startVertex; loop do u = v; if (v = findPath(u)) != -1 @f[u][v] -= 1; while u != v do p = @path[u][v]; result << [@cheapestLabel[u][p], u, p] u = p end else bridgeVertex = @path[u][startVertex]; if @arcs[u][bridgeVertex] == 0 return result end v = bridgeVertex; @n.times do |i| if i != bridgeVertex && @arcs[u][i] > 0 v = i; break; end end @arcs[u][v] -= 1; result << [@label[u][v][@arcs[u][v]], u, v] end end raise 'cant get here' end |
#solve ⇒ Object
17 18 19 20 21 22 23 |
# File 'lib/spekmachine/runner/path.rb', line 17 def solve leastCostPaths checkValid findUnbalanced findFeasible loop do break unless improvements end end |
#updateMap(a) ⇒ Object
33 34 35 36 37 38 39 40 41 42 43 44 |
# File 'lib/spekmachine/runner/path.rb', line 33 def updateMap(a) @nodeList ||= [] @nodeMap ||= {} if @nodeMap[a] u = @nodeMap[a] else u = @nodeList.size @nodeMap[a] = u @nodeList << a end u end |