Class: RubyLabs::TSPLab::Map

Inherits:
Object
  • Object
show all
Defined in:
lib/tsplab.rb

Overview

Map

A Map is a 2D array of distances between pairs of cities. Use the index operator to look up the distance between two points. For example, given a Map object m, call <tt>m to find the distance between cities i and j. Indices i and j can be symbols or integers.

Instance Method Summary collapse

Constructor Details

#initialize(arg) ⇒ Map

Create a new Map object. If the argument is an integer n, make a map with n cities at random locations (see the method make_random_map for a description of how the cities are chosen). If the argument is a symbol, read a file with that name from the TSPLab data directory. If the argument is a string, look for a file with that name in the current directory.

Example:

>> m = Map.new(10)
=> #<TSPLab::Map [0,1,2,3,4,5,6,7,8,9]>
>> m = Map.new(:ireland)
=> #<TSPLab::Map [belfast,cork,dublin,galway,limerick]>



60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
# File 'lib/tsplab.rb', line 60

def initialize(arg)
  @labels = Array.new
  @dist = Array.new
  @coords = Array.new
  if arg.class == String || arg.class == Symbol
    read_file(arg)
  elsif arg.class == Fixnum
    make_random_map(arg)
  # elsif arg.class == Array
  #   make_map(arg)
  else
    raise "Map.new: parameter must be a symbol, a file name, or an integer"
  end
end

Instance Method Details

#[](i, j) ⇒ Object

Return the distance between cities i and j (which can be given in either order, i.e. d[i,j] is the same as d[j,i]).

Example:

>> m = Map.new(:ireland)
=> #<TSPLab::Map [belfast,cork,dublin,galway,limerick]>
>> m[:cork, :dublin]
=> 257.0

>> m = Map.new(10)
=> #<TSPLab::Map [0,1,2,3,4,5,6,7,8,9]>
>> m[6,2]
=> 111.07



290
291
292
293
294
295
 
# File 'lib/tsplab.rb', line 290

def [](i,j)
  ix = @labels.index(i) or return nil
  jx = @labels.index(j) or return nil
  ix, jx = jx, ix if ix < jx
  @dist[ix][jx]
end

#[]=(i, j, val) ⇒ Object

Update the map by assigning a new distance between cities i and j.

Example:

>> m[6,2] = 110
=> 110



303
304
305
306
307
308
309
 
# File 'lib/tsplab.rb', line 303

def []=(i,j,val)
  raise "Map: can't assign to diagonal" if i == j
  ix = index_of(i)
  jx = index_of(j)
  ix, jx = jx, ix if ix < jx
  @dist[ix][jx] = val.to_f
end

#coords(x) ⇒ Object

Return the canvas coordinates of city x.



339
340
341
 
# File 'lib/tsplab.rb', line 339

def coords(x)
  return @coords[index_of(x)]
end

#display(fw = nil) ⇒ Object

Print the complete set of driving distances in the map in the form of a symmetric matrix. The argument is the field width (number of chars in each matrix entry). If no argument is passed, the method uses the number of letters in the longest city name as the field width.

Example:

>> m = Map.new(:ireland)
=> #<TSPLab::Map [belfast,cork,dublin,galway,limerick]>
>> m.display
          belfast     cork   dublin   galway limerick 
 belfast      0.00
    cork    425.00     0.00
  dublin    167.00   257.00     0.00
  galway    306.00   209.00   219.00     0.00
limerick    323.00   105.00   198.00   105.00     0.00



99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/tsplab.rb', line 99

def display(fw = nil)
  if fw.nil?
    lw = labels.inject(0) { |max, x| n = x.to_s.length;  (n > max) ? n : max }
    dw = (log10(@maxdist).ceil+4)
    fw = max(lw+1,dw)
  end
  res = " " * fw
  @labels.each { |name| res << sprintf("%#{fw-1}s ", name.to_s[0..fw-1]) }
  res += "\n"
  @dist.each_with_index do |a,i| 
    res += sprintf("%#{fw-1}s ", @labels[i].to_s[0..fw-1])
    a.each { |x| res += (x.nil? ? "  --  " : sprintf("%#{fw}.2f", x)) }
    res += "\n"
  end
  puts res
end

#dist ⇒ Object

Return a copy of the distance matrix for this map, in the form of 2D triangular array of Floats.

Example:

>> m = Map.new(:ireland)
=> #<TSPLab::Map [belfast,cork,dublin,galway,limerick]>
>> m.dist
=> [[0.0], [425.0, 0.0], [167.0, 257.0, 0.0], [306.0, 209.0, 219.0, 0.0], [323.0, 105.0, 198.0, 105.0, 0.0]]



331
332
333
334
335
 
# File 'lib/tsplab.rb', line 331

def dist
  d = Array.new
  @dist.each { |row| d << row.clone }
  return d
end

#each_tour ⇒ Object

Generate all possible tours of this map. Every tour starts in the first city (city 0 when city names are integers, or the first city read from the file). Successive tours are generated by the Johnson-Trotter algorithm, which generates permutations by exchanging just two cities from the previous tour. The Johnson-Trotter algorithm makes it possible to stop iterating after all unique tours starting from city 0 have been generated.

Example:

>> m = Map.new(5)
=> #<TSPLab::Map [0,1,2,3,4]>
>> m.each_tour { |t| puts t }
#<TSPLab::Tour [0, 1, 2, 3, 4] (865.11)>
#<TSPLab::Tour [0, 1, 2, 4, 3] (1042.97)>
#<TSPLab::Tour [0, 1, 4, 2, 3] (987.40)>
#<TSPLab::Tour [0, 4, 1, 2, 3] (808.91)>
#<TSPLab::Tour [0, 4, 1, 3, 2] (741.31)>
#<TSPLab::Tour [0, 1, 4, 3, 2] (941.69)>
#<TSPLab::Tour [0, 1, 3, 4, 2] (975.37)>
#<TSPLab::Tour [0, 1, 3, 2, 4] (843.23)>
#<TSPLab::Tour [0, 3, 1, 2, 4] (842.59)>
#<TSPLab::Tour [0, 3, 1, 4, 2] (919.17)>
#<TSPLab::Tour [0, 3, 4, 1, 2] (941.06)>
#<TSPLab::Tour [0, 4, 3, 1, 2] (796.88)>
=> nil



223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
 
# File 'lib/tsplab.rb', line 223

def each_tour
  a = []
  n = @labels.length
  for i in 1...n do
    a << ItemWithDirection.new(i, true)
  end
  loop do
    # yield [0] + a
    yield Tour.new(self, [@labels[0]] + a.map { |x| @labels[x.value] })
    mover = nil
    for i in 0...a.length
      mover = i if movable(a,i) && (mover.nil? || a[i].value > a[mover].value)
    end
    break if mover.nil?
    k = a[mover].value
    # puts "mover = #{mover} k = #{k}"
    break if k == 2
    adj = a[mover].direction ? mover-1 : mover+1
    a[adj], a[mover] = a[mover], a[adj]
    for i in 0...a.length
      if a[i].value > k
        a[i].direction ^= true 
      end
    end
  end
end

#first ⇒ Object

Return the first pair of city labels in this map – used only by read_file when loading a map from a file.



259
260
261
 
# File 'lib/tsplab.rb', line 259

def first   # :nodoc:
  return @labels[0..1]
end

#inspect ⇒ Object Also known as: to_s

Generate a string that lists the cities in this map object.



77
78
79
 
# File 'lib/tsplab.rb', line 77

def inspect
  sprintf "#<TSPLab::Map [%s]>", @labels.join(",") 
end

#labels ⇒ Object

Return a list of city names for this map.

Example:

>> m = Map.new(:ireland)
=> #<TSPLab::Map [belfast,cork,dublin,galway,limerick]>
>> m.labels
=> [:belfast, :cork, :dublin, :galway, :limerick]



319
320
321
 
# File 'lib/tsplab.rb', line 319

def labels
  return @labels.clone
end

#make_tour(*args) ⇒ Object

Creat a new Tour object that represents a path that connects cities in this map. If the argument is an array of city names, the tour will include just these cities, in the order they are given (the array does not have to include all the cities). If the method is called without any arguments it returns a tour that contains all the cities in the order in which they were defined. The third situation is to pass a symbol as the first argument in the call, in which case the symbol specifies how the new tour is created:

m.make_tour(:random)

make a complete tour of all cities in a random order

m.make_tour(:mutate, t1)

the new tour is a copy of t1 with a single point mutation

m.make_tour(:cross, t1, t2)

the new tour is a cross between tours t1 and t2.

Example:

>> m = Map.new(10)
=> #<TSPLab::Map [0,1,2,3,4,5,6,7,8,9]>
>> m.make_tour([2,4,6])
=> #<TSPLab::Tour [2, 4, 6] (871.38)>
>> t1 = m.make_tour
=> #<TSPLab::Tour [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] (2161.70)>
>> t2 = m.make_tour(:random)
=> #<TSPLab::Tour [8, 6, 7, 5, 4, 0, 1, 9, 2, 3] (2294.16)>
>> m.make_tour(:mutate, t1)
=> #<TSPLab::Tour [0, 1, 2, 3, 5, 4, 6, 7, 8, 9] (2426.67)>
>> m.make_tour(:cross, t1, t2)
=> #<TSPLab::Tour [4, 5, 6, 7, 8, 9, 0, 1, 2, 3] (2161.70)>



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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
 
# File 'lib/tsplab.rb', line 141

def make_tour(*args)
  begin
    args << :nil if args.length == 0
    case args[0]
    when :nil
      tour = Tour.new(self, labels)    # note labels returns clone of @labels array...
    when :random
      tour = Tour.new(self, permute!(labels))
    when :mutate
      raise "usage" unless args.length >= 2 && args[1].class == Tour && (args[2].nil? || args[2].class == Fixnum)
      child = args[1].clone
      dmax = args[2] ? args[2] : 1
      i = rand(size)
      d = 1 + rand(dmax)
      # puts "mutate #{i} #{d}"
      tour = child.mutate!(i,d)
      child.parent = args[1]
      child.op = [:mutate, i, d]
    when :cross
      raise "usage" unless args.length == 3 && args[1].class == Tour && args[2].class == Tour
      child = args[1].clone
      i = rand(size)
      n = 1 + rand(size-1)
      # puts "cross #{i} #{n}"
      tour = child.cross!(args[2], i, n)
      child.parent = args[1]
      child.op = [:cross, args[2], i, n]
    else
      raise "usage" unless args[0].class == Array
      a = args[0]
      errs = 0
      a.each do |x|
        if ! @labels.include?(x)
          puts "unknown city: #{x}"
          errs += 1
        end
      end
      raise "errors in list of cities" if errs > 0
      tour = Tour.new(self, a)  
    end
  rescue Exception => e
    if e.message == "usage"
      puts "Usage:"
      puts "  make_tour( [x,y,..] )"
      puts "  make_tour( :random )"
      puts "  make_tour( :mutate, t [,n] )"
      puts "  make_tour( :cross, t1, t2 )"
    else
      puts "make_tour: #{e.message}"
    end
    return nil
  end
  
  return tour
  
end

#rest ⇒ Object

Iterate over every other pair of city labels except the first – used only by read_file when loading a map from a file.



266
267
268
269
270
271
272
273
274
 
# File 'lib/tsplab.rb', line 266

def rest   # :nodoc:
  n = @labels.length
  @labels.each_with_index do |x,i| 
    @labels.last(n-i-1).each_with_index do |y,j|
      next if i == 0 && j == 0
      yield(x,y)
    end
  end
end

#size ⇒ Object

Return the number of cities in this map.



252
253
254
 
# File 'lib/tsplab.rb', line 252

def size
  return @labels.length
end