ruby on rails - ¿Modelar un gráfico no dirigido en Rails?

ruby-on-rails activerecord

Question

Importando el lenguaje de bases de datos de grafos , entendemos

1. nodos ( representados por círculos ),
2. bordes ( representados por flechas ), y
3. propiedades ( metadatos de nodos / bordes )

El gráfico (cortesía de wikipedia) describe un gráfico dirigido .

¿Cuál es la mejor manera de modelar un gráfico no dirigido en Rails?

Es decir, un gráfico donde todos los bordes son recíprocos ( como en el gráfico anterior ), y donde las propiedades de cada borde son las mismas independientemente de la dirección (al contrario del gráfico anterior ).

Asumamos una configuración predeterminada de Rails 3 utilizando una tienda SQL a través de ActiveRecord.

Una doble asociación polimórfica crearía un gráfico dirigido, capaz de modelar los datos descritos por la imagen anterior.

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

¿Se debería ampliar este modelo para administrar relaciones inversas, o hay un mejor modelo disponible?

Un elemento de una aplicación puede ser un problema gráfico, pero no significa que la aplicación esté centrada alrededor del problema, que los gráficos transversales se deben realizar en los datos, ni que el conjunto de datos sea más grande que la memoria disponible.

Answer 1

¿Por qué no usar Neo4J?

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

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

https://github.com/andreasronge/neo4j

Answer 2

En lugar de usar asociaciones polimórficas, intente usar has_many,: through

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

Puede almacenar las propiedades del borde en el modelo Membership.

Answer 3

En un gráfico no dirigido, lo único que debe saber es si un nodo está conectado a otro nodo. Y no hay tal cosa como una dirección.

Enfoque simple:

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

Esto también se conoce como lista de adyacencia: para cada nodo podemos obtener fácilmente la lista de nodos adyacentes (conectados).

Un posible problema con este enfoque: almacenamos las conexiones dos veces. A está conectado a B y B está conectado a A.

Por lo tanto, parece mejor normalizar el almacenamiento de cada conexión solo una vez, y luego nos acercamos mucho a su propuesta original.

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

Solo hacemos nuestro mejor esfuerzo para no imponer ningún orden o dirección a través de la denominación.

Recuperar los nodos conectados es a todos los nodos conectados como node1 o como node2 , por lo tanto, sin tener en cuenta cualquier dirección posible.

En este caso, también necesita expresar una validación de que una conexión con (node1, node2) es única, pero que (node2, node1) es en realidad la misma y no se puede insertar dos veces.

Mi elección personal sería utilizar el segundo esquema, aunque mantener la primera solución podría ser más rápido (vea también esta question ).

También encontré un article muy interesante en el que el autor explica cómo se pueden almacenar los gráficos en la base de datos. Muy profundo, pero más centrado en la base de datos.

Espero que esto ayude.