在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

只有我们尽最大努力不通过命名强加任何命令或方向.

检索所述连接的节点是所有连接到作为节点node1或作为node2,因此有效地忽略任何可能的方向.

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

我个人的选择是使用第二个模式,尽管保持第一个解决方案可能会更快(另请参阅此问题).

我还发现了一篇非常有趣的文章,作者解释了图表如何存储在数据库中.非常深刻,但更多的数据库为中心.

希望这可以帮助.