ruby-on-rails - 在 Rails 中建模无向图？

Question

导入图数据库语言，懂

1. 节点（由圆圈表示），
2. 边缘（由箭头表示），和
3. 属性（节点/边的元数据）

图形（由维基百科提供）描述了一个有向图。

在 Rails中建模无向图的最佳方法是什么？

也就是说，所有边都是互易的图（如上图），并且无论方向如何，每条边的属性都相同（与上图相反）。

让我们假设通过 ActiveRecord 使用 sql 存储的默认 Rails 3 设置。

双多态关联将创建一个有向图，能够对上图描述的数据进行建模。

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

应该扩展这个模型来管理反向关系，还是有更好的模型可用？

---

应用程序的一个元素可能是图问题，但这并不意味着应用程序以问题为中心，必须对数据执行图横向，也不意味着数据集大于可用内存。

Answer 1

在无向图中，您唯一需要知道的是一个节点是否连接到另一个节点。而且没有方向这样的东西。

简单的方法：

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

这也称为邻接列表：对于每个节点，我们可以轻松获得相邻（连接）节点的列表。

这种方法的一个可能问题是：我们将连接存储了两次。A连接到B，B连接到A。

因此，将每个连接仅存储一次似乎更好，然后我们会非常接近您的原始提案。

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

只有我们尽力不通过命名强加任何顺序或方向。

检索连接的节点是连接到 asnode1或 as的所有节点node2，因此有效地忽略了任何可能的方向。

在这种情况下，您还需要验证与 (node1, node2) 的连接是唯一的，但 (node2, node1) 实际上是相同的并且不能插入两次。

我个人的选择是使用第二个模式，尽管维护第一个解决方案可能会更快（另见这个问题）。

我还发现了一篇非常有趣的文章，作者解释了如何将图形存储在数据库中。非常深刻，但更以数据库为中心。

希望这可以帮助。

Answer 2

为什么不使用 Neo4J？

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

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

https://github.com/andreasronge/neo4j

Answer 3

不要使用多态关联，而是尝试使用 has_many, :through

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

您可以将边缘的属性存储在 Membership 模型中。