Scala中不可变的图形结构 [英] Immutable graph-like structures in Scala

问题描述

美好的一天！我试图在Scala 2.9.1中构建不可变图。
它给我的 Seq [BO] ，其中 BO 可以表示图中的一个节点， BO.attr_bo：Seq [String] 表示边界到其他节点，由字符串名称给出。我需要构建已解决图，由 BO代表，其中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 
 $ b $ class Universe（list：Seq [BO]）{
 val m_list：Map [String，BO] = list.map （x =>（x.name，x））（collection.breakOut）
 val m_list_r：映射[String，BO和ResolvedBO] = ... ??? （b），新的S_BO（b，c），新的S_BO（b，Seq （a，c）），新的S_BO（c，Seq（a，b））））
  

其中 class Universe 代表图形（它也可以是一个连接）
另外，如果它很重要，我可以限制图形是没有周期的。

所以我的主要问题：

1. 既然节点（ trait BO ）可以是相当复杂的对象，可以通过几个子类型来实现，实现解析节点的最佳方式是什么 - 即与其他节点直接链接的节点节点？ （ BO和ResolvedBO ）。如果自行解析节点是最好的方法（ lazy val r_attr_bo：Seq [BO with ResolvedBO] = attr_bo map（uni.m_list_r（_））
code> trait ResolvedBO ），我如何初始化图的引用（ val uni：Universe ）in trait ResolvedBO ？

2. 总而言之，在Scala中使用类图结构的最佳方式是什么？

谢谢

解决方案

你对最好意思的定义。我建议您不要自己实现一个库，并使用 scala-graph ，这似乎符合您的需求（不可变图）。

如果你真的坚持写你自己的图库（这是提高你在Scala中的知识的一个好方法），请尝试避免一个对象图使用引用来表示连接）。而是使用像 myGraph.neighborsOf（myVertex）。

$ b这样的通用操作来执行 Graph 类。
$ b

一个好的表示（容易实现，但对于巨大的图很慢）是将图形表示为一组边。要添加新的边，只需向该集添加一个新对象。要获得所有顶点的集合，只需将这组边集中在一起。为了得到顶点的邻居，你在每一个边上迭代，等等。

更快的解决方案是使用更复杂的表示，比如一个Map，其中的键是顶点和值的邻居组。

看看scala-graph源代码的灵感。

Good day! I'm trying to construct immutable graph in Scala 2.9.1. It's given to me with Seq[BO], where BO can represent one node in graph, and BO.attr_bo: Seq[String] who represents edges to other nodes, given by string name. And I need to construct "resolved" graph, represented by BO with ResolvedBO You can see possible realization here:

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"))))

where class Universe represents graph at all (it can also be disconnected one) Also, if it's important, I can restrict graph to be without cycles.

So my main questions:

1. Since nodes (trait BO) can be quite complex objects and can be realized with several subtypes, what is the best way to implement "resolved nodes" - i.e. nodes with direct links to other nodes? (BO with ResolvedBO).
2. If resolving nodes by themselves is the best way (lazy val r_attr_bo: Seq[BO with ResolvedBO] = attr_bo map (uni.m_list_r(_)) in trait ResolvedBO), how can I initialize graph's reference (val uni: Universe) in trait ResolvedBO?
3. At all, what's the best way to work with graph-like structures in Scala?

thank you

解决方案

For point 3, it depends on your definition of what "best" means. I would recommend not implementing a lib yourself and use scala-graph which seems to be suited to your needs (immutable graphs).

If you really insist to write your own graph library (it's a good way to improve your knowledge in Scala), try avoiding a graph of objects (using references to represent the connections). Rather go for a Graph class with generic operations like: myGraph.neighborsOf( myVertex ).

A nice representation (easy to implement but slow for huge graphs) is to represent the graph as a set of edges. To add a new edge, you just add a new object to the set. To get the set of all vertices, you just flatten the set of edges. To get the neighbors of a vertex, you iterate on every edges, etc.

A faster solution is to use a more complex representation, like a Map where the keys are vertices and the values the set of neighbors.

Have a look at scala-graph source code for inspiration.

这篇关于Scala中不可变的图形结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！