matos416 matos416 - 4 months ago 11
Scala Question

trouble maintaining the integrity of the data structure in a graph algorithm in a functional way

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

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))