Jak zaimplementować nieukierunkowany wykres w Ruby on Rails?

Question

trzeba zaimplementować nieukierunkowane wykres G = (V, E) w Ruby na szynach myśl budowy wierzchołek oraz krawędzi model, w którym wierzchołek has_many kanty.

Jako że krawędź łączy dokładnie dwa wierzchołki, w jaki sposób można to wymusić w Railsach?

Czy znasz jakiś klejnot lub bibliotekę, która pomogłaby w implementacji takiego wykresu (niezainteresowanego ponownym wynalezieniem koła ;-))?

Answer 1

Brak wiedzy o istniejącej bibliotece, która oferuje logikę wykresu na szczycie ActiveRecord.

Być może trzeba będzie wdrożyć własne modele Vertex, Edge ActiveRecord-baseded (zobacz vertex.rb i edge.rb w katalogu instalacji Rails rails/activerecord/test/fixtures), np.

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

Aby zachowywać wyżej jako adirected wykres, że wkładanie komplementarną krawędzi oraz po włożeniu krawędzi. Zauważ też, że korzystanie z has_and_belongs_to_many jest odradzane, możesz zamiast tego użyć has_many :sources ... :through => :edges. Dowolne wymuszenia mogą być wykonywane przez walidację (tj. Wierzchołek nie ma krawędzi do siebie) i/lub ograniczenia bazy danych (jednoograniczenie/indeks na wartości [source_id,sink_id] w edges zapewnia, że ​​wierzchołki V1 ---> V2 nie są połączone przez więcej niż jeden skierowana krawędź i wierzchołki V1 < --- V2 nie są połączone przez więcej niż jedną skierowaną krawędź).

W tym momencie masz dwie opcje, w zależności od tego, jak duży jest twój wykres i ile z tego chcesz być przejeżdżające w danym momencie:

1. napisać minimalną ilość logiki wykresu wymaganej przez aplikację na szczycie powyższych modeli, używając ActiveRecord stosunków biodra (np. vertex1.edges.first.sink.edges ...); to spowoduje, że spowoduje znaczącą liczbę podróży w obie strony do bazy danych
2. import RGL; wybierz wszystkie wierzchołki i krawędzie z DB do RGL i użyj RGL do przechodzenia między wykresami, np.

.

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) 

Powyższy obniża łączną liczbę zapytań SQL (w operacji tylko do odczytu) do 2, ale może obciążać swojej bazie danych lub pamięci, jeśli wykres (Edge.find(:all)) jest duża - w którym momencie ci może myśleć o dalszych sposobach ograniczania ilości danych, których faktycznie potrzebujesz, np tylko dbałość o połączenia wierzchołków: red:

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