Scalaの変更不能なグラフのような構造

Question

おはよう！私はScala 2.9.1で不変グラフを作成しようとしています。 Seq[BO]で私に与えられました。BOはグラフで1つのノードを表すことができ、BO.attr_bo: Seq[String]は他のノードへのエッジを表し、文字列名で与えられます。そして、私はあなたがここで可能な実現を見ることができますBO with ResolvedBO で表される「解決」のグラフを構築する必要があります：class Universeは（それは、1つを切断することができます）、すべてのグラフを表し

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

また 、それが重要だ場合には、Iグラフをサイクルなしで制限することができます。

だから私の主な質問：ノード（trait BO）以来

1. は非常に複雑なオブジェクトにすることができ、いくつかのサブタイプで実現することができ、「解決ノード」を実装するための最良の方法は何である - の直接リンクを持つすなわちノード他のノードに？ （BO with ResolvedBO）。
2. ノードを単独で解決するのが最良の方法（lazy val r_attr_bo: Seq[BO with ResolvedBO] = attr_bo map (uni.m_list_r(_))：trait ResolvedBO）の場合、グラフの参照（val uni: Universe）をtrait ResolvedBOに初期化するにはどうすればよいですか？
3. Scalaのグラフのような構造を使って作業する最善の方法は何ですか？

あなたは

Answer 1

ポイント3については、それがどのような「最良の」手段のあなたの定義に依存感謝します。私はlibを自分で実装することをお勧めしませんあなたのニーズ（不変グラフ）に適しているようだscala-graphを使用してください。

あなた自身のグラフライブラリを書くことを本当に主張しているなら（Scalaで知識を向上させる良い方法です）、オブジェクトのグラフを避けてください（接続を表す参照を使用して）。代わりにmyGraph.neighborsOf(myVertex)のような汎用操作を使用してGraphクラスに進みます。

グラフを辺の集合として表現するのは、簡単に実装できますが、巨大なグラフでは遅くなります。新しいエッジを追加するには、新しいオブジェクトをセットに追加するだけです。すべての頂点のセットを取得するには、エッジのセットを平坦化します。頂点の近傍を取得するには、すべてのエッジなどを反復処理します。

より速い解決策は、キーが頂点であり、値が近隣のセットであるMapなど、より複雑な表現を使用することです。

インスピレーションのためのスケーラグラフのソースコードをご覧ください。