title: Immutable graph-like structures in Scala
body: <p>Good day! I'm trying to construct immutable graph in Scala 2.9.1.
  It's given to me with <code>Seq[BO]</code>, where <code>BO</code> can represent one node in graph, and <code>BO.attr_bo: Seq[String]</code> who represents edges to other nodes, given by string name. And I need to construct "resolved" graph, represented by <code>BO with ResolvedBO</code>
  You can see possible realization here:</p>
  
  <pre><code>trait BO {
    def name: String
    def attr_bo: Seq[String]
  }
  
  trait ResolvedBO {
    x: BO =&gt;
    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 =&gt; (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"))))
  </code></pre>
  
  <p>where <code>class Universe</code> represents graph at all (it can also be disconnected one)
  Also, if it's important, I can restrict graph to be without cycles.</p>
  
  <p>So my main questions:</p>
  
  <ol>
  <li>Since nodes (<code>trait BO</code>) 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? (<code>BO with ResolvedBO</code>). </li>
  <li>If resolving nodes by themselves is the best way (<code>lazy val r_attr_bo: Seq[BO with ResolvedBO] = attr_bo map (uni.m_list_r(_))</code> in <code>trait ResolvedBO</code>), how can I initialize  graph's reference (<code>val uni: Universe</code>) in <code>trait ResolvedBO</code>?</li>
  <li>At all, what's the best way to work with graph-like structures in Scala?</li>
  </ol>
  
  <p>thank you</p>