kairo-gokko (18) 回路の分割 2

目次ページに戻る / 前 / 次

子回路へ分割の実装編です。

修正前はこうなっていたのを、

# class ChildCircuit

  def self.create(lines, rects)
    all_plus_poles = ...
    all_minus_poles = ...
    all_switches = ...

    wf_set = to_wire_fragments(lines)
    all_edges = to_edges(wf_set)

    ChildCircuit.new(
      all_edges,
      all_plus_poles,
      all_minus_poles,
      all_switches
    )
  end

次のように変更しました。

  def self.create(lines, rects)
    all_plus_poles = ...
    all_minus_poles = ...
    all_switches = ...

    wf_set = to_wire_fragments(lines)
    all_edges = to_edges(wf_set)

    edge_groups = to_edge_groups(all_edges)

    edge_groups.map { |edges|
      plus_poles  = select_child_circuit_units(edges, all_plus_poles)
      minus_poles = select_child_circuit_units(edges, all_minus_poles)
      switches    = select_child_circuit_units(edges, all_switches)

      ChildCircuit.new(
        edges,
        plus_poles,
        minus_poles,
        switches
      )
    }
  end

to_edge_groups() でエッジを子回路ごとにグループ化し、
グループごとに
- select_child_circuit_units() でグループ内のエッジ上にあるプラス極、マイナス極、スイッチだけを選び、
- edges と一緒に ChildCircuit.new に渡してインスタンスを生成

to_edge_groups() は何をしているかというのが下記です。ここが分割処理のメインの部分。

  def self.to_edge_groups(all_edges)
    ecs = all_edges.map { |edge| EdgeCluster.new([edge]) }

    loop do
      merge_occured = false

      ecs.combination(2).each { |ec_a, ec_b|
        if ec_a.connected_to?(ec_b)
          ec_a.merge(ec_b)
          merge_occured = true
        end
      }

      break unless merge_occured

      ecs = ecs.reject { |ec| ec.edges.empty? }
    end

    ecs.map { |ec| ec.edges }
  end

EdgeCluster はエッジの配列と便利メソッドを持つ作業用のクラスです。

EdgeCluster 1つにつき 1本のエッジを持たせた状態から開始し、
EdgeCluster 同士のすべての組み合わせについてエッジのいずれかがつながっているかを調べ、
- つながっていたら片方の EdgeCluster が持っているエッジの配列をもう片方にマージ（移動）する。
マージが発生しなくなるまで繰り返す

小さなクラスタ同士をちょっとずつくっつけていって、それ以上くっつかなくなったら終わり、みたいなイメージですね。オレオレなのでもっと良い方法があるかもしれません。

最初は組み合わせの列挙をベタに二重ループで書いていましたが、 Array#combination で書けると気づいて書き直しました。便利。

Array#combination (Ruby 2.7.0 リファレンスマニュアル)
https://docs.ruby-lang.org/ja/latest/method/Array/i/combination.html

2つのエッジがつながっているかどうかを判断するにはノードが重なっているかを見てあげれば OK。

# class EdgeCluster

    def connected_to?(other)
      all_node_set.intersect?(other.all_node_set)
    end

以上で子回路ごとに分割する処理ができました。あとは、 ChildCircuit.create が単体の ChildCircuit ではなく ChildCircuit の配列を返すようになったので、それに合わせて preprocess.rb や main.rb を修正すればできあがりです。

f:id:sonota88:20200308170322g:plain