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!

Typical Graph-Processing API [in JAVA]

This post defines API for fundamental graph operations for developing graph processing algorithms. The following is an API:
 

public class Graph

                                                                                             
     Graph(int V)                   creates a V-vertex graph with no-edge
     Graph(String filePath)         creates a graph from specified file
 int V()                            number of vertices
 int E()                            number of edges
void addEdge(int v, int w)             add edge v-w to this graph
List<Integer> adjacentVertices(int v) vertices adjacent to vertex v 
String toString()                          string representation
                          API for an undirected graph

    This API contains two constructors, methods to return the number of vertices and edges, a method to add an edge, a method to get adjacent vertices and method to print Graph.

    Let me present the implementation part of it.It is written in JAVA. The above API is taken from Chapter:4 Graphs, Algorithms, 4th Ed. I have implemented the above API as presented below. Feel free to use it for practicing some of the  fundamental graph algorithms like BFS, DFS, Shortest path etc...


                                                                                                                                      

Graph.java

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;

public class Graph {
    List<Integer>[] adjList;

    /** This constructor build the graph of v vertices of no edges*/
    public Graph(int v) {
        createGraph(v);
    }

    /**
     * Constructs the graph from a given file. The first two lines give  the number of vertices and edges in the graph, respectively. From third line, edges are specified, as shown in example below.
     1. Every line in the file should start with an integer. I, mean no space or empty chars at the start of each line.
     2. <EOF> should be on the line of last edges specified in the file.
     */
    public Graph(String filePath) {
        BufferedReader reader;
        try {
            reader = new BufferedReader(new FileReader(new File(filePath)));
            int v = Integer.valueOf(reader.readLine());
            createGraph(v);
            int e = Integer.valueOf(reader.readLine());
            String line = reader.readLine();
            while (line != null) {
                int[] vertices = getVerticesForEdge(line);
                addEdge(vertices[0], vertices[1]);
                line = reader.readLine();
            }
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    /** Retrieves the vertices from a given string. */
    private int[] getVerticesForEdge(String line) {
        int[] vertices = new int[2];
        vertices[0] = Integer.valueOf(line.split(" ")[0]);
        vertices[1] = Integer.valueOf(line.split(" ")[1]);
        return vertices;
    }

    /** Creates a graph with v vertices without any edges.*/
    private void createGraph(int v) {
        adjList = (ArrayList<Integer>[]) new ArrayList[v];
        for (int i = 0; i < v; i++)
            adjList[i] = new ArrayList<Integer>();
    }

    /** Retievs the adjacent vertices for a given vertex.*/
    public List<Integer> adjacentVertices(int v) {
        return adjList[v];
    }

    /** Adds an edge: v-w to the current graph.*/
    public void addEdge(int v, int w) {
        adjList[v].add(w);
        adjList[w].add(v);
    }

    /** Retrieves the number of vertices in this graph.*/
     public int V() {
        return adjList.length;
    }

    /** Retrieves the number of vertices in this graph.*/
    public int E() {
        int edges = 0;
        for (int i = 0; i < adjList.length; i++)
            edges += adjList[i].size();
        return edges / 2;
    }

    /** Return the string version of the graph.*/
    public String toString() {
        int vertices = V();
        int edges = E();
        String s = vertices + " vertices, " + edges + " edges\n";
        for (int v = 0; v < vertices; v++) {
            s += v + ": ";
            for (int w : this.adjacentVertices(v)) {
                s += w + " ";
            }
            s += "\n";
        }
        return s;
    }
}

                                                                                                                                      
DemoGraph.java

public class DemoGraph {
    public static void main(String[] args) {
        Graph g = new Graph("<File Specifying the graph>");
        System.out.println(g.toString());
    }
}

                                                                                                                                        
====Output====
13 verticies, 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 
                                                                                                                                      
Sample Input File: (tinyG.txt)
13
13
0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3

       This implementation of graph considered vertex-id to be only integers. It has used adjacency list as the graph representation. Feel free to let me know any bugs in the code.