Java Graph:

Extend the given graph class to make two new subclasses DirectedGraph and UndirectedGraph. Hint: Override the addEdge() method.

Implement BFS algorithm on an undirected graph following the pseudo-code given below. Read the file mediumG.txt as the input graph. Print the BFS paths from a source to all the other nodes in the graph.

Hints: Use the Queue interface from Java Collections Framework and instantiate a queue using a LinkedList type object. Enqueing can be done here by the add() method while dequeing can be done by the remove() method. You can use the element() method to peek at the head of the queue.

Write a driver program, which reads input files mediumG.txt as an undirected graph and reads an input file tinyDG.txt as a directed graph. This driver program should display the graphs in the form of adjacency lists.

Graph.java

import java.io.BufferedReader;

import java.io.File;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.io.IOException;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.StringTokenizer;

/*

* To change this template, choose Tools | Templates

* and open the template in the editor.

*/

public class Graph {

public int V;

public int E;

public LinkedList[] adj;

public Graph()

{

V = 0;

E = 0;

}

public Graph(BufferedReader reader) throws IOException

{

String line;

line = reader.readLine();

V = Integer.parseInt(line);

line = reader.readLine();

E = Integer.parseInt(line);

adj = new LinkedList[V];

for (int v = 0; v

adj[v] = new LinkedList();

}

while ((line = reader.readLine()) != null) {

int tempV1, tempV2;

StringTokenizer st = new StringTokenizer(line, " ");

tempV1 = Integer.parseInt(st.nextToken());

tempV2 = Integer.parseInt(st.nextToken());

addEdge(tempV1, tempV2);

}

}

public void addEdge(int v, int w) {

}

public String tostring()

{

String s = new String();

s = "There are "+V+" vertices and "+E+" edges ";

for(int i=0;i

{

s = s+i+": ";

for(int j = 0; j

{

s = s+adj[i].get(j)+" ";

}

s = s+" ";

}

return s;

}

}

tinyDG.txt

13 22 4 2 2 3 3 2 6 0 0 1 2 0 11 12 12 9 9 10 9 11 7 9 10 12 11 4 4 3 3 5 6 8 8 6 5 4 0 5 6 4 6 9 7 6

largeG.txt

1000000 7586063 999812 999997 999592 999782 999499 999881 999213 999297 999082 999896 999067 999159 999063 999354 999037 999626 998991 999808 998856 999431 998602 998726 998601 998719 998494 999657 998475 999232 998456 999256 998375 999945 998353 999790 998347 999348 998299 998335 998292 998433 998261 999240 998244 999924 998013 999598 998008 999192 997936 998069 997905 999016 997877 999937 997847 998290

mediumG.txt

250 1273 244 246 239 240 238 245 235 238 233 240 232 248 231 248 229 249 228 241 226 231 223 242 223 249 222 225 220 247 219 221 218 224 218 227 217 232 216 232 214 219 214 221 213 235 213 238 212 214 212 219 212 221 212 244 211 222 211 225 210 212 210 214 210 219 210 221 210 244 209 211 209 222 209 225 208 226 208 231 207 210 207 212 207 214 207 219 207 221 207 244 206 209 205 207 205 210 205 214 205 219 205 221 204 222

BFS(G, s) for each vertex u e G.V- {s) 2 1 u. color = WHITE 4 5 s.color=GRAY PRINT-PATH(G, s, v) sd = 0 2 3 print s elseif v.?= NIL 9 ENQUEUE Q,s) 10 while Q? 4 print "no path from" s "to" v "exists" 5 else PRINT-PATH(G,s, v u = DEQUEUE(0) for each v E G.Adj[u print v 12 13 if v. color == WHITE v,color = GRAY 15 16 17 18 ENQUEUE(Q, v) ucolor = BLACK BFS(G, s) for each vertex u e G.V- {s) 2 1 u. color = WHITE 4 5 s.color=GRAY PRINT-PATH(G, s, v) sd = 0 2 3 print s elseif v.?= NIL 9 ENQUEUE Q,s) 10 while Q? 4 print "no path from" s "to" v "exists" 5 else PRINT-PATH(G,s, v u = DEQUEUE(0) for each v E G.Adj[u print v 12 13 if v. color == WHITE v,color = GRAY 15 16 17 18 ENQUEUE(Q, v) ucolor = BLACK