matos416 - 1 year ago 78

Scala Question

i'm trying to solve a problem from the UVA online judge site, specifically 539 where i need to use a DFS to find the longest path, i can solve it imperatively but i'd like to do it in a more functional idiomatic way using scala, the problem is that when the algorithm return from a branch the data structure is not updated for use in others branches, don't want to use vars, nor side effects, heres my code:

`type Vertex=Int`

type Graph = Map[Vertex,Set[Vertex]]

def DFS(start: Vertex, g: Graph): Int = {

def loop(v: Vertex, visited: List[Vertex], size: Int = 0): Int = {

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

if (neighbours == Nil) size

else {

( for (elem <- neighbours) yield loop(elem, v :: visited, size + 1) ).max }

}

loop(start, List())

}

Answer Source

You need to store the paths, not the Vertex in the visited Set (better performance than List in contains operation). Also you should try this starting in all the Vertex. Check this:

```
type Vertex = Int
type Graph = Map[Vertex, Set[Vertex]]
def DFS(g: Graph): Int = {
def loop(current: Vertex, visited: Set[(Vertex, Vertex)]): Int = {
val neighbours = g(current).filterNot(contains(visited, current, _))
if (neighbours.isEmpty)
visited.size
else {
(for {
elem <- g(current).filterNot(contains(visited, current, _))
} yield (loop(elem, add(visited, current, elem)))).max
}
}
(for {
elem <- g.keys
} yield (loop(elem, Set()))).max
}
def add(set:Set[(Vertex,Vertex)], v1:Vertex, v2:Vertex): Set[(Vertex,Vertex)] =
if(v1 < v2) add(set, v2,v1) else set.+((v1,v2))
def contains(set:Set[(Vertex,Vertex)], v1:Vertex, v2:Vertex):Boolean =
if(v1 < v2) contains(set, v2,v1) else set.contains((v1,v2))
```