Will Jessop's Writings

Sailing, Food, Programming, Technology, and other things

Do you have a Ruby on Rails application you'd like to be faster, more scalable, or just upgraded safely? I'm currently open to new contracts doing Ruby on Rails and Postgres scaling and performance work, and Rails upgrades. Contact me at will@willj.net to get started.
| tags:programming ruby tech

How to find if two nodes are connected in an RGL graph

Say you have a graph like this:

a simple graph

A simple graph

How do you find out if there is a path between any of the two nodes? By using a breadth-first search:

require 'rgl/implicit'
require 'rgl/traversal'

vertices = ["one", "two", "three"]

g = RGL::ImplicitGraph.new do |g|
  g.vertex_iterator { |b| vertices.map{|v| b.call(v) } }
  g.adjacent_iterator { |x, b| b.call( vertices[(vertices.index(x) - 1).abs] ) }
  g.directed = true

t = g.bfs_search_tree_from("one")

puts t.has_vertex?("two")   # true
puts t.has_vertex?("three") # false