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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s