経路

gistfile1.rb

# encoding: utf-8

class RouteMap
  def initialize(&block)
    @links = []
    block.call(self) if block_given?
  end

  def link(station_a, station_b, time_cost=0)
    @links << Link.new(station_a, station_b, time_cost)
  end

  def routes(from, to, visited_stations=[], routes=[])
    # 計算量を減らす工夫はしていない。
    visited_stations << from
    to_stations = other_stations(from) - visited_stations

    routes << new_route(visited_stations << to) if to_stations.include?(to)

    to_stations.each do |other|
      routes = routes(other, to, visited_stations.clone, routes)
    end
    routes
  end

  def route(from, to)
    route_minimum_time_cost(from, to)
  end

  def route_minimum_time_cost(from, to)
    routes = routes(from, to)
    return nil if routes.empty?

    routes.sort_by { |route| route.time_cost }.first
  end

  def new_route(visited_stations)
    links = (0..visited_stations.size-2).map { |n|
      from, to = visited_stations[n..n+1]
      @links.find { |l| l.link?(from, to) }
    }

    Route.new(visited_stations, links)
  end

  def other_stations(station)
    links_by(station).map { |link| link.other_station(station) }
  end

  def links_by(station)
    @links.select { |link| link.include?(station) }
  end
end

class Link
  attr_reader :time_cost

  def initialize(station_a, station_b, time_cost=0)
    @station_a, @station_b, @time_cost = station_a, station_b, time_cost
  end

  def include?(station)
    @station_a == station || @station_b == station
  end

  def link?(station_a, station_b)
    (@station_a == station_a && @station_b == station_b) ||
    (@station_a == station_b && @station_b == station_a)
  end

  def other_station(station)
    @station_a == station ? @station_b : @station_a
  end
end

class Route
  attr_reader :stations

  def initialize(stations, links)
    @stations = stations
    @links = links
  end

  def time_cost
    @links.map {|l| l.time_cost }.reduce(:+)
  end
end

class Fixnum
  def min
    return self
  end
end

shared_context '標準の経路マップ設定' do
  subject(:route_map) do
    route_map = RouteMap.new do |c|
     [['横浜', '川崎', 14.min],
      ['川崎', '東京', 24.min],
      ['東京', '秋葉原', 6.min],
      ['秋葉原', '田端', 11.min],
      ['田端', '赤羽', 14.min],
      ['赤羽', '南浦和', 16.min],
      ['南浦和', '大宮', 12.min],
      ['横浜', '武蔵小杉', 23.min],
      ['川崎', '武蔵小杉', 19.min],
      ['武蔵小杉', '西国分寺', 50.min],
      ['西国分寺', '南浦和', 36.min],
      ['武蔵小杉', '渋谷', 21.min],
      ['渋谷', '新宿', 10.min],
      ['渋谷', '東京', 25.min],
      ['新宿', '西国分寺', 32.min],
      ['新宿', '池袋', 11.min],
      ['新宿', 'お茶の水', 16.min],
      ['東京', 'お茶の水', 10.min],
      ['お茶の水', '秋葉原', 8.min],
      ['池袋', '田端', 12.min],
      ['池袋', '赤羽', 15.min],
      ['横浜', 'AAA', 999.min],
      ['西国分寺', 'BBB', 888.min],].each {|a, b, time_cost| c.link(a, b, time_cost) }
    end
  end
end

describe '経路マップ#route' do
  context '2つの駅が直接つながっている場合' do
    subject(:route_map) do
      route_map = RouteMap.new do |c|
        c.link('大宮', '横浜')
      end
    end

    it '直接つながっている区間は電車で行けること' do
      route_map.route('横浜', '大宮').stations.should == ['横浜', '大宮']
      route_map.route('大宮', '横浜').stations.should == ['大宮', '横浜']
    end

    it 'つながっていない区間は電車で行けないこと' do
      route_map.route('大島', '横浜').should be_nil
    end
  end

  context '経由駅がある場合も' do
    subject(:route_map) do
      route_map = RouteMap.new do |c|
        c.link('横浜', '東京')
        c.link('東京', '大宮')
      end
    end

    it '電車で行けること' do
      route_map.route('横浜', '大宮').stations.should == ['横浜', '東京', '大宮']
    end
  end

  context '多数の駅がある場合も' do
    include_context '標準の経路マップ設定'

    it '電車で行けること' do
      route_map.route('横浜', '大宮').stations.should == ['横浜', '川崎', '東京', '秋葉原', '田端', '赤羽', '南浦和', '大宮']
      route_map.route('横浜', '渋谷').stations.should == ["横浜", "武蔵小杉", "渋谷"]
    end
  end
end

describe '経路マップ#time_cost' do
  include_context '標準の経路マップ設定'

  it 'かかる時間が計算できること' do
    route_map.route('横浜', '武蔵小杉').time_cost.should == 23.min
  end

  it '経由でもかかる時間が計算できること' do
    route_map.route('横浜', '東京').time_cost.should == 14.min + 24.min
  end
end

describe '経路マップ#route_minimum_time_cost' do
  include_context '標準の経路マップ設定'

  it '最短時間の経路検索できること' do
    route_map.route_minimum_time_cost('川崎', '渋谷').stations.should == ['川崎', '武蔵小杉', '渋谷']
    route_map.route_minimum_time_cost('川崎', '渋谷').time_cost.should == 19.min + 21.min
    route_map.route_minimum_time_cost('新宿', '横浜').stations.should == ['新宿', '渋谷', '武蔵小杉', '横浜']
    route_map.route_minimum_time_cost('新宿', '横浜').time_cost.should == 10.min + 21.min + 23.min
  end
end


shared_context '縮小版経路マップ設定' do
  subject(:route_map) do
    route_map = RouteMap.new do |c|
     [['横浜', '川崎', 14.min],
      ['川崎', '東京', 24.min],
      ['横浜', '武蔵小杉', 23.min],
      ['川崎', '武蔵小杉', 19.min],
      ['武蔵小杉', '渋谷', 21.min],
      ['渋谷', '東京', 25.min],].each { |a, b, time_cost| c.link(a, b, time_cost) }
    end
  end
end

describe '経路マップ#time_cost' do
  include_context '縮小版経路マップ設定'

  it '複数の経路検索できること' do
    route_map.routes('川崎', '渋谷').sort_by {|route| route.time_cost }[0].stations.should == ['川崎', '武蔵小杉', '渋谷']
    route_map.routes('川崎', '渋谷').sort_by {|route| route.time_cost }[1].stations.should == ['川崎', '東京', '渋谷']
    route_map.routes('川崎', '渋谷').sort_by {|route| route.time_cost }[2].stations.should == ["川崎", "横浜", "武蔵小杉", "渋谷"]
  end
end