ダイクストラ法によるグラフの最短経路の計算を Ruby で書く

「なっとく！アルゴリズム」という本を読んでいる。アルゴリズムの説明が平易かつ丁寧で、イラストもかわいいのでお気に入りだ。

なっとく！アルゴリズム

この書籍の第 7 章で ダイクストラ法 というグラフの最短経路を求めるためのアルゴリズムが紹介されている。書中には説明のために Python のコードが載っているが、今回は復習を兼ねて Ruby で書き直し、かつオブジェクト指向で実装してみることにした。

以下の重み付き有向グラフの最短経路を求める。

require('forwardable')

class Node
  attr_reader :name

  def initialize(name)
    self.name = name
  end

  def ==(other)
    name == other.name
  end

  private

  attr_writer :name
end

class Edge
  attr_reader :from, :to, :weight

  def initialize(from, to, weight = nil)
    self.from = from
    self.to = to
    self.weight = weight
  end

  private

  attr_writer :from, :to, :weight
end

class Graph
  attr_reader :edges

  def initialize(edges)
    self.edges = edges
  end

  def nodes
    @nodes ||= edges.flat_map { |edge| [edge.from, edge.to] }.uniq
  end

  def neighbor_edges_of(node)
    edges.select { |edge| edge.from == node }
  end

  def start_node
    @start_node ||= (nodes - edges.map(&:to)).first
  end

  def finish_node
    @finish_node ||= (nodes - edges.map(&:from)).first
  end

  private

  attr_writer :edges
end

class DijkstrasAlgorithm
  class Node < Node
    attr_accessor :cost, :parent

    def initialize(name:, cost: nil, parent: nil)
      super(name)
      self.cost = cost
      self.parent = parent
      self.processed = false
    end

    def processed!
      self.processed = true
    end

    def processed?
      processed
    end

    private

    attr_accessor :processed
  end

  extend Forwardable

  private_class_method :new

  def self.call(graph)
    new(graph).send(:call)
  end

  private

  attr_accessor :graph
  def_delegators :graph, :nodes, :edges, :neighbor_edges_of, :start_node, :finish_node

  def initialize(original_graph)
    initialize_graph_by(original_graph)
    initialize_node_properties
  end

  def call
    update_node_costs!
    build_shortest_route
  end

  def initialize_graph_by(original_graph)
    new_nodes = initialize_nodes_by(original_graph.nodes)
    new_edges = initialize_edges_by(original_graph.edges, new_nodes)

    self.graph = Graph.new(new_edges)
  end

  def initialize_nodes_by(original_nodes)
    original_nodes.map { |original_node| Node.new(name: original_node.name) }
  end

  def initialize_edges_by(original_edges, new_nodes)
    original_edges.map do |original_edge|
      Edge.new(
        new_nodes.find { |new_node| new_node == original_edge.from },
        new_nodes.find { |new_node| new_node == original_edge.to },
        original_edge.weight
      )
    end
  end

  def initialize_node_properties
    start_edges = edges.select { |edge| edge.from == start_node }
    nodes.each do |node|
      next node if start_node == node

      start_edge = start_edges.find { |edge| edge.to == node }

      if start_edge
        node.cost = start_edge.weight
        node.parent = start_node
      else
        node.cost = Float::INFINITY
        node.parent = nil
      end
    end
  end

  def update_node_costs!
    loop do
      node = find_lowest_cost_node
      break unless node

      neighbor_edges_of(node).each do |edge|
        new_cost = node.cost + edge.weight

        if edge.to.cost > new_cost
          edge.to.cost = new_cost
          edge.to.parent = node
        end
      end

      node.processed!
    end

    true
  end

  def build_shortest_route
    ordered_nodes = [finish_node]

    loop do
      node = nodes.find { |node| node == ordered_nodes.first.parent }
      ordered_nodes.unshift(node)
      break unless node.parent
    end

    ordered_nodes.map { |node| "(#{node.name})" }.join(' -> ')
  end

  def find_lowest_cost_node
    nodes
      .reject { |node| node.cost.nil? || node.processed? }
      .min_by(&:cost)
  end
end

start = Node.new('start')
a = Node.new('a')
b = Node.new('b')
finish = Node.new('finish')

graph = Graph.new([
  Edge.new(start, a, 6),
  Edge.new(start, b, 2),
  Edge.new(a, finish, 1),
  Edge.new(b, a, 3),
  Edge.new(b, finish, 5)
])

DijkstrasAlgorithm.call(graph)
#=> (start) -> (b) -> (a) -> (finish)

# 念のため別のグラフにもアルゴリズムを適用してみる。

start = Node.new('start')
a = Node.new('a')
b = Node.new('b')
c = Node.new('c')
d = Node.new('d')
finish = Node.new('finish')

graph = Graph.new([
  Edge.new(start, a, 5),
  Edge.new(start, b, 0),
  Edge.new(a, c, 15),
  Edge.new(a, d, 20),
  Edge.new(b, c, 30),
  Edge.new(b, d, 35),
  Edge.new(c, finish, 20),
  Edge.new(d, finish, 10)
])

DijkstrasAlgorithm.call(graph)
#=> (start) -> (a) -> (d) -> (finish)

Hash オブジェクトを使って単純に Ruby に翻訳するだけならすぐに終わったけど、クラスを定義してオブジェクト指向で書き直すと非常に時間がかかった。

Graph の構成要素である Node に経路探索コストをそのまま保存している点が気になる。グラフというデータ構造と経路探索コストの計算というアルゴリズムをどうにかして切り離せないだろうか。でも疲れたのでここまで。

↓

アルゴリズムの計算に特化した専用の Node クラスを用意することで、アルゴリズム実行時の副作用を限定できた。ただ代償として、Graph オブジェクトの複製というコストが掛かっている。

ジェットストリームと初期化されたアンドロイド

社会人になって使う頻度が格段に増したものがいくつかある。その中でも毎日よく使っているのが黒ボールペンだ。メモに使ったり、勉強に使ったり、手帳を書くのに使ったり。僕は油性の ジェットストリーム を愛用している。非常になめらかな書き味で、文字を書くのが快適だ。そして、するすると文字を書けると、書くという行為自体がとても楽しくなる。素晴らしいペンだ。

ペンを多用しているので、それなりの頻度でインクが切れてしまう。そうすると、博多駅の東急ハンズや地元のドンキホーテで新しい替芯を買って、芯を交換する。そのときにとても残念でならないことがひとつある。それが、なめらかな書き味との別れだ。新しい芯はペン先が馴染んでいないためか、非常に書き味が悪い。天下のジェットストリームといえどもだ。少し前まで味わっていた至上の書き心地がとても恋しくなる。

失われた書き味と空っぽになってしまった替芯。それらからは、初期化されたアンドロイドを連想する。スマートフォンではなく、知能を持ったロボットであるアンドロイド。長いときをともにすごし、色々な思い出を作ってきたアンドロイド。しかし彼 (彼女かもしれない) は長い起動時間によって不具合が蓄積し、それはやがて致命的になった。そして、完全な死を回避するためには OS の初期化を余儀なくされてしまった。初期化が終わると、全てを忘れてしまった彼は音声を口にする。「ハジメマシテ。アナタガ ワタシノ ゴシュジンデスカ？」。

このような心を押しつぶすような別れを幾度もなく繰り返してきた僕。でも、僕は新しい相棒とまた新たな思い出を築いていくのだ。やがて訪れる新たな別れの時まで。悲しみのループを繰り返し、僕は少しでもタフになれただろうか。あの暁美ほむらのように。

買い物バグ

どうも僕は買い物に関するバグを抱えているようだ。精算後に商品をレジにそのまま置いていってしまうことが多い。そして今日はその逆で、商品を受け取り精算も済ませたのに、まだ何かしらの処理が残っていると勘違いして、レジの前に居座ってしまった。これまた恥ずかしい。

証明における Q.E.D. (Quod Erat Demonstrandum: かく示された、証明終了) と同様の語句が、買い物におけるおいても存在すると仮定する。買い物終了。僕はこの S.E.D をどのタイミングで示すべきかの判断が著しく苦手なようだ。処理途中で示してしまうこともあれば、示しあぐねてしまうこともある。

これは何かの障害なんだろうか。でも、別に障害だろうが障害でなかろうが、そんなことはどうでもいい。事実困っているし、しばしば恥ずかしい目に合うし、こういった問題が生じないように毎回意識することも難しい。

今日、靴下を買った後にレジに立ち尽くし、一人だけ時間の静止した世界を生きてしまったので書いた。参ったね。

チキンチリ

世の中にはさまざまなチキンがいる。形而上学的チキンと非形而上学的チキン。慎ましいチキンと軽率なチキン。そして、生きたチキンと死んだチキン。

今日出会ったのは、死んだチキンの中の調理されたチキンというサブカテゴリにある「チキンチリ」と呼ばれる存在。昼の華味鳥で出会った。穏やかに陽の沈みゆく北欧の夕暮れのように赤くきらめくソースをまとっている。そして、ソースのとろみがチキンの柔らかさを引き立てている。

チリと言葉には辛いイメージがあるが、辛みと呼べるものはほとんど沈みきっていた。むしろ、わずかな辛みの残滓が、チキンに備わった甘味を引き立てていた。甘いチキンの周りには、これまた甘くてジューシーな野菜が色とりどりに添えられていた。夕暮れの後に待っている賑やかな夜会の始まりがそう遠くないことを思わせる。華味鳥というレストランには、たくさんの明るいイメージや予兆を料理に乗せて提供してくれる、すばらしい場所だ。

主人公がコールガールと寝るシーンで泣いた話

村上春樹の「ダンス・ダンス・ダンス」を読んでいる。2 回目。

ダンス・ダンス・ダンス(上) (講談社文庫)

今までの人生の中で最も感動した小説だったのを覚えている。だから、村上春樹の長編 (今日発売されたばかりの「騎士団長殺し」を除く) をコンプリートした直後に、また読み始めた。

主人公が中学の同級生でイケメン俳優の五反田くんの家を訪れる。五反田くんはふたりのコールガールを呼び、それぞれ女の子とセックスをするシーンがある。僕は電車の中でそのシーンを読んでいて、思わず涙がこぼれた。主人公が娼婦と寝るシーンを読んで、感動のあまり泣いてしまうような小説が他にあるだろうか。

それは同窓会のような集まりだった。文化的雪かきと官能的雪かき。それは雪のたっぷり積もり、しんと静かな朝にふたりで行う本当の雪かきを連想させた。朝日が白い絨毯を照らして、あたりはきらきらと輝いている。その雪かきは多義的なメタファーであるとともに、実際的な雪かきでもあるんだ。そういう様子を連想して、深く感動してしまった。

ちなみに「騎士団長殺し」を読むのはだいぶん後になるだろう。「NieR：Automata」をプレイしなくてないけないし、「ニンテンドースイッチ」の発売日も近い。娯楽の予定がたくさん詰まっていることはとてもいいことだ。なぜなら、生きていくうえで退屈というのは無味無臭の劇薬だから。

華味鳥と奇跡的なチキン竜田について

今、僕が語るべきことはそう多くないと思う。筆舌を尽くして語るべきはたったひとつ。そう、華味鳥のチキン竜田のことについてのみだ。

華味鳥 は水炊き料理のチェーン店だ。僕の勤めている会社のオフィスのすぐそばに店舗があるため、気の合う同僚たちとランチによく通っている。しかし、そこで食すのは水炊き料理ではない。水炊きのランチは手頃な値段ではない。それは、お金と時間にある程度めぐまれた専業主婦が、優雅なひとときをすごすために通うランチの値段だ。かわりに、僕たちは定食を食べる。華味鳥の定食は量が多くて美味しい割に値段はそれほど高くない。非常にコストパフォーマンスに優れている。しかも食後のコーヒーまで無料でついてくる (無限に使える無料コーヒー券を、なぜか同僚が所持している) 。

華味鳥には通常のランチメニューに加え、週替りの定食メニューが存在する。今週は「チキン竜田」だ。華味鳥には長く通っているが、週替り定食としてハズレと呼べるものが出されたことは一度たりともなかった。そして、今日のチキン竜田は群を抜いて美味しかった！

特筆すべきはその衣だ。カラッと香ばしく揚げられていることがわかる、こんがり色の衣。それを口に運ぶと感じられる驚異的なサクサク感。まるで、どこまでも空気の透き通った真冬の朝に、新鮮な霜を足で踏みつけたときのような爽快さがそこにはある。

実は月曜日にも既にこのチキン竜田を味わっていた。しかし、今日のチキン竜田は、さらに美味しさと衣のサクサクさが増していたような気がするのだ。だから語らずにはいられなくなった。そして、軽妙な食感とそのグレードアップは、何かよいことの予兆を感じさせてくれて、気持ちまで爽快にさせてくれた。

これが定番メニューだったらなとも考えた。でも、よく考えなおすと、この幸せは一期一会という制約の上に成り立っているのではと思った。定番メニューとなれば、ありがたみは薄れてしまい、そこから見出した予兆は失われてしまう。またいつか、このチキン竜田と出会えることを祈って、今の幸せを精一杯享受することにしよう。それがいい。

最後に。「唐揚げ」と「チキン竜田」と「ザンギ」の違いに詳しいマエストロがいたら、私のところに来なさい！以上！

望まぬ蓄え

この冬、僕のお腹が着実に肥えている。厳しい寒さを理由に、いつもの日課である帰宅時のウォーキングをさぼっているせいだ。このだらしのないお腹は、行き場のない在庫を抱える暗い倉庫を連想させ、ときおり僕を悲しい気持ちにさせる。

今、いくつかの種類の動物は冬の長い眠りについている。生き残りを賭け、越冬のために蓄えた栄養を切り詰めて消費しながら。その一方で、この僕はどうだろう。何の危機感も抱かずに温かな場所でふんぞり返り、あまつさえ、ぶくぶくと肥え太っている。これを体たらくと呼ばずになんと呼べばいいのだろうか。

今はまだポケモンの ジュゴン のように、優しいふくよかさを備えたお腹だ。しかし、油断するとそれは、あっという間に トドゼルガ へと変貌してしまうだろう。その太さにもはや優しさと呼べるものはなく、残るのは悲しい暴力性だけだ。

しかし、僕はこりずに明日の昼も 華味鳥 へ向かうのだろう。週に 3 回以上はここに通っている。親切で気の利いた店員さんに案内され、柔らかで味わい深い鳥料理をバクバクと食らうのだ。ああ、人間の進歩の無さというのはなんとも度し難いものだ。

ちなみに、この文章は 乳酸菌ショコラ アーモンドチョコレート を食べながら書いた。しかも、歯磨きもデンタルフロスも終わった後で。なんということだ。