Как реализовать неориентированный граф в Ruby on Rails?

Question

Мне нужно реализовать неориентированный граф G = (V, E) в Ruby on Rails и подумать о создании модели Vertex и Edge , где Vertex has_many Edges .

Поскольку ребро соединяет ровно две вершины, как бы вы применили это в Rails?

Знаете ли вы какой-нибудь драгоценный камень или библиотеку, которая помогла бы реализовать такой граф (не заинтересованный в повторном изобретении колеса; -))?

Answer 1

Не известно ни о какой существующей библиотеке, которая предлагает графическую логику поверх ActiveRecord.

Возможно, вам придется реализовать свои собственные модели Vertex, Edge ActiveRecord (см. vertex.rb и edge.rb в каталоге rails/activerecord/test/fixtures вашей Rails-установки), например,

### 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 также не связаны более чем одним направленным ребром.) </p>

На данный момент у вас есть два варианта, в зависимости от того, насколько велик ваш график, и какую часть вы ожидаете пересечь в любой данный момент времени:

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, но это может привести к нагрузке на вашу базу данных или память, если график (Edge.find(:all)) большой - в этот момент вы можете подумать других способов ограничения объема данных, которые вам действительно нужны, например, заботятся только о red соединениях вершин:

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