How to generate transitive closure of set of tuples?

Question

What is the best way to generate transitive closure of a set of tuples?

Example:

• Input Set((1, 2), (2, 3), (3, 4), (5, 0))
• Output Set((1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (5, 0))

Answer 1

//one transitive step
def addTransitive[A, B](s: Set[(A, B)]) = {
  s ++ (for ((x1, y1) <- s; (x2, y2) <- s if y1 == x2) yield (x1, y2))
}

//repeat until we don't get a bigger set
def transitiveClosure[A,B](s:Set[(A,B)]):Set[(A,B)] = {
  val t = addTransitive(s)
  if (t.size == s.size) s else transitiveClosure(t)
}

println(transitiveClosure(Set((1,2), (2,3), (3,4))))

This is not a very efficient implementation, but it is simple.