Come implementare il grafo non orientato in Ruby on Rails?

Question

Ho bisogno di attuare un grafo orientato G = (V, E) in Ruby on Rails e pensato di costruire un Vertex e un modello bordo dove Vertex has_many bordi.

Come un bordo collega esattamente due vertici, come si imporrebbe questo in Rails?

Conoscete qualche gemma o libreria che aiuterebbe l'implementazione di un tale grafico (non invano nel reinventare la ruota ;-))?

Answer 1

Non è a conoscenza di alcuna libreria esistente che offre la logica del grafico su ActiveRecord.

Potrebbe essere necessario implementare i propri modelli Vertex, Edge ActiveRecord con supporto (vedere vertex.rb e edge.rb nella directory rails/activerecord/test/fixtures dell'installazione di Rails), ad es.

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

Per rendere si comportano come sopra adirected grafico, pensare inserendo il bordo complementare così quando si inserisce un bordo. Si noti inoltre che l'uso di has_and_belongs_to_many è ora scoraggiato, è invece possibile utilizzare has_many :sources ... :through => :edges. Qualsiasi rafforzamento può essere eseguito tramite convalida (ovvero un vertice non ha un vantaggio) e/o vincoli di database (un vincolo/indice di unicità su [source_id,sink_id] in edges assicura che i vertici V1 ---> V2 non siano collegati da più di un V2 < --- V2 non sono collegati da più di un fronte diretto.)

A questo punto hai due opzioni, a seconda di quanto è grande il tuo grafico e di quanto ti aspetti da attraversare in qualsiasi punto nel tempo:

1. scrivere la quantità minima di logica grafico richiesto dall'applicazione sopra dei modelli descritti, utilizzando ActiveRecord relazioni fianchi (ad es. vertex1.edges.first.sink.edges ...); questo corrisponderà a in un numero significativo di viaggi andata e ritorno nel database
2. import RGL; seleziona tutti i vertici e i bordi dal DB in RGL e usa RGL per fare il traversal del grafico, ad es.

.

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) 

È possibile che abbatte il numero totale di istruzioni SQL (nelle operazioni di sola lettura) a 2, ma può mettere a dura prova il vostro database o memoria, se il grafico (Edge.find(:all)) è di grandi dimensioni - alla quale si punta può pensare a ulteriori modi per limitare la quantità di dati effettivamente necessari, ad es mi preoccupo solo delle connessioni dei vertici red:

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