Class: CPP

Inherits:
Object
  • Object
show all
Defined in:
lib/spekmachine/runner/path.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

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