Monthly Archives: September 2015

Random graph

Random graph, from playing around with RGL in Ruby.
Random graph

Tagged ,

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

Say you have a graph like this:

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
end
t = g.bfs_search_tree_from("one")
puts t.has_vertex?("two") # true
puts t.has_vertex?("three") # false

view raw
graph.rb
hosted with ❤ by GitHub

Tagged , ,