Tìm mối liên hệ ngắn nhất giữa 2 phần tử trong bảng n*n

Trong công việc nhiều lúc bạn gặp phải vấn đề tìm mối liên hệ ngắn nhất (thông qua ít bước trung gian nhất) giữa 2 phần tử, tip nhỏ sau đây hi vọng sẽ giúp bạn phần nào, giả sử có bảng person và bảng liên hệ giữa các phần tử people_relation

class Person < ActiveRecord::Base
  has_many :people_relations
  has_many :other_ones, class_name: Person.name,
    through: :people_relations
end

class PeopleRelation < ActiveRecord::Base
  belongs_to :person
  belongs_to :other_one, class_name: Person.name, foreign_key: :other_one_id
end

ActiveRecord::Schema.define(version: 20151121090958) do
  create_table "people", force: :cascade do |t|
    t.string   "name"
    t.integer  "score"
    t.datetime "created_at", null: false
    t.datetime "updated_at", null: false
  end

  create_table "people_relations", force: :cascade do |t|
    t.integer  "person_id"
    t.integer  "other_one_id"
    t.datetime "created_at",   null: false
    t.datetime "updated_at",   null: false
  end
end

Bây giờ cần tạo 1 def trong model person tìm mối liên hệ ngắn nhất tới 1 id nào đó, đầu tiên tại model people_relation viết thêm:

  validates_exclusion_of :other_one_id, in: ->(p){[p.person_id]}, message: "same people"

  after_create do
    unless PeopleRelation.find_by(person_id: other_one_id, other_one_id: person_id)
      PeopleRelation.create person: other_one, other_one: person
    end
  end

phần này để validate mối liên hệ giữa các person, trong model person viết thêm:

  scope :by_score, ->score{where score: score}

  def update_score
    other_ones.each do |other_one|
      other_one.update score: other_one.score || score + 1
    end
  end

  def find_nearest to_id
    return [] if id == to_id
    reset_score
    mark_score score, to_id
    @way = []
    find_back_way to_id
    @way.reverse.join " -> "
  end

  private
  def reset_score
    Person.update_all score: nil
    self.update score: 1
  end

  def mark_score index, to_id
    return if (Person.find_by(id: to_id).score) || (index > Person.count)
    Person.by_score(index).map(&:update_score)
    mark_score index + 1, to_id
  end

 def find_back_way to_id
    to_person = Person.find_by(id: to_id)
    return unless to_person.try(:score) || 1 == to_person.try(:score)
    @way << to_id
    find_back_way to_person.other_ones.find_by(score: to_person.try(:score) - 1).try(:id)
  end

Hàm find_nearest làm nhiệm vụ tìm mối liên hệ gần nhất, gọi tới 2 hàm mark_score và find_back_way, hàm mark_score làm nhiệm vụ dánh score tăng dần theo số lượng bước liên hệ cho tới khi tìm được person với id cần tìm đến, hàm find_back_way làm nhiệm vụ lần ngược lại các bước đi với bằng cách tìm các person có liên hệ và có score nhỏ hơn 1 đơn vị, thử với file seed:

9.times do |n|
  Person.create name: "Person_" + n.to_s
end

Person.all.each do |person|
  person.other_one_ids += [*(person.id + 1)..Person.last.id].sample(1)
end

Và chạy console để xem kết quả: Thực chất đây là thuật toán loang rộng dần và đánh score mối liên hệ, cảm ơn bạn đã đọc, hi vọng bài viết giúp ích phần nào trong công việc của bạn.