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(_))
intrait ResolvedBO
), how can I initialize the link to the graph (val uni: Universe
) intrait ResolvedBO
? - Actually, what's the best way to deal with graph-like structures in Scala?
Thank you
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.
source to share