Connectivity in graphs   Leave a comment

Today we shall use some of the algorithms described in the previous post and explore connectivity in graphs. Lets start with finding connected components in an undirected graph. In an undirected graph connected components are subgraphs in which any two vertices have a path between them. Lets take a look at the graph represented by the adjacency list shown below:

A: F B
B: G A F H
C: D I
D: C I
E: J
F: A B G
G: B H F
H: G B
I: D C
J: E

This will look the figure below:

 

cc

In this case the vertices A,F,B,H,G is a connected component and so is C,D,I and E,J. Finding connected components in an undirected graph is relatively simple. You start with a vertex and do a depth or breadth first search to mark all the vertices that can be reached from that vertex with an index. Every vertex that can be reached is in that connected component. You increment the index and repeat the procedure with another unmarked vertex till there are no more vertices left to be marked. For the depth first search we shall use the class developed in the last post. The scala code that finds the connected components is shown below. Here is the link of the github repo where the code is stored.

package com.salil.graphs.connectivity

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

/**
 * Created by sasurendran on 12/25/2014.
 */

object ConnectedComponents extends App {

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

class ConnectedComponents {
  val graphTraversal = new GraphTraversal()

  def work(fileName: String)={
    val g = GraphUtil.getGraphFromAdjacencyList(fileName)
    println(connectedComponents(g,g.vertices.toList).map(x => x._1 + " -> " + x._2.mkString(",")).mkString("\n"))  
}


  def connectedComponents(g: Graph, unmarkedList: List[Vertex], i: Int = 0): 
      List[(Int, List[Vertex])] = unmarkedList match {
    case Nil => Nil
    case head :: tail => 
      val cc: List[Vertex] = graphTraversal.preOrderDFS(g, g.vertices, List(head))
      (i, cc) :: connectedComponents(g, unmarkedList diff cc, i + 1)
  }

}

 

In the code above we are once again using Scala’s pattern matching. If the unmarkedList is empty we return back a null list else we pick up the first element of the list and do a depth first traversal. We then add this list to a tuple along with the index and prepend it to the result of next method call. But this time we remove all the vertices found by the previous depth first traversal since they are already accounted for. We use the ‘diff’ operator which returns the difference between the two lists. The output of the above code is:

0 -> E,J
1 -> A,F,B,G,H
2 -> D,C,I

 

Advertisements

Posted December 26, 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: