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.

Answer 2

With the help of unfold,

def unfoldRight[A, B](seed: B)(f: B => Option[(A, B)]): List[A] = f(seed) match {
  case Some((a, b)) => a :: unfoldRight(b)(f)
  case None => Nil
}

def unfoldLeft[A, B](seed: B)(f: B => Option[(B, A)]) = {
  def loop(seed: B)(ls: List[A]): List[A] = f(seed) match {
    case Some((b, a)) => loop(b)(a :: ls)
    case None => ls
  }

  loop(seed)(Nil)
}

it becomes rather simple:

def transitiveClosure(input: Set[(Int, Int)]) = {
    val map = input.toMap
    def closure(seed: Int) = unfoldLeft(map get seed) {
        case Some(`seed`) => None
        case Some(n)      => Some(seed -> n -> (map get n))
        case _            => None
    }
    map.keySet flatMap closure
}

Another way of writing closure is this:

def closure(seed: Int) = unfoldRight(seed) {
    case n if map.get(n) != seed => map get n map (x => seed -> x -> x)
    case _ => None
}

I'm not sure which way I like best, myself. I like the elegance of testing for Some(seed) to avoid loops, but, by the same token, I also like the elegance of mapping the result of map get n.

Neither version returns seed -> seed for loops, so you'll have to add that if needed. Here:

    def closure(seed: Int) = unfoldRight(map get seed) {
        case Some(`seed`) => Some(seed -> seed -> None)
        case Some(n)      => Some(seed -> n -> (map get n))
        case _            => None
    }

Answer 3

Model the problem as a directed graph as follows:

Represent the numbers in the tuples as vertices in a graph. Then each tuple (x, y) represents a directed edge from x to y. After that, use Warshall's Algorithm to find the transitive closure of the graph.

For the resulting graph, each directed edge is then converted to an (x, y) tuple. That is the transitive closure of the set of tuples.