Random graph, from playing around with RGL in Ruby.
Will writes
It's all good
Tag Archives: graphs
How to find if two nodes are connected in an RGL graph
Say you have a graph like this:
How do you find out if there is a path between any of the two nodes? By using a breadth-first search:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 |
Will writes 