Find unconnected nodes of a graph

Question

It is a set of edges of a graph given. An edge is given as an array of its endpoints, e.g. [:a, :b]. The array can contain an arbitrary amount of endpoints. Therefore [] and [:b, :c, :d] are also valid edges.

I want to find all islands which means that I looking for unconnected sets of nodes. Here is my Ruby solution.

e = [[:a, :b],[:c, :d],[:b, :c, :e], [:f, :g]]
n = e.flatten.uniq
def islands(edges)
 edges.reduce([]) do |islands, edge|
 matches = islands.select { |island| island.any? { |node| edge.include?(node) } }
 if !matches.empty?
 island = matches.shift
 islands.delete_if { |i| matches.include?(i) }
 island.concat(matches.flatten)
 island.concat(edge)
 island.uniq!
 else
 islands << edge
 end
 islands
 end
end
puts islands(e).inspect
# => [[:a, :b, :c, :d, :e], [:f, :g]]

Is there room for improvement?

• sschmeck: Found a similar question for C#
• tokland: I am too lazy to write an answer, but with a quick-union algorithm it would be much, much faster. cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

Answer 1

if !matches.empty? 

equals

if matches.any?

And the second is preferable, cause you don't have negation.

• Nakilon: [nil].empty? == [nil].any?