Graph algorithmns with Scala   Leave a comment

Recently I got very interested in the Scala language after sucessfully completing a related course in Coursera. It definitely is a big jump to start thinking in terms of functional programming afters so many years of object oriented programming. I have tried to use immutable data structures and this being my first attempt at Scala I don’t expect the algorithms to be very efficient which will be confirmed by benchmarks later. So I will be grateful for any kind of feedback. Here are some examples of graph traversal algorithms in Scala. Here is the link of the github repo where the code is stored.

Here is a scala class that will help us represent the graph. Graph.scala has 3 classes Graph, Vertex and Edge.

package com.salil.graphs

class Graph {
  //Returns a set of vertices
  var vertices = Set[Vertex]()
  //Maintains a list of edges
  var edges = List[Edge]()
  //Maintains a map of vertices where each vertex(key) is connected to a list of vertices(value)
  var vertexMap = Map[Vertex,List[Vertex]]()


  def addVertex(v: Vertex) = vertices = vertices + v

  def addEdge(e: Edge) = {
    edges = e :: edges
    vertexMap += e.node1 -> (e.node2::vertexMap.getOrElse(e.node1, Nil))
  }

  override def toString = vertexMap.toString
}

case class Vertex(id: String, weight: Float = 0){
  override def toString = id
}

case class Edge(node1: Vertex, node2: Vertex, weight: Float = 0)</pre>

In my case I am representing the graphs in the following adjacency list format:

A:  B E F // A is connected to the vertices B, E and F
B:  A G C 
C:  D B 
D:  C G 
E:  F A 
F:  E A 
G:  H D B 
H:  G

The above graph would look something like this:

Capture

There are a couple of ways to traverse a graph:

  1. Depth First Search(DFS): In this case you traverse the depth of a tree visiting the child node before the sibling node. Based upon when the node is processed you can divide the DFS into 3 categories
    1. Pre Order: You process the node before processing any of it’s children
    2. Post Order: Process the node after all of it’s children are processed
    3. In Order(Symmetric): Process the node after it’s left sibling has been processed.
  2. Bread First Search(BFS): In this kind of traversal you visit the sibling before visiting the child nodes.

PreOrder Depth First Search

Let’s do a preorder depth first search on a simple graph starting from the Vertex A:

First we have to create a Graph object from the adjacency list given above using the utility class below:

package com.salil.graphs.util

import com.salil.graphs.{Edge, Vertex, Graph}

import scala.io.Source

/**
 * Created by sasurendran on 12/24/2014.
 */
object GraphUtil {

  def getGraphFromAdjacencyList(fileName: String): Graph = {

    val graph = new Graph()
    //Read a line from the file for eg. A : B C denoting A is connected to B and C
    for (line <- Source.fromFile(fileName).getLines()) {
      val arr = line.trim.split(":") //Split the line into two using the delimiter ':"
      graph.addVertex(Vertex(arr(0))) //Add the vertex A
      if (arr.length > 1)
        for (e <- arr(1).trim.split("\\s+"))
          graph.addEdge(new Edge(new Vertex(arr(0)), new Vertex(e))) //Add the edge A -> B and A -> C
    }
    graph
  }

}

Next comes the actual code that does the preorder search

 

package com.salil.graphs.search


import com.salil.graphs.util.GraphUtil
import com.salil.graphs.{Graph, Vertex}


object DFS extends App {

  if (args.isEmpty)
    print("Please pass a filename containing the graph details to the program")
  else
    new DFS().doDFS(args(0))
}

  class DFS {
    def doDFS(fileName: String) {
      val g = GraphUtil.getGraphFromAdjacencyList(fileName)
      println(preOrderDFS(g, g.vertices, List(Vertex("A"))).mkString(" "))
    }


  def preOrderDFS(g: Graph, unmarkedSet: Set[Vertex], vertexList: List[Vertex]): List[Vertex] = vertexList match {
    case List() => Nil
    case head :: tail => (head) :: preOrderDFS(g, unmarkedSet - head,
      g.vertexMap.getOrElse(head, List()).reverse ++ tail intersect (unmarkedSet.toList))
  }
}

All the logic of the preOrder search is present in the preOrderDFS method. This method takes 3 parameters:

  1. g: The graph to be traversed
  2. unmarkSet: A set of vertices that is yet to be marked
  3. vertexList: A list of vertices that has to be traversed in the specified order

The initial call to preOrderDFS() happens in doDFS() and the intial parameters is the graph g, all the vertices in g and the 3rd parameter is a list containing the single start vertex from where we wish to start traversing.

The method uses Scala’s pattern matching using case classes. Here we match vertexList and in case the list is empty we return back an empty list other wise we return the head of the list prepended to the output of the next call of preOrderDFS.

To the next call we pass the same graph as the first parameter but since we have already visited the head we remove head from set of unmarked vertices and pass it as the second paramter.

Now the third parameter is a little bit more trickier. We should traverse the children of the vertex we just visited(i.e. head) and then traverse the rest of the list(i.e. tail). But at the same time we shouldn’t visit the vertices that have already been visited. We get the children of the head from the graph using the

g.vertexMap.getOrElse(head, List())

This getOrElse method returns back the children or an empty list if head has not children. Reversing the list is optional. I reversed it because I wanted to maintain the order of the adjacency list. But please do note while prepending the element to a list is a constant time operation (O(1)) in Scala appending an element as well as reversing the list is a linear time operation (O(n)).

Next we append the tail to children and intersect it with the list of unmarked vertices. So the 3rd parameter contains a list of vertices that are present in (children ++ tail) and unmarked vertices.

When the vertexList is empty the whole chain terminates and returns. When running this code on the above graph you get the output:

A B G H D C E F

which is exactly how the preorder would work if it honored the order of the adjacency list and started out from the vertex “A”.

Post Order Depth First Search

 

def postOrderDFS(g: Graph, unmarkedSet: Set[Vertex], vertexList: List[Vertex]): List[Vertex] = vertexList match {
    case List() => Nil
    case head :: tail => val visited = postOrderDFS(g, unmarkedSet - head,
      g.vertexMap.getOrElse(head, List()).reverse intersect unmarkedSet.toList) :+ head
      visited ::: postOrderDFS(g, unmarkedSet -- visited, tail diff visited)
  }

Running post order on the same graph shown above starting from A will give you:

H C D G B F E A

Breadth First Search

Now lets try Breadth First Search

def bfs(g:Graph,unmarkedSet:Set[Vertex],queue:List[Vertex]):List[Vertex] = queue match{
    case Nil => Nil
    case head::tail => head::bfs(g,unmarkedSet - head,
      tail++ g.vertexMap.getOrElse(head,List()).reverse intersect(unmarkedSet.toList))
  }

This will output on the above graph starting from ‘A’

A B E F G C H D

This is very similar to the preOrderDFS algorithm and the only difference is that instead of appending the tail of vertices we are prepending it and hence the tail (i.e. the siblings of the node) will get processed first before the children.

Advertisements

Posted December 25, 2014 by salilsurendran in Technology

Tagged with ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: