kairo-gokko (4-2) データの整形 3

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

はい、では WireFragment（以下 WF）の集合をエッジの集合に変換する to_edges メソッドを作っていきます。

LibreOffice Draw で描いた大元のデータはこう。要素が多いとデバッグが面倒なので少なめにしました。

f:id:sonota88:20200221072609p:plain

目標イメージはこんな感じです。

f:id:sonota88:20200221050928p:plain

※ 変換後の出力はグラフなんですが、入力もまたグラフなので、ややこしくならないように今回は入力データでは「点」「WF」、出力データでは「ノード」「エッジ」と呼び方を分けます。

次の図のように、開始点から出発してエッジのもう一方の終端まで WF を辿っていけばいいんじゃないでしょうか。

f:id:sonota88:20200220063419p:plain

で、1本のエッジが取り出せたら、また次のエッジを取り出し、全部取り出せるまで繰り返すと。

このとき、通過した WF にフラグを立てておいて、一度通ったところをまた通らないようにします。

おおざっぱにはこんな感じでどうでしょうか。

では細かいところを詰めましょう。

まずは出発点をリストアップする必要があります。

f:id:sonota88:20200220063446p:plain

直感的には図で赤丸を付けている点です。すべての点の中から、何らかの条件でふるい分けて赤丸の点だけ探し出したい。

これは入力のグラフの次数（グラフ理論の用語。各点につながっている WF の数）を見るだけで分かります。

f:id:sonota88:20200221055323p:plain

見ての通りですね。次数が 2 ではない点を選べば、それが出発点（兼、終着点）です。

というわけで、まずは点（のセル座標）から次数を引くためのマッピング（以下、次数マップ）を用意します。これは簡単。

def make_degree_map(wf_set)
  map = Hash.new(0)

  wf_set.each { |wf|
    map[wf.pos1] += 1
    map[wf.pos2] += 1
  }

  map
end

degree_map = make_degree_map(wf_set)

次数マップができたら、それを使って出発点のリストを作るのも簡単。

def select_start_points(degree_map)
  pts = []

  degree_map.each { |pt, degree|
    pts << pt if degree != 2
  }

  pts
end

start_pts = select_start_points(degree_map)

処理に都合のよいデータをもう1つ用意します。

{
  pt1 => [
    wf11,
    wf12,
    ...
  ],
  pt2 => [
    wf21,
    wf22,
    ...
  ]
}

要するにつながっている順に WF を辿っていきたいので、そのために都合がよいデータです。

たとえば点 pt1 から出発した場合、 pt1 => wf11 => pt11 のように、 WF と WF を経由した次の点 pt11 が分かり、同じように点 pt11 から出発して次の WF と点を pt11 => wf… => pt... と辿っていくことができます。

こういうデータ構造はグラフのアルゴリズムではよく使われるらしく、「隣接リスト」と呼ばれているそうです。

def make_pt_wfs_map(wf_set)
  pt_set = Set.new

  wf_set.each { |wf|
    pt_set << wf.pos1
    pt_set << wf.pos2
  }

  map = {}

  # 空配列で初期化
  pt_set.each { |pt| map[pt] = [] }

  wf_set.each { |wf|
    map[wf.pos1] << wf
    map[wf.pos2] << wf
  }

  map
end

pt_wfs_map = make_pt_wfs_map(wf_set)

データが用意できたのでエッジを取り出す処理を書きます。

def take_edge(degree_map, pt_wfs_map, pt0, wf1)
  wfs = []

  wf1.visit()
  wfs << wf1

  work_pt = wf1.opposite_pos(pt0)

  loop do
    next_wfs =
      if degree_map[work_pt] == 2
        pt_wfs_map[work_pt].select { |wf| ! wf.visited }
      else
        # 次数が 2 以外の場合は次の経路なし
        []
      end

    case next_wfs.size
    when 0
      break
    when 1
      # OK
    else
      # assert
      raise "next_wfs.size must be 0 or 1"
    end

    next_wf = next_wfs[0]

    next_wf.visit()
    wfs << next_wf

    work_pt = next_wf.opposite_pos(work_pt)
  end

  Unit::Edge.new(
    pt0,
    work_pt,
    wfs
  )
end

next_pt = wf.opposite_pos(pt) という操作により、WF を挟んで pt と反対側の点 next_pt（次に進むべき点）が得られるようにしています。

Edge には、両方の端点と、WF の配列を持たせておきます。 WF の配列そのままだと無駄が多いのでスリムにしたいところですが、先に進みたいので放置。

これらをまとめて、 to_edges() はこう。

def to_edges(wf_set)
  degree_map = make_degree_map(wf_set)
  start_pts = select_start_points(degree_map)
  pt_wfs_map = make_pt_wfs_map(wf_set)

  edges = []

  start_pts.each { |start_pt|
    pt_wfs_map[start_pt].each { |wf|
      next if wf.visited
      edges << take_edge(degree_map, pt_wfs_map, start_pt, wf)
    }
  }

  edges
end

edges = to_edges(wf_set)

描画するときも wf_set を直接使うのではなく、 edges を使うようにしてみます。

edges.each { |edge|
  edge.wfs.each { |wf|
    drawer.draw_line(
      wf.x1 + 0.5, wf.y1 + 0.5,
      wf.x2 + 0.5, wf.y2 + 0.5,
      C_WHITE
    )
  }
}

f:id:sonota88:20200221050928p:plain

できました！（エッジの色とノードの赤い点は適当に描き加えたものです）

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