1
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$
if !matches.empty? 

equals

if matches.any?

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

\$\endgroup\$
  • \$\begingroup\$ I will apply any?, thanks. \$\endgroup\$ – sschmeck Aug 5 '15 at 13:38
  • \$\begingroup\$ [nil].empty? == [nil].any? \$\endgroup\$ – Nakilon Aug 6 '15 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.