Làm thế nào để triển khai đồ thị vô hướng trong Ruby on Rails?

Question

tôi cần phải thực hiện một đồ thị vô hướng G = (V, E) trong Ruby on Rails và nghĩ đến việc xây dựng một Vertex và một Cạnh mô hình nơi Vertex has_many Edges.

Là một cạnh kết nối chính xác hai đỉnh, bạn sẽ thực thi điều này trong Rails như thế nào?

Bạn có biết bất kỳ đá quý hoặc thư viện nào có thể giúp triển khai biểu đồ như vậy không (không bắt buộc phải phát minh lại bánh xe ;-)) không?

Answer 1

Không biết bất kỳ thư viện hiện có nào cung cấp lôgic đồ thị ở trên ActiveRecord.

Bạn có thể phải triển khai các mô hình Vertex, Edge ActiveRecord của riêng mình (xem vertex.rb và edge.rb trong thư mục rails/activerecord/test/fixtures cài đặt Rails của bạn), ví dụ:

### From Rails: ### 

# This class models an edge in a directed graph. 
class Edge < ActiveRecord::Base 
    belongs_to :source, :class_name => 'Vertex', :foreign_key => 'source_id' 
    belongs_to :sink, :class_name => 'Vertex', :foreign_key => 'sink_id' 
end 

# This class models a vertex in a directed graph. 
class Vertex < ActiveRecord::Base 
    has_many :sink_edges, :class_name => 'Edge', :foreign_key => 'source_id' 
    has_many :sinks, :through => :sink_edges 

    has_and_belongs_to_many :sources, 
    :class_name => 'Vertex', :join_table => 'edges', 
    :foreign_key => 'sink_id', :association_foreign_key => 'source_id' 
end 

Để tạo một hành vi trên là một adirected đồ thị, hãy nghĩ về cách chèn mép bổ sung cũng như khi chèn một cạnh. Cũng lưu ý rằng việc sử dụng has_and_belongs_to_many hiện không được khuyến khích, bạn có thể sử dụng has_many :sources ... :through => :edges để thay thế. Bất kỳ thực thi nào cũng có thể được thực hiện thông qua xác thực (tức là đỉnh không có cạnh) và/hoặc ràng buộc cơ sở dữ liệu (một ràng buộc/chỉ số duy nhất trên [source_id,sink_id] trong edges đảm bảo rằng các đỉnh V1 ---> V2 không được kết nối bởi nhiều hơn một cạnh được chỉ đạo và các đỉnh V1 < --- V2 không được kết nối bởi nhiều hơn một cạnh được chỉ dẫn.)

Tại thời điểm này, bạn có hai tùy chọn, tùy thuộc vào đồ thị của bạn lớn đến mức nào và bạn muốn bao nhiêu đang đi qua tại bất kỳ điểm nào đã cho trong thời gian:

1. ghi số lượng tối thiểu của logic đồ thị theo yêu cầu của bạn trên các mô hình trên, sử dụng quan hệ ActiveRecord hông (ví dụ: vertex1.edges.first.sink.edges ...); này sẽ dẫn đến một số lượng đáng kể các chuyến đi khứ hồi được thực hiện cho cơ sở dữ liệu
2. nhập RGL; chọn tất cả các đỉnh và cạnh từ DB vào RGL và sử dụng RGL để thực hiện truyền tải đồ thị, ví dụ:

.

edges = Edge.find(:all) 
    dg = RGL::AdjacencyGraph.new(edges.inject([]) { |adj,edge| 
     adj << edge.source_id << edge.sink_id 
    }) 
    # have fun with dg 
    # e.g. isolate a subset of vertex id's using dg, then 
    # load additional info from the DB for those vertices: 
    vertices = Vertex.find(vertex_ids) 

Trên đây mang xuống tổng số điện thoại của các câu lệnh SQL (trong hoạt động read-only) đến 2, nhưng có thể đặt căng thẳng trên cơ sở dữ liệu hoặc bộ nhớ của bạn nếu đồ thị (Edge.find(:all)) là lớn - lúc này bạn có thể nghĩ ra các cách khác để hạn chế lượng dữ liệu bạn thực sự yêu cầu, ví dụ chỉ quan tâm đến các kết nối của red các đỉnh ':

Edge.find(:all, 
       :joins => :sources, # or sinks; indifferent since symmetric 
       :conditions => [ 'vertices.red = ?', true ] 
    )