Моделировать неориентированный граф в Rails?

Импортировать язык графические базы данных, понять

узлы (представлены кружками),
ребра (представлены стрелками) и
свойства (метаданные узлов/ребер)

Графика (любезно предоставлена википедией) описывает ориентированный график.

Какой лучший способ смоделировать неориентированный график в Rails?

То есть, график, где все ребра являются взаимными (как в приведенном выше графике), и где свойства каждого ребра одинаковы независимо от направления (в отличие от выше графика).

Предположим, что установка Rails 3 по умолчанию используется с помощью хранилища sql через ActiveRecord.

Двойная полиморфная ассоциация создаст ориентированный граф, способный моделировать данные, описанные выше.

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

Следует ли расширить эту модель для управления обратными связями или доступной лучшей модели?

Один элемент приложения может представлять собой проблему с графом, но это не значит, что приложение сосредоточено вокруг проблемы, что трансверсалы графа должны выполняться на данных или что набор данных больше доступной памяти.

Ответ 1

В ненаправленном графе, единственное, что вам нужно знать, - это то, связано ли node с другим node. И нет такой вещи, как направление.

Простой подход:

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

Это также называется списком смежности: для каждого node мы можем легко получить список смежных (связанных) узлов.

Возможная проблема с этим подходом: мы сохраняем соединения дважды. 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) на самом деле то же самое и не может быть вставлено дважды.

Моим личным выбором было бы использовать вторую схему, хотя сохранение первого решения может быть более быстрым (см. также question).

Я также нашел очень интересную статью где автор объясняет, как графы могут храниться в базе данных. Очень глубокий, но более ориентированный на базу данных.

Надеюсь, что это поможет.

Ответ 2

Вместо использования полиморфных ассоциаций попробуйте использовать has_many,: через

class Group < ActiveRecord::Base
  has_many :memberships
  has_many :persons, :through => :memberships
end

class Membership < ActiveRecord::Base
  belongs_to :group
  belongs_to :person
end

class Person < ActiveRecord::Base
  has_many :memberships
  has_many :groups, :through => :memberships
end

Вы можете сохранить свойства ребра int в модели Membership.

Ответ 3

Почему бы не использовать Neo4J?

http://wiki.neo4j.org/content/Ruby

https://github.com/andreasronge/neo4j-rails-example

https://github.com/andreasronge/neo4j