Find unconnected nodes of a graph

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?

if !matches.empty?


equals

if matches.any?


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

• I will apply any?, thanks. Aug 5, 2015 at 13:38
• [nil].empty? == [nil].any? Aug 6, 2015 at 20:03