9
\$\begingroup\$

I would love it if someone could give me some suggestions for these 2 graph search functions. I am new to scala and would love to get some insight into making these more idiomatic.

  type Vertex=Int
  type Graph=Map[Vertex,List[Vertex]]
  val g: Graph=Map(1 -> List(2,4), 2-> List(1,3), 3-> List(2,4), 4-> List(1,3))
 //example graph meant to represent
 //  1---2
 //  |   |
 //  4---3

//I want this to return results in the different layers that it finds them (hence the list of list of vertex)     
def BFS(start: Vertex, g: Graph): List[List[Vertex]]={
  val visited=List(start)
  val result=List(List(start))

  def BFS0(elems: List[Vertex],result: List[List[Vertex]], visited: List[Vertex]): List[List[Vertex]]={
    val newNeighbors=elems.flatMap(g(_)).filterNot(visited.contains).distinct
    if(newNeighbors.isEmpty) result
    else BFS0(newNeighbors, newNeighbors :: result, visited ++ newNeighbors)
    }

  BFS0(List(start),result,visited).reverse
   }

//I would really appreciate some input on DFS, I have the feeling there is a way to do this sans var.

 def DFS(start: Vertex, g: Graph): List[Vertex]={
    var visited=List(start)
    var result=List(start)

  def DFS0(start: Vertex): Unit={
     for(n<-g(start); if !visited.contains(n)){
       visited=n :: visited 
       result=n :: result 
       DFS0(n)
  }}
   DFS0(start)
   result.reverse     
} 

//some examples
scala> BFS(1,g)
res84: List[List[Vertex]] = List(List(1), List(2, 4), List(3))
scala> BFS(2,g)
res85: List[List[Vertex]] = List(List(2), List(1, 3), List(4))
scala> DFS(1,g)
res86: List[Vertex] = List(1, 2, 3, 4)
scala> DFS(3,g)
res87: List[Vertex] = List(3, 2, 1, 4)
\$\endgroup\$
  • \$\begingroup\$ Your representation of graphs and nodes is broken. Shouldn't that at least be "type Graph=Map[Vertex,Set[Vertex]]"? Because no vertex should be listed twice as a connection for any other node (assuming that all the edges are undirected). \$\endgroup\$ – itsbruce Aug 24 '13 at 17:34
  • \$\begingroup\$ Why are you searching this graph? It seems you aren't looking for any particular node, just collecting the whole set of nodes. This doesn't seem generally applicable. Hard to adapt to searching for a node with specific properties. \$\endgroup\$ – itsbruce Aug 24 '13 at 19:18
  • \$\begingroup\$ @itsbruce you are right about the definition. I have changed that to Set to avoid having that issue. As to why I am doing these searches: I was not looking for any node in particular, but rather wanted to check the logic in my DFS to use it to find strongly connected components. Thanks for the review! \$\endgroup\$ – JPC Aug 26 '13 at 13:02
14
\$\begingroup\$

OK, so I'm going to start with your DFS method. You're right - you should be able to do it without those vars in the outer function. You should be able to work out why - after all, you have vals in the outer layer of your BFS method. Why? Because your BFS uses a recursive helper function, so the vals are only used once (and could be discarded).

So your DFS function should really use recursion, but I suspect you may have rejected recursion because you couldn't see how visited would be properly preserved as a recursive function popped back and forth. The answer is foldLeft.

def DFS(start: Vertex, g: Graph): List[Vertex] = {

  def DFS0(v: Vertex, visited: List[Vertex]): List[Vertex] = {
    if (visited.contains(v))
      visited
    else {
      val neighbours:List[Vertex] = g(v) filterNot visited.contains 
      neighbours.foldLeft(v :: visited)((b,a) => DFS0(a,b))
    } 
  }
  DFS0(start,List()).reverse
} 

I don't have space here to explain foldLeft, if you've never encountered it - maybe Matt Malone's blog post will help. You can rewrite almost anything with foldLeft, although it isn't always a good idea. Definitely the right thing to do here, though. Notice that I completely dropped your result var since visited is the result, the way you are doing this.

My version of your DFS method is entirely functional, which is how Scala really wants to be used. Note also the lack of braces and brackets in

val neighbours:List[Vertex] = g(v) filterNot visited.contains

It can be written

val neighbours:List[Vertex] = g(v).filterNot(visited.contains)

but the Scala style is to omit the brackets and braces except where essential.

Your BFS method is similarly over-populated. I've slimmed it down a little without altering the basic way it works:

def BFS(start: Vertex, g: Graph): List[List[Vertex]] = {

  def BFS0(elems: List[Vertex],visited: List[List[Vertex]]): List[List[Vertex]] = {
    val newNeighbors = elems.flatMap(g(_)).filterNot(visited.flatten.contains).distinct
    if (newNeighbors.isEmpty) 
      visited
    else
      BFS0(newNeighbors, newNeighbors :: visited)
  }

  BFS0(List(start),List(List(start))).reverse
} 

It still gives the same results.

The other big point to make is that while Scala is a functional language it is also an Object Oriented language. Those DFS and BFS methods should belong to a graph object, preferably at least derived from a generic class. Something like this:

class Graph[T] {
  type Vertex = T
  type GraphMap = Map[Vertex,List[Vertex]]
  var g:GraphMap = Map()

  def BFS(start: Vertex): List[List[Vertex]] = {

    def BFS0(elems: List[Vertex],visited: List[List[Vertex]]): List[List[Vertex]] = {
      val newNeighbors = elems.flatMap(g(_)).filterNot(visited.flatten.contains).distinct
      if (newNeighbors.isEmpty)
        visited
      else
        BFS0(newNeighbors, newNeighbors :: visited)
    }

    BFS0(List(start),List(List(start))).reverse
  }

  def DFS(start: Vertex): List[Vertex] = {

    def DFS0(v: Vertex, visited: List[Vertex]): List[Vertex] = {
      if (visited.contains(v))
        visited
      else {
        val neighbours:List[Vertex] = g(v) filterNot visited.contains
        neighbours.foldLeft(v :: visited)((b,a) => DFS0(a,b))
      }
    }
    DFS0(start,List()).reverse 
  }
}

And then you could do this:

scala> var intGraph = new Graph[Int]
scala> intGraph.g = Map(1 -> List(2,4), 2-> List(1,3), 3-> List(2,4), 4-> List(1,3))
scala> intGraph.BFS(1)
res2: List[List[Int]] = List(List(1), List(2, 4), List(3))
scala> intGraph.BFS(2)
res3: List[List[Int]] = List(List(2), List(1, 3), List(4))
scala> intGraph.DFS(3)
res4: List[Int] = List(3, 2, 1, 4)

or this:

scala> var sGraph = new Graph[String]
scala> sGraph.g = Map("Apple" -> List ("Banana","Pear","Grape"), "Banana" -> List("Apple","Plum"), "Pear" -> List("Apple","Plum"), "Grape" -> List("Apple","Plum"), "Plum" -> List ("Banana","Pear","Grape"))
scala> sGraph.BFS("Apple")
res6: List[List[java.lang.String]] = List(List(Apple), List(Banana, Pear, Grape), List(Plum))
\$\endgroup\$
  • \$\begingroup\$ incredibly helpful! \$\endgroup\$ – JPC Aug 28 '13 at 3:44
  • \$\begingroup\$ You're welcome. Really, though, I don't think Map is the best model for graphs, although having a constructor method which took a Map as input might often be fine. I would implement Graph as an immutable generic collection, most of whose methods returned new views/versions/subsets of the original object. I'd write the DF and BF traversal methods in the style of fold/foldLeft/foldRight so that searching the graph for a specific node (or subset) or returning the whole graph (in either of your given styles) was just a case of passing in the right function. \$\endgroup\$ – itsbruce Aug 28 '13 at 8:42
  • \$\begingroup\$ Is this what you were looking for from an answer, @JPC, or are you after some more/other information? \$\endgroup\$ – itsbruce Aug 28 '13 at 11:12
  • \$\begingroup\$ I went back and re-read this now and think you did a fantastic job at explaining! I really wish I could give you another upvote. This is exactly the info I was looking for. I'm trying to learn scala on my own, but having few-no people to review what I do, I fear I am incurring in a bunch of pitfalls and developing poor habits. So thank you for helping me change this! \$\endgroup\$ – JPC Aug 28 '13 at 11:43
  • \$\begingroup\$ oh and thanks for actually providing a link to that blog post...few people seem to be doing this now for some reason. \$\endgroup\$ – JPC Aug 28 '13 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.