Comment implémenter un graphe non orienté dans Ruby on Rails?

Question

J'ai besoin de mettre en œuvre un graphe non orienté G = (V, E) en Ruby on Rails et de la pensée de la construction d'un Vertex et un bord modèle où Vertex has_many Edges.

Comme une arête connecte exactement deux sommets, comment appliqueriez-vous cela dans Rails? Connaissez-vous une gemme ou une bibliothèque qui aiderait à mettre en œuvre un tel graphique (pas intéressé à réinventer la roue ;-))?

Answer 1

Aucune bibliothèque existante n'offre la logique graphique en plus de ActiveRecord.

Vous devrez peut-être implémenter vos propres modèles à support Vertex, Edge ActiveRecord (voir vertex.rb et edge.rb dans le répertoire rails/activerecord/test/fixtures de votre installation Rails), par exemple.

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

Pour rendre le comportent de manière plus comme un adirected graphique, pensez à insérer le bord complémentaire et lors de l'insertion d'un bord. Notez également que l'utilisation de has_and_belongs_to_many est maintenant déconseillée, vous pouvez utiliser has_many :sources ... :through => :edges à la place. Toute contrainte peut être effectuée via la validation (ie un sommet ne possède pas de bord) et/ou les contraintes de base de données (une contrainte/index unicité sur [source_id,sink_id] en edges garantit que les sommets V1 ---> V2 ne sont pas connectés par plus d'un bord dirigé, et sommets V1 < --- V2 ne sont pas connectés par plus d'un seul côté dirigé non plus.)

À ce stade, vous avez deux options, en fonction de la taille de votre graphique et de la taille de celui-ci. être traversée à un moment donné dans le temps:

1. écrire la quantité minimale de la logique graphique requise par votre application sur des modèles ci-dessus, en utilisant ActiveRecord relations les hanches (par ex. vertex1.edges.first.sink.edges ...); ce entraînera un nombre important d'allers-retours à la base de données
2. import RGL; sélectionnez tous les sommets et arêtes de la base de données dans RGL, et utilisez RGL pour effectuer la traversée de graphe, par ex.

.

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) 

Le positionne au-dessus votre nombre total d'instructions SQL (dans les opérations en lecture seule) à 2, mais peut mettre la pression sur votre base de données ou de la mémoire si le graphe (Edge.find(:all)) est grande - à laquelle vous pointez penser à d'autres moyens de limiter la quantité de données dont vous avez réellement besoin, par exemple se soucient seulement de red connexions des vertices:

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