Ruby on Railsで無向グラフを実装する方法は？

Question

Iレールと頂点と頂点にhas_manyは縁エッジモデルを構築するの思想にRubyで無向グラフG =（V、E）を実装する必要があります。

エッジがちょうど2つの頂点に接続するので、これをRailsでどのように強制しますか？

このようなグラフの実装に役立つ宝石や図書館を知っていますか（車輪を再発明する際には心配していません;-)）？

Answer 1

ActiveRecordの上にグラフロジックを提供する既存のライブラリは認識していません。

独自のVertex、Edge ActiveRecord対応モデルを実装する必要があるかもしれません（Railsインストールのrails/activerecord/test/fixturesディレクトリにvertex.rbとedge.rbを参照してください）。

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

がグラフをadirected上記のように挙動をするためには、エッジを挿入する際にも相補エッジを挿入すると考えます。また、has_and_belongs_to_manyの使用は推奨されません。代わりにhas_many :sources ... :through => :edgesを使用することができます。任意の執行は、検証（つまり、頂点にはエッジがない）やデータベースの制約（[source_id,sink_id]のedgesのユニティシティ制約/インデックスは、頂点V1 ---> V2が複数で接続されないことを保証します有向辺と頂点V1 < --- V2は、複数の有向辺で接続されていません。

この時点では、グラフの大きさと期待する範囲によって2つの選択肢があります任意の時点で横断する：

1. はActiveRecord関係を使用して、上記のモデルの上に、あなたのアプリケーションで必要とされるグラフ・ロジックの最小限の量を書きます股関節vertex1.edges.first.sink.edges ...）;このはとなり、データベースへの往復の回数はかなり多くなります。
2. インポートRGL; DBからRGLへの頂点および辺のすべてを選択し、RGLを使用してグラフの横断を行う。

。あなたのその時点で - 上記2に（読み取り専用操作で）SQL文のあなたの総数をダウンさせますが、グラフ（Edge.find(:all)）が大きい場合は、データベースまたはメモリに負担をかけること

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) 

あなたが実際に必要とするデータの量を制限するさらなる方法を考えるかもしれません。 red頂点の接続のみに注意してください：

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