使用 FoldLeft 在 Scala 中创建邻接表

Question

给定这个函数

  def makeAdjacencyList(edgeList: Seq[(String, String)]): Map[String, Seq[String]] = {
    val emptyMap = Map[String, Seq[String]]().withDefaultValue(Seq[String]())

    edgeList.foldLeft(emptyMap) {
      case (acc, curr) => {
        acc + (curr._1 -> (acc(curr._1) :+ curr._2))
        acc + (curr._2 -> (acc(curr._2) :+ curr._1))
      }
    }
  }

它接受一个无向图的edgeList，例如：

Vector((S1,E1), (S1,D1), (S2,E2), (S2,D1), (S3,E1), (S3,D2))

但是该函数给出的输出为

[E1 -> [S1, S3], D1 -> [S1, S2], E2 -> [S2], D2 -> [S3]]

但我期待

的输出

[S1 -> [E1, D1], S2 -> [E2, D1], S3 -> [E1], E1 -> [S1, S3], D1 -> [S1, S2], E2 -> [S2], D2 -> [S3]]

foldLeft (acc + (curr._1 -> (acc(curr._1) :+ curr._2))) 的第一行似乎被忽略了，我不太清楚为什么。

Answer 1

case 块中的两行代码都产生一个结果，但只返回第二个结果并成为下一个 acc 值。

这会解决问题。

edgeList.foldLeft(emptyMap) {
  case (acc, curr) =>
    acc + (curr._1 -> (acc(curr._1) :+ curr._2)) +
          (curr._2 -> (acc(curr._2) :+ curr._1))
}

另一方面，这是实现所需输出的不同方法。

def makeAdjacencyList(edgeList: Seq[(String,String)]): Map[String,Seq[String]] =
  edgeList.flatMap(edge => Seq(edge, edge.swap))
          .groupMap(_._1)(_._2)

使用 FoldLeft 在 Scala 中创建邻接表

Making Adjacency List in Scala with FoldLeft

scala

graph

immutability

scala-collections