¿Cómo implementar un gráfico no dirigido en Ruby on Rails?

Question

I necesidad de implementar un grafo no dirigido G = (V, E) en rubí en los carriles y el pensamiento de la construcción de una Vertex y un modelo de Edge donde Vertex has_many Bordes.

Como un borde conecta exactamente dos vértices, ¿cómo harías esto en Rails?

¿Conoces alguna joya o biblioteca que ayude a implementar un gráfico como este (no se interesa en reinventar la rueda ;-))?

Answer 1

No tiene conocimiento de ninguna biblioteca existente que ofrezca la lógica de gráficos sobre ActiveRecord.

Puede que tenga que poner en práctica sus propios modelos Vertex, respaldado por ActiveRecord Edge (véase vertex.rb y edge.rb en el directorio de instalación de rieles su rails/activerecord/test/fixtures), por ejemplo,

### 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 

Para hacer el comportan anteriormente como adirected gráfico, piense de insertar el borde complementario, así cuando se inserta un borde. También tenga en cuenta que ahora se desaconseja el uso de has_and_belongs_to_many, puede usar has_many :sources ... :through => :edges en su lugar. Cualquier aplicación se puede hacer a través de validación (es decir, un vértice no tiene un borde) y/o restricciones de base de datos (una restricción de unidad/índice en [source_id,sink_id] en edges asegura que los vértices V1 ---> V2 no están conectados por más de uno borde dirigido, y vértices V1 < --- V2 no están conectados por más de un borde dirigido tampoco.)

En este punto tiene dos opciones, dependiendo de qué tan grande es su gráfico y cuánto de eso espera se atraviesa en cualquier punto dado en el tiempo:

1. escribir la cantidad mínima de lógica gráfico requerido por su aplicación en la parte superior de los modelos anteriores, usando ActiveRecord relaciones caderas (p. vertex1.edges.first.sink.edges ...); dará como resultado resultado en un número significativo de viajes de ida y vuelta realizados a la base de datos
2. importación RGL; seleccione todos los vértices y bordes de la base de datos en RGL, y use RGL para hacer un recorrido de gráfico, p.

.

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) 

Lo anterior hace que caiga el número total de sentencias SQL (en las operaciones de sólo lectura) a 2, pero puede poner la tensión en su base de datos o la memoria si el gráfico (Edge.find(:all)) es grande - en el que el punto puede pensar en otras formas de limitar la cantidad de datos que realmente necesita, por ej. sólo se preocupan por las conexiones de los vértices de red:

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