# Untitled

By: a guest on Jun 17th, 2012  |  syntax: None  |  size: 2.17 KB  |  hits: 18  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. How to generate transitive closure of set of tuples?
2. //one transitive step
3. def addTransitive[A, B](s: Set[(A, B)]) = {
4.   s ++ (for ((x1, y1) <- s; (x2, y2) <- s if y1 == x2) yield (x1, y2))
5. }
6.
7. //repeat until we don't get a bigger set
8. def transitiveClosure[A,B](s:Set[(A,B)]):Set[(A,B)] = {
10.   if (t.size == s.size) s else transitiveClosure(t)
11. }
12.
13. println(transitiveClosure(Set((1,2), (2,3), (3,4))))
14.
15. def unfoldRight[A, B](seed: B)(f: B => Option[(A, B)]): List[A] = f(seed) match {
16.   case Some((a, b)) => a :: unfoldRight(b)(f)
17.   case None => Nil
18. }
19.
20. def unfoldLeft[A, B](seed: B)(f: B => Option[(B, A)]) = {
21.   def loop(seed: B)(ls: List[A]): List[A] = f(seed) match {
22.     case Some((b, a)) => loop(b)(a :: ls)
23.     case None => ls
24.   }
25.
26.   loop(seed)(Nil)
27. }
28.
29. def transitiveClosure(input: Set[(Int, Int)]) = {
30.     val map = input.toMap
31.     def closure(seed: Int) = unfoldLeft(map get seed) {
32.         case Some(`seed`) => None
33.         case Some(n)      => Some(seed -> n -> (map get n))
34.         case _            => None
35.     }
36.     map.keySet flatMap closure
37. }
38.
39. def closure(seed: Int) = unfoldRight(seed) {
40.     case n if map.get(n) != seed => map get n map (x => seed -> x -> x)
41.     case _ => None
42. }
43.
44. def closure(seed: Int) = unfoldRight(map get seed) {
45.         case Some(`seed`) => Some(seed -> seed -> None)
46.         case Some(n)      => Some(seed -> n -> (map get n))
47.         case _            => None
48.     }
49.
50. input.groupBy(_._1) mapValues ( _ map (_._2) )
51.
52. def transitiveClosure[T]( dag: Map[ T, List[T] ] ) = {
53.   var tc = Map.empty[ T, List[T] ]
54.   def getItemTC( item:T ): List[T] = tc.get(item) match {
55.     case None =>
56.       val itemTC = dag(item) flatMap ( x => x::getItemTC(x) )
57.       tc += ( item -> itemTC )
58.       itemTC
59.     case Some(itemTC) => itemTC
60.   }
61.   dag.keys foreach getItemTC
62.   tc
63. }
64.
65. scala> val a = List((1,2), (2,3), (3,4))
66. a: List[(Int, Int)] = List((1,2), (2,3), (3,4))
67.
68. scala> val (xx, yy) = a unzip
69. xx: List[Int] = List(1, 2, 3)
70. yy: List[Int] = List(2, 3, 4)
71.
72. scala> for(x <- xx; y <- yy if (x != y && x < y)) yield (x,y)
73. res32: List[(Int, Int)] = List((1,2), (1,3), (1,4), (2,3), (2,4), (3,4))