Scala 中不可变的类图结构

Question

再会！我正在尝试在 Scala 2.9.1 中构建不可变图。它是给我的Seq[BO]，其中BO可以代表图中的一个节点，而BO.attr_bo: Seq[String]who 代表其他节点的边，由字符串名称给出。我需要构建“已解析”图，由BO with ResolvedBO 您可以在此处看到可能的实现：

trait BO {
  def name: String
  def attr_bo: Seq[String]
}

trait ResolvedBO {
  x: BO =>
  val uni: Universe
  lazy val r_attr_bo: Seq[BO with ResolvedBO] = attr_bo map (uni.m_list_r(_))
}

class S_BO(val name: String, val attr_bo: Seq[String]) extends BO

class Universe(list: Seq[BO]) {
  val m_list: Map[String, BO] = list.map(x => (x.name, x))(collection.breakOut)
  val m_list_r: Map[String, BO with ResolvedBO] = ...???
}

val x: Uni = new Uni(Seq(new S_BO("a", Seq("b", "c")), new S_BO("b", Seq("a", "c")), new S_BO("c", Seq("a", "b"))))

其中class Universe代表图形（它也可以断开连接）另外，如果很重要，我可以将图形限制为没有循环。

所以我的主要问题是：

1. 由于节点 ( trait BO) 可以是相当复杂的对象，并且可以用多个子类型来实现，因此实现“解析节点”（即直接链接到其他节点的节点）的最佳方法是什么？( BO with ResolvedBO)。
2. 如果自行解析节点是最好的方法（lazy val r_attr_bo: Seq[BO with ResolvedBO] = attr_bo map (uni.m_list_r(_))in trait ResolvedBO），那么如何初始化图的引用（val uni: Universe）trait ResolvedBO？
3. 到底，在 Scala 中处理类图结构的最佳方式是什么？

谢谢

Answer 1

对于第 3 点，这取决于您对“最佳”的定义。我建议不要自己实现库并使用scala-graph，它似乎适合您的需求（不可变图）。

如果您确实坚持编写自己的图形库（这是提高 Scala 知识的好方法），请尝试避免使用对象图（使用引用来表示连接）。而是选择Graph具有通用操作的类，例如：myGraph.neighborsOf( myVertex )。

一个很好的表示（易于实现，但对于巨大的图来说速度很慢）是将图表示为一组边。要添加新边，只需将新对象添加到集合中即可。要获得所有顶点的集合，只需展平边的集合即可。要获取顶点的邻居，您需要迭代每条边等。

更快的解决方案是使用更复杂的表示形式，例如 Map，其中键是顶点，值是邻居集。

查看 scala-graph 源代码以获取灵感。