Simple Graph Processing Utils : [Java]

This post presents the code snippets for some simple graph processing tasks. Preferred Language in Java.

Tasks

1. Connectvity:Given a graph, support queries of the form: Are two given vertices connected?
2. Finding Path: Given a graph, vertex v and vertex w , support queries of the form Is there a path from v to w? If so, find such a path.

Task 1: Connectivity

Given a graph, support queries of the form: Are two given vertices connected?

    Two vertices are said to be connected, if there exists a path from one vertex to another vertex. We can find out connectivity by traversing the graph. This task is based on one of the graph traversal techniques:Depth First Search.

    Let me present a brief overview of Depth First Search. To visit a vertex:

•  Mark it as having visited.
• Visit (recursively) all the vertices that are adjacent to it and that have not been marked.

     Let us design a GraphUtil class, that provides a method called isConnected(int v, int w) , which returns true if the vertices v and w are connected; Otherwise false;
                                                                                                    
GraphUtils.java

public class GraphUtils {
public static boolean isConnected(Graph g, int v, int w, boolean[] marked) {
        boolean isConnected = false;
        if (v == w) {
            isConnected = true;
        } else {

            for (int u : g.adjacentVertices(v)) {
                if (!marked[u]) {
                    marked[u] = true;
                    isConnected = isConnected(g, u, w, marked);
                    if (isConnected) {
                        break;
                    }
                }
            }
        }
        return isConnected;
    }
  }

    The Graph API, we have used in the above class is explained in my previous post. In the above method isConnected(Graph g, int v, int w, boolean[] marked), g is the graph to check if two vertices are connected, v is the source vertex and u is destination vertex, and marked is the boolean array. This array is used to keep track, if a vertex is visited, while traversing the graph. Default values of this array are false.

    Following is the demo for the above method.   

                                                                                                    
DemoGraph.java

public class DemoGraph {
    public static void main(String[] args) {
        Graph g = new Graph("<File location>"); // you can find the sample input file in my previous post
        System.out.println(g.toString());
        System.out.println("Connectivity of Vertices " + 0 + " and " + 4 + ":"
                + GraphUtils.isConnected(g, 0, 4, new boolean[g.V()]));
          }
}

                                                                                                                                       
====Output====
13 vertices, 13 edges
0: 5 1 2 6
1: 0
2: 0
3: 4 5
4: 3 6 5
5: 0 4 3
6: 4 0
7: 8
8: 7
9: 12 10 11
10: 9
11: 12 9
12: 9 11  
Connectivity of Vertices 0 and 4:true

Task 2: Finding path

Given a graph, vertex v and vertex w , support queries of the form Is there a path from v to w? If so, find such a path.

This task is similar to task 1, as it based on DFS. Only difference is that, we construct path recursively every time we visit a new vertex. 
Let us add a new method called findPath(Graph g, int v, int w, boolean[] marked) , which returns path if the vertices v and w are connected; Otherwise <NO PATH>;


                                                                                                    
GraphUtils.java

         public class GraphUtils {

    public static String findPath(Graph g, int v, int w, boolean[] marked) {
        marked[v] = true;
        String path = findPath(g, v, w, marked, null);
        return path != null ? String.valueOf(v) + path : "<NO PATH>";
    }

    private static String findPath(Graph g, int v, int w, boolean[] marked,
            String path) {
        if (v == w) {
            path = "";
        }

        else {
            for (int u : g.adjacentVertices(v)) {
                if (!marked[u]) {
                    marked[u] = true;
                    path = findPath(g, u, w, marked, path);
                    if (path != null) {
                        path = "-" + String.valueOf(u) + path;
                        break;
                    }
                }
            }
        }
        return path;
        }
  }

Following is the demo for the above method.   
                                                                                                    
DemoGraph.java

public class DemoGraph {

    public static void main(String[] args) {
        Graph g = new Graph("<File location>"); // you can find the sample input file in my previous post
        System.out.println(g.toString());
       
        int v = 4;
        int w = 0;
        System.out.println("Path between " + v + " and " + w + " is: "
                + GraphUtils.findPath(g, v, w, new boolean[g.V()]));

        v = 4;
        w = 9;
        System.out.println("Path between " + v + " and " + w + " is: "
                + GraphUtils.findPath(g, v, w, new boolean[g.V()]));
    }
}

                                                                                                                                       
====Output====
13 vertices, 13 edges
0: 5 1 2 6
1: 0
2: 0
3: 4 5
4: 3 6 5
5: 0 4 3
6: 4 0
7: 8
8: 7
9: 12 10 11
10: 9
11: 12 9
12: 9 11  

Path between 4 and 0 is: 4-3-5-0
Path between 4 and 9 is: <NO PATH>

Feel free to let me know, if there are any bugs!