トップレベルのノードとその子のマップを作成する方法

Question

case class Node(id: Int, children: Set[Node]) 

val topLevel = Node(1, tlChildren) 
val topLevel2 = Node(2, tl2Children) 

val nodes = Set(topLevel1, topLevel2,..) 

topLevelのIDのマップを作成し、その値を子のすべてのIDのリストにしたいと考えています。

val map = Map[Int, List[Int]] = .. 

このマップでは、任意のIDを指定すると、トップレベルIDが何であるかを知ることができます。

上記のノードクラスとノード階層を指定してこのマップを生成するにはどうすればよいですか？

は、私はこのようなトップレベルのノードを取得することができます。

val topLevelNodeIds = nodes.map(n => n.id) 

しかし、私は、再帰呼び出しでそれを使用する必要があるので、それが役に立つかわかりません。

Answer 1

まず、再帰Nodeを横断し、すべてのIDを収集するための補助方法を定義します。ために

val topLevelNodeIds = nodes.map(n => n.id -> collectIds(n.children)).toMap 

Answer 2

：

def collectIds(nodes: Set[Node]): List[Int] = 
    nodes.map(_.id).toList ++ nodes.map(_.children).map(collectIds).flatten 

は今度は単に上記の方法の結果、各Nodeをマッピングすることができ我々はBFSアルゴリズムを使用する必要があります尾の再帰的な方法でそれを行う：

case class Node(id: Int, children: Set[Node]) 

val topLevel = Node(1, Set.empty) 
val topLevel2 = Node(2, Set.empty) 

val nodes = Set(topLevel, topLevel2) 

@tailrec 
def tailRecursiveSolution(buffer: List[Node], 
          visited: Set[Node] = Set.empty, 
          acc: Map[Int, List[Int]] = Map.empty): Map[Int, List[Int]] = 
    buffer match { 
    case top :: bottom if !visited.contains(top) => 
     val children = top.children 
     tailRecursiveSolution(
     children.toList ::: bottom, 
     visited + top, 
     acc + (top.id -> children.map(_.id).toList) 
    ) 
    case top :: bottom => 
     tailRecursiveSolution(bottom, visited, acc) 
    case Nil => acc 
    } 

各レベルでtailRecursiveSolutionを使用し、必要なマッピングが行われています。したがって、各レベルの結果を折りたたむだけです。

val result: Map[Int, List[Int]] = 
     nodes./:(Map.empty[Int, List[Int]]) { case (acc, root) => acC++ tailRecursiveSolution(List(root)) }