CODEWITHSUNDEEP
scalacase-classrecursive-datastructures
Austin
Austin

Reputation: 1132

Recursive Types in Scala with a List

Similarly to mutually recursive types in scala I am trying to create a mutually recursive type in Scala.

I am trying to make a graph defined with this type (which does compile) :

 case class Node(val id : Int, val edges : Set[Node])

But I don't understand how I can actually create something with this type, because in order to initialize Node A with edges B and C, I need to at least have a lazy reference to B and C, but I can't simultaneously create their edgesets.

Is it possible to implement this recursive type?

EDIT:

Here is the solution I am currently using to convert an explicit adjacency list to a self-referential one.

def mapToGraph(edgeMap : Map[Int, mutable.Set[Int]]) : List[Node] = {
  lazy val nodeMap = edgeMap map  (kv => (kv._1, new Node(kv._1, futures.get(kv._1).get)))
  lazy val futures : Map[Int, Set[Node]] = edgeMap map (kv => {
    val edges = (kv._2 map (e => nodeMap.get(e).get)).toSet
    (kv._1, edges)
  })
  val eval = nodeMap.values.toList
  eval //to force from lazy to real - don't really like doing this
}

or alternatively, fromm an edgelist

//reads an edgeList into a graph
def readEdgelist(filename : String) : List[Node] = {
  lazy val nodes = new mutable.HashMap[Int, Node]()
  lazy val edges = new mutable.HashMap[Int, mutable.Buffer[Node]]()
  Source.fromFile(filename).getLines() filter (x => x != None) foreach {edgeStr =>
    val edge = edgeStr.split('\t')
    if (edge.size != 2) goodbye("Not a well-formed edge : " + edgeStr + " size: " + edge.size.toString)
    val src = edge(0).toInt
    val des = edge(1).toInt
    if (!(nodes.contains(src))) nodes.put(src, new Node(src, futures.get(src).get))
    if (!(nodes.contains(des))) nodes.put(des, new Node(des, futures.get(des).get))
    edges.put(src, edges.getOrElse(src, mutable.Buffer[Node]()) += nodes.get(des).get)
  }
  lazy val futures : Map[Int, Set[Node]] = nodes map {node => (node._1, edges.getOrElse(node._1, mutable.Buffer[Node]()).toSet)} toMap
  val eval = nodes.values.toList
  eval
}

Thanks everyone for the advice!

Upvotes: 2

Views: 1264

Answers (2)

Richard Sitze
Richard Sitze

Reputation: 8463

Chicken & egg... you have three options:

  1. Restrict your graphs to Directed Acyclic Graphs (DAGs) and use RKumsher's suggestion.

  2. To retain immutability, you'll need to separate your node instances from your edge sets (two different classes: create nodes, then create edge sets/graph).

  3. If you prefer the tight correlation, consider using a setter for the edge sets so that you can come back and set them later, after all the nodes are created.

Upvotes: 3

RKumsher
RKumsher

Reputation: 2897

Sounds like you need to work from the bottom up

val b = Node(1, Set.empty)
val c = Node(2, Set.empty)
val a = Node(3, Set(b, c))

Hope that helps

Upvotes: 3

Related Questions