Scala中不可變的圖形結構

Question

美好的一天！我試圖在Scala 2.9.1中構建不可變圖。 它給我Seq[BO]，其中BO可以代表圖中的一個節點，BO.attr_bo: Seq[String]誰代表邊緣到其他節點，由字符串名稱給出。我需要構造「解決」圖表中，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(_))），我怎樣才能初始化圖形的引用（val uni: Universe）trait ResolvedBO？
3. 總之，在Scala中使用類圖結構的最佳方式是什麼？

謝謝

Answer 1

對於3點，這取決於你是什麼「最好」的方式定義。我建議不要自己實現一個庫，並使用scala-graph這似乎適合您的需求（不可變圖）。

如果你真的堅持寫自己的圖庫（這是提高你在Scala知識的好方法），試着避免使用對象圖（用引用來表示連接）。寧可去Graph類，通用操作如：myGraph.neighborsOf(myVertex)。

一個很好的表示（容易實現，但對於巨大圖表很慢）是將圖形表示爲一組邊。要添加新邊，只需向該集添加一個新對象。要獲得所有頂點的集合，只需將這組邊集中在一起。要獲得頂點的鄰居，可以在每條邊上迭代，等等。

更快的解決方案是使用更復雜的表示形式，如一個Map，其中鍵是頂點，值是鄰居集。

看看scala-graph源代碼的靈感。