我需要在Ruby on Rails中实现无向图G =(V,E),并考虑构建一个具有Vertex has_many Edges的Vertex和Edge模型。

当一条边正好连接两个顶点时,您将如何在Rails中强制执行此操作?

您是否知道任何有助于实现这种图形的 gem 或库(不要迷失于重新发明轮子;-))?

最佳答案

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

您可能必须实现自己的,受Edge ActiveRecord支持的顶点模型(请参见Rails安装的vertex.rb目录中的edge.rbrails/activerecord/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
此时,您有两个选择,具体取决于图形的大小以及您希望在任何给定时间点遍历的图形数量:
  • 使用ActiveRecord关系(例如vertex1.edges.first.sink.edges ...)在上述模型之上编写应用程序所需的最少图形逻辑。这将导致对数据库
  • 进行大量往返
  • 导入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 ]
        )
    

    10-05 20:32
    查看更多