如何在Scala中通过DAG列出路径

Question

我有一个DAG的单词类型如下：HashMap[String, Set[String]]。我想通过图表建立一个所有路径的集合。但我编写的方法完全不像我所期望的那样：

def buildChain(wordGraph: HashMap[String, Set[String]], path: ListBuffer[String], accumChains: ListBuffer[ListBuffer[String]]): ListBuffer[ListBuffer[String]] = {
  val children = wordGraph(path.last)

  for (word <- children) {
    path += word
    if (wordGraph.keySet.contains(word)) buildChain(wordGraph, path, accumChains)
    else accumChains += path
  } 

  return accumChains
}

当我传入这张图时：

Map("chow" -> Set("how", "cho", "cow"), "how" -> Set("ho", "ow"), "cho" -> Set("ho"), "cow" -> Set("ow"))

我希望得到：

ListBuffer(ListBuffer("chow", "how", "ho"), ListBuffer("chow", "how", "ow"), ListBuffer("chow", "cho", "ho"), ListBuffer("chow", "cow", "ow"))

当我从“周”开始的时候。

相反，我得到了这个：

ListBuffer(ListBuffer(chow, how, ho, ow, cho, ho, cow, ow), ListBuffer(chow, how, ho, ow, cho, ho, cow, ow), ListBuffer(chow, how, ho, ow, cho, ho, cow, ow), ListBuffer(chow, how, ho, ow, cho, ho, cow, ow))

我也搞不懂为什么。我肯定这很简单，但我现在只是错过了。

Answer 1

下面是一个简单的解决方案，我对param类型做了一些修改，因为我认为不可变类型足够好：

def _buildChain(wordGraph: Map[String, Set[String]], path: String): List[List[String]] = { 
  wordGraph.get(path) match {
    case Some(w) =>  w.toList.flatMap(_buildChain(wordGraph, _).map(path :: _)) 
    case None =>  List(List(path))
  }
}

def buildChain(wordGraph: Map[String, Set[String]], path: List[String]): List[List[String]] = path.flatMap(_buildChain(wordGraph, _)) 


val a = _buildChain( Map("chow" -> Set("how", "cho", "cow"), "how" -> Set("ho", "ow"), "cho" -> Set("ho"), "cow" -> Set("ow")), "chow")
println(a)
val b = buildChain( Map("chow" -> Set("how", "cho", "cow"), "how" -> Set("ho", "ow"), "cho" -> Set("ho"), "cow" -> Set("ow")), List("chow", "how"))
println(b)

产出如下：

List(List(chow, how, ho), List(chow, how, ow), List(chow, cho, ho), List(chow, cow, ow))


List(List(chow, how, ho), List(chow, how, ow), List(chow, cho, ho), List(chow, cow, ow), List(how, ho), List(how, ow))

Answer 2

当您为path += word中的每个word执行行children时，您将附加到同一个缓冲区，因此缓冲区只会增长到容纳所有的子缓冲区(然后将同一个缓冲区多次添加到accumChains中)。您希望为每个单词生成一个新的序列。我可以建议在这里使用不可变的列表吗？