ruby on rails - ¿Modelar un gráfico no dirigido en Rails?
ruby-on-rails activerecord (3)
¿Por qué no usar Neo4J?
http://wiki.neo4j.org/content/Ruby
Importando el lenguaje de bases de datos de grafos , entendemos
- nodos ( representados por círculos ),
- bordes ( representados por flechas ), y
- 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.
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.
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.