Immutable graph-like structures in Scala

Good day! I am trying to build an immutable graph in Scala 2.9.1. This is given to me with Seq[BO]

, where BO

can represent one node in the graph, and BO.attr_bo: Seq[String]

that represents edges to other nodes given by the string name. And I need to plot the "resolved" graph, presented BO with ResolvedBO

You can see the possible implementation 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] = => (, 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 the graph at all (it can also be turned off) Also, if it matters, I can limit the graph without cycles.

So my main questions are:

  • Since nodes ( trait BO

    ) can be quite complex objects and can be implemented with several subtypes, what is the best way to implement "allowed nodes" - i.e. nodes with direct links to other nodes? ( BO with ResolvedBO

  • If the nodes themselves decide ( lazy val r_attr_bo: Seq[BO with ResolvedBO] = attr_bo map (uni.m_list_r(_))

    in trait ResolvedBO

    ), how can I initialize the link to the graph ( val uni: Universe

    ) in trait ResolvedBO

  • Actually, what's the best way to deal with graph-like structures in Scala?

Thank you


source to share

1 answer

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

If you really insist on writing your own graph library (which is a good way to improve your knowledge in Scala), try to avoid plotting objects (using links to represent connections). Let's go back to the class Graph

with the general type of operations: myGraph.neighborsOf( myVertex )


A good 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 simply add a new object to the set. To get a set of all vertices, you simply flatten a set of edges. To get adjacent vertices, you iterate over each edge, etc.

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

Take a look at the scala -graph source code for inspiration.



All Articles