Tạo mô hình đồ thị vô hướng trong Rails?

Question

Nhập ngôn ngữ của graph databases, hiểu

1. nút (đại diện bởi vòng tròn),
2. cạnh (đại diện bởi mũi tên), và
3. tính (siêu dữ liệu của các nút/cạnh)

Các đồ họa (biếu không của wikipedia) mô tả một directed graph.

Cách tốt nhất để tạo mô hình undirected graph trong Rails là gì?

Đó là để nói, một biểu đồ mà tất cả các cạnh là đối ứng (như trong trên đồ họa), và nơi các thuộc tính của mỗi cạnh đều giống nhau bất kể hướng (trái với trên đồ họa).

Giả sử thiết lập Rails 3 mặc định bằng cách sử dụng cửa hàng sql thông qua ActiveRecord.

Một đôi polymorphic association sẽ tạo biểu đồ có hướng, có thể mô hình dữ liệu được mô tả bằng hình ảnh trên.

def Edge < ActiveRecord::Base 
    belongs_to :head, polymorphic: true 
    belongs_to :tail, polymorphic: true 
end 

class Node < ActiveRecord::Base 
    has_many :from, as: :head 
    has_many :to, as: :tail 
end 

class Group < ActiveRecord::Base 
    # a Node of Type: Group 
    has_many :from, as: :head 
    has_many :to, as: :tail 
end 

Có nên mở rộng mô hình này để quản lý các mối quan hệ nghịch đảo hoặc mô hình tốt hơn không?

---

Một yếu tố của một ứng dụng có thể là một vấn đề đồ thị, nhưng nó không có nghĩa là ứng dụng tập trung vào các vấn đề, rằng transversals đồ thị phải được thực hiện trên các dữ liệu, cũng không phải là các tập dữ liệu lớn hơn bộ nhớ còn trống .

Answer 1

Trong một đồ thị vô hướng, điều duy nhất bạn cần phải biết, là liệu một nút được kết nối với một nút khác. Và không có thứ gì như một hướng.

cách tiếp cận đơn giản:

class Node 
    has_many :connected_nodes 
    has_many :nodes, :through => :connected_nodes 
end 

class ConnectedNode 
    belongs_to :node 
    belongs_to :connected_node, :class_name => 'Node' 
end 

này cũng được gọi là một danh sách kề: cho mỗi nút chúng ta có thể dễ dàng có được danh sách các liền kề nút (kết nối).

Có thể có vấn đề với cách tiếp cận này: chúng tôi lưu trữ các kết nối hai lần. A được kết nối với B và B được kết nối với A.

Vì vậy, có vẻ bình thường hơn để lưu trữ từng kết nối chỉ một lần và sau đó chúng tôi thực sự gần với đề xuất ban đầu của bạn.

class Connection 
    belongs_to :node1, :class_name => 'Node' 
    belongs_to :node2, :clasS_name => 'Node' 
end 

Chỉ chúng tôi làm hết sức mình để không áp đặt bất kỳ thứ tự hoặc hướng nào thông qua đặt tên.

Truy xuất các nút được kết nối là tất cả các nút được kết nối với dạng node1 hoặc là node2, do đó có thể bỏ qua bất kỳ hướng nào có thể có hiệu quả. Trong trường hợp này, bạn cũng cần phải thể hiện xác nhận rằng kết nối với (node1, node2) là duy nhất, nhưng (node2, node1) thực sự giống nhau và không thể chèn hai lần.

Lựa chọn cá nhân của tôi sẽ là sử dụng lược đồ thứ hai, mặc dù việc duy trì giải pháp đầu tiên có thể nhanh hơn (xem thêm question) này.

Tôi cũng tìm thấy một địa chỉ article rất thú vị, nơi tác giả giải thích cách biểu đồ có thể được lưu trữ trong cơ sở dữ liệu. Rất sâu sắc, nhưng có nhiều cơ sở dữ liệu hơn.

Hy vọng điều này sẽ hữu ích.

Answer 2

Thay vì sử dụng các hiệp hội đa hình, hãy thử sử dụng has_many,: thông qua

class Group < ActiveRecord::Base 
    has_many :memberships 
    has_many :persons, :through => :memberships 
end 

class Membership < ActiveRecord::Base 
    belongs_to :group 
    belongs_to :person 
end 

class Person < ActiveRecord::Base 
    has_many :memberships 
    has_many :groups, :through => :memberships 
end 

Bạn có thể lưu trữ các thuộc tính của cạnh int mô hình thành viên.

Answer 3

Tại sao không sử dụng Neo4J?

http://wiki.neo4j.org/content/Ruby

https://github.com/andreasronge/neo4j-rails-example

https://github.com/andreasronge/neo4j