scala - 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完全代表图形(它也可以是断开连接的)
另外，如果这很重要，我可以将图形限制为没有循环。

所以我的主要问题:

由于节点( trait BO )可以是非常复杂的对象，并且可以通过多个子类型实现，那么实现“已解析节点”的最佳方法是什么 - 即与其他节点直接链接的节点？ ( BO with ResolvedBO )。

如果自己解析节点是最好的方法( lazy val r_attr_bo: Seq[BO with ResolvedBO] = attr_bo map (uni.m_list_r(_)) 中的 trait ResolvedBO )，我如何在 val uni: Universe 中初始化图的引用( trait ResolvedBO ) ?

在 Scala 中使用类图结构的最佳方式是什么？

谢谢你

Answer 1

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

如果您真的坚持要编写自己的图形库(这是提高您在 Scala 中的知识的好方法)，请尝试避免使用对象图形(使用引用来表示连接)。宁愿去一个 Graph具有通用操作的类，例如:myGraph.neighborsOf( myVertex ) .

一个很好的表示(易于实现但对于巨大的图来说很慢)是将图表示为一组边。要添加新边，您只需向集合中添加一个新对象。要获得所有顶点的集合，您只需展平边的集合。要获得顶点的邻居，您需要在每条边上进行迭代，等等。

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

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