如何生成元组集的传递闭包？

Question

如何生成一组元组的传递闭包是最佳方法？

例子:

• 输入 Set((1, 2), (2, 3), (3, 4), (5, 0))
• 输出 Set((1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (5, 0))

- aioobe

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))))

这不是一个非常高效的实现，但它很简单。

- Kim Stebel

Answer 2

通过 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)
}

这变得相当简单：

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
}

闭包的另一种写法如下：

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

我不确定自己更喜欢哪种方式。我喜欢使用Some(seed)进行测试以避免循环的优雅，但是同样地，我也喜欢将map get n的结果映射。

两个版本都不会返回seed -> seed以用于循环，因此如果需要，您必须添加它。这里：

    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
    }

- Daniel C. Sobral

---

你不能使用input.toMap，因为输入不一定代表一个函数（尽管给出的示例是这样的）- 它代表一个关系。toMap会丢弃给定的数据((1,1), (1,2))。 - Robin Green

Answer 3

将问题建模为有向图，如下所示：

将元组中的数字表示为图中的顶点。然后，每个元组（x，y）表示从x到y的有向边。之后，使用 Warshall算法 找到图的传递闭包。

对于结果图，每个有向边都转换为一个（x，y）元组。这就是元组集合的传递闭包。

- yanhan

---

非常抱歉，我没有注意到这是标记在Scala下的。请原谅。 - yanhan

Answer 4

假设你手头有一张DAG（在你的数据示例中没有循环），你可以使用下面的代码。它期望将DAG作为从T到List[T]的Map，你可以使用输入获取它。

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

这是传递闭包：

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
}

这段代码只为每个元素计算一次闭包。但是：

• 如果DAG中存在足够长的路径（递归不是尾递归），则此代码可能会导致堆栈溢出。
• 对于大型图形，最好将tc设置为可变Map，然后在需要不可变Map时再进行转换。
• 如果您的元素像示例中那样非常小，则可以通过使用数组而不是Map来显著提高性能，尽管这样做会使某些事情变得复杂。

为了消除DAG的堆栈溢出问题，您可以进行拓扑排序，然后反转它，并按顺序处理项目。但请参见此页面：

用于图形的已知最佳传递闭包算法

- AmigoNico