How to implement undirected graph in Ruby on Rails?

Question

I need to implement a undirected graph G = (V,E) in Ruby on Rails and thought of building a Vertex and an Edge model where *Vertex has_many Edges*.

As an edge connects exactly two vertices, how would you enforce this in Rails?

Do you know any gem or library that would help implementing such a graph (not intrested in re-inventing the wheel ;-))?

Answer 1

The RGL might help.

Answer 2

Not aware of any existing library that offers the graph logic on top of ActiveRecord.

You may have to implement your own Vertex, Edge ActiveRecord-backed models (see vertex.rb and edge.rb in your Rails installation's rails/activerecord/test/fixtures directory), e.g.

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

To make the above behave as an adirected graph, think of inserting the complementary edge as well when inserting an edge. Also note that the use of has_and_belongs_to_many is now discouraged, you may use has_many :sources ... :through => :edges instead. Any enforcements can be done through validation (i.e. a vertex does not have an edge to itself) and/or database constraints (a unicity constraint/index on [source_id,sink_id] in edges ensures that vertices V1 ---> V2 are not connected by more than one directed edge, and vertices V1 <--- V2 are not connected by more than one directed edge either.)

At this point you have two options, depending on how big your graph is and how much of it you expect to be traversing at any given point in time:

1. write the minimal amount of graph logic required by your application on top of the above models, using ActiveRecord relationships (e.g. vertex1.edges.first.sink.edges ...); this will result in a significant number of round trips made to the database
2. import RGL; select all vertices and edges from the DB into RGL, and use RGL to do graph traversal, e.g.

.

    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)

The above brings down your total number of SQL statements (in read-only operations) to 2, but may put strain on your database or memory if the graph (Edge.find(:all)) is large -- at which point you may think of further ways of limiting the amount of data you actually require, e.g. only care about red vertices' connections:

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

Cheers, V.