# 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] = 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 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

+3

source to share

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.

+2

source

All Articles