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

Question

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

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

你知道任何有助于实现这种图形的宝石或图书馆(对重新发明轮子不感兴趣;-))？

Answer 1

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

您可能需要实现自己的顶点,边ActiveRecord的支持模型(见vertex.rb和edge.rb在Rails安装的rails/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 <--- V2也不是由一个以上的有向边连接.)

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

1. 使用ActiveRecord关系(例如vertex1.edges.first.sink.edges......)在上述模型之上编写应用程序所需的最少量图形逻辑; 这将导致对数据库进行大量往返
2. 进口RGL; 选择从DB到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,但如果graph(Edge.find(:all))很大,可能会对数据库或内存造成压力- 此时您可能会想到进一步限制您实际需要的数据量,例如只关心red顶点的连接:

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