ruby-on-rails - 如何在 Ruby on Rails 中实现无向图？

Question

我需要在 Ruby on Rails 中实现无向图 G = (V,E) 并考虑构建一个Vertex 和一个Edge 模型，其中Vertex有_多条边。

由于边恰好连接两个顶点，您将如何在 Rails 中执行此操作？

您是否知道任何有助于实现此类图表的 gem 或库(对重新发明轮子不感兴趣 ;-))？

Answer 1

不知道有任何现有库在 ActiveRecord 之上提供图形逻辑。

您可能必须实现自己的 Vertex、Edge ActiveRecord 支持的模型(请参阅 Rails 安装的 rails/activerecord 中的 vertex.rb 和 edge.rb/test/fixtures 目录)，例如

### 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

要使上面的图表现得像有向图，请考虑在插入边时也插入互补边。另请注意，现在不鼓励使用 has_and_belongs_to_many，您可以改用 has_many :sources ... :through => :edges。任何强制执行都可以通过验证(即顶点本身没有边)和/或数据库约束([source_id,sink_id] 中的唯一性约束/索引在 edges 确保顶点 V1 ---> V2 不由多条有向边连接，并且顶点 V1 <--- V2 也不由多条有向边连接。)

此时您有两个选择，具体取决于您的图表有多大以及您希望在任何给定时间点遍历的图表数量:

1. 使用 ActiveRecord 关系(例如 vertex1.edges.first.sink.edges)，在上述模型之上编写您的应用程序所需的最少量图形逻辑。 ..);这将导致对数据库进行大量往返
2. 导入RGL；从数据库中选择所有顶点和边到RGL中，并使用RGL进行图遍历，例如

.

    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)

以上将您的 SQL 语句总数(在只读操作中)减少到 2，但如果图形 (Edge.find(:all) ) 很大——此时您可能会想到进一步的方法来限制您实际需要的数据量，例如只关心 red 顶点的连接:

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