Моделировать неориентированный граф в Rails? - PullRequest
Новая
       14

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

19 голосов
/ 02 ноября 2011

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

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

Graph Database Property Graph

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

Какой лучший способ моделирования ненаправленного графа в 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

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

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

Ответы [ 3 ]

12 голосов
/ 12 ноября 2011

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

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

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

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

ВозможенПроблема с этим подходом: мы храним соединения дважды.A подключен к B, а B подключен к A.

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

class Connection
  belongs_to :node1, :class_name => 'Node'
  belongs_to :node2, :clasS_name => 'Node'
end

Только мы делаем все возможное, чтобы не навязывать какой-либо порядок или направление через именование.

Извлечение подключенных узлов - это все узлы, подключенные как node1 или как node2, следовательно, фактически игнорируя любое возможное направление.

В этом случае вам также необходимо выразить подтверждение того, что соединение с (узел1, узел2) уникально, но что (узел2, узел1) на самом деле то же самое и не может быть вставлено дважды.

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

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

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

3 голосов
/ 02 ноября 2011

Вместо использования полиморфных ассоциаций, попробуйте использовать 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

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

2 голосов
/ 07 ноября 2011
...