Ruby on Rails에서 무향 그래프를 구현하는 방법은 무엇입니까?

Question

은 내가 무향 그래프 G 루비 온 레일즈 = (V, E)과 정점 및 정점 has_many가 엣지 에지 모델을 구축하는 생각을 구현해야합니다.

에지가 정확하게 두 개의 꼭지점을 연결하기 때문에 레일스에서 ​​이것을 어떻게 적용합니까?

그래프를 구현하는 데 도움이되는 보석이나 라이브러리를 알고 계십니까? (휠을 다시 발명하는 데 intrested가 아닙니다 ;-))?

Answer 1

ActiveRecord 위에 그래프 논리를 제공하는 기존 라이브러리를 알지 못합니다.

Vertex, Edge ActiveRecord 지원 모델을 구현해야 할 수도 있습니다 (레일 설치의 rails/activerecord/test/fixtures 디렉토리에 vertex.rb 및 edge.rb 참조). 는 에지를 삽입 할 때뿐만 아니라 상보 에지 삽입 생각 그래프로 adirected

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

위없이 행동을한다. 또한 has_and_belongs_to_many의 사용을 권장하지 않으므로 대신 has_many :sources ... :through => :edges을 사용할 수 있습니다. 모든 시행은 유효성 검사 (즉, 정점 자체에 가장자리가 없음) 및/또는 데이터베이스 제약 조건 ( [source_id,sink_id]의 edges에있는 단일성 제약/색인은 정점 V1 ---> V2가 둘 이상으로 연결되지 않도록합니다 직사각형 및 정점 V1 < --- V2는 둘 이상의 지향 에지로 연결되지 않습니다.)

이 시점에서 그래프의 크기와 예상되는 양에 따라 두 가지 옵션이 있습니다. ActiveRecord 관계를 이용하여,

1. 위 모델의 상단에 귀하의 응용 프로그램에 필요한 그래프 논리의 최소한의 쓰기 시간에 주어진 시점에서 통과 될 엉덩이 (예. vertex1.edges.first.sink.edges ...); 이 은 일 때 데이터베이스 왕복 횟수가 많습니다.
2. 수입자는 RGL입니다. DB에서 RGL 로의 모든 꼭지점과 모서리를 선택하고 RGL을 사용하여 그래프 순회를 수행합니다.

.

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) 

는 위의 2 (읽기 전용 작업)에 SQL 문의 총 번호를 제공하지만, 그래프 (Edge.find(:all))가 큰 경우 데이터베이스 나 메모리에 부담을 줄 수 있습니다 - 어떤에서 당신을 가리 킵니다 실제로 필요한 데이터의 양을 제한하는 추가 방법을 생각할 수 있습니다. red 정점의 연결에만주의하십시오 :

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