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.

Answer 4

Assuming that what you have is a DAG (there are no cycles in your example data), you could use the code below. It expects the DAG as a Map from T to List[T], which you could get from your input using

input.groupBy(_._1) mapValues ( _ map (_._2) )

Here's the transitive closure:

def transitiveClosure[T]( dag: Map[ T, List[T] ] ) = {
  var tc = Map.empty[ T, List[T] ]
  def getItemTC( item:T ): List[T] = tc.get(item) match {
    case None =>
      val itemTC = dag(item) flatMap ( x => x::getItemTC(x) )
      tc += ( item -> itemTC )
      itemTC
    case Some(itemTC) => itemTC
  }
  dag.keys foreach getItemTC
  tc
}

This code figures out the closure for each element just once. However:

• This code can cause a stack overflow if there are long enough paths through the DAG (the recursion is not tail recursion).
• For a large graph, you would probably be better off making tc a mutable Map and then converting it at the end if you wanted an immutable Map.
• If your elements were really small integers as in your example, you could improve performance significantly by using Arrays rather than Maps, although doing so would complicate some things.

To eliminate the stack overflow problem (for DAGs), you could do a topological sort, reverse it, and process the items in order. But see also this page:

best known transitive closure algorithm for graph