Problem
This is the implementation of BFS and DFS i have tried to follow from CLRS.Please suggest what can be improved in this code.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Graph {
VertexList[] row;
int time;
public Graph(String file) throws FileNotFoundException {
Scanner sc = new Scanner(new File(file));
String graphType = sc.next();
boolean undirected = true;
if (graphType.equals("directed"))
undirected = false;
row = new VertexList[sc.nextInt()];
for (int v = 0; v < row.length; v++)
row[v] = new VertexList(sc.next(), null);
while (sc.hasNext()) {
int v1 = indexForName(sc.next());
int v2 = indexForName(sc.next());
row[v1].head = new Node(v2, row[v1].head);
if (undirected) {
row[v2].head = new Node(v1, row[v2].head);
}
}
}
public int indexForName(String name) {
for (int v = 0; v < row.length; v++) {
if (row[v].vertexName.equals(name))
return v;
}
return -1;
}
public void print() {
System.out.println();
for (int v = 0; v < row.length; v++) {
System.out.print(row[v].vertexName);
for (Node nbr = row[v].head; nbr != null; nbr = nbr.next) {
System.out.print("-->" + row[nbr.vertexNum].vertexName);
}
System.out.println("n");
}
}
public void bfs(int s, int v) {
Node[] N = new Node[row.length];
for (int i = 0; i < row.length; i++) {
N[i] = new Node(indexForName(row[i].vertexName), null);
N[i].color = "white";
N[i].d = 1000;
N[i].p = null;
}
N[s].color = "gray";
N[s].d = 0;
N[s].p = null;
Queue Q = new LinkedList();
Q.add(s);
while (Q.isEmpty() != true) {
int u = (Integer) Q.remove();
for (Node nbr = row[u].head; nbr != null; nbr = nbr.next) {
if (N[nbr.vertexNum].color == "white") {
N[nbr.vertexNum].color = "gray";
N[nbr.vertexNum].d = N[u].d + 1;
N[nbr.vertexNum].p = N[u];
Q.add(nbr.vertexNum);
}
N[u].color = "black";
}
}
System.out.println("Printing distances of nodes");
for (int i = 0; i < N.length; i++) {
System.out.println("Node " + N[i].vertexNum + " Distance is "
+ N[i].d);
}
System.out.println("Printing shortest path from " + s + " to " + v);
printPath(N, s, v);
}
public void dfs() {
Node[] N = new Node[row.length];
for (int i = 0; i < row.length; i++) {
N[i] = new Node(indexForName(row[i].vertexName), null);
N[i].color = "white";
N[i].p = null;
}
time = 0;
for (int i = 0; i < row.length; i++) {
if (N[i].color == "white")
dfsVisit(N, N[i].vertexNum);
}
System.out.println("nnPrinting time and freq of vertexes in DFS");
for (int i = 0; i < row.length; i++) {
System.out.println("Node " + i + " time-d is " + N[i].time_d
+ " time-f is " + N[i].time_f);
}
}
public void dfsVisit(Node[] N, int u) {
time = time + 1;
N[u].time_d = time;
N[u].color = "gray";
for (Node v = row[u].head; v != null; v = v.next) {
if (N[v.vertexNum].color == "white") {
N[v.vertexNum].p = N[u];
dfsVisit(N, v.vertexNum);
}
}
N[u].color = "black";
time = time + 1;
N[u].time_f = time;
}
public void printPath(Node[] N, int s, int v) {
if (v == s)
System.out.print(s + " ");
else if (N[v].p == null)
System.out.println("No Path from s to v");
else {
printPath(N, s, N[v].p.vertexNum);
System.out.print(v + " ");
}
}
public static void main(String[] args) throws FileNotFoundException {
String fileName = "C:/Users/Dell PC/Algorithm_Workspace/Graph_CLRS/src/graph.txt";
Graph graph = new Graph(fileName);
graph.print();
graph.bfs(0, 3);
graph.dfs();
}
}
class Node {
int vertexNum;
Node next;
String color;
int d;
Node p;
int time_d;
int time_f;
public Node(int vertexNum, Node next) {
this.vertexNum = vertexNum;
this.next = next;
}
}
class VertexList {
String vertexName;
Node head;
public VertexList(String vertexName, Node head) {
this.vertexName = vertexName;
this.head = head;
}
}
The graph input file is in this format:
undirected
5
Ram
Dam
Mam
Kam
Tam
Ram Dam
Ram Mam
Dam Tam
Mam Tam
Tam Kam
Solution
the first thing I noticed in your code is the non-conventional indentation of 2 spaces instead of 4. Additionally your constructor declaration is not indented. The next thing I noticed is that yiou’re working on String instead of Path.
It’s usually considered incorrect to use Strings as paths, especially since normalizing Strings is harder than normalizing Paths. You should use the “new” I/O API of java from the java.nio package.
public Graph(Path file) throws IOException {
Scanner sc = new Scanner(file.toFile());
since you never use the graphType aside from determining whether the graph is directed or not you can condense the next four lines into one:
boolean undirected = !"directed".equals(sc.next());
If you want to keep your “readability-variables” (those are really not a bad thing) I strongly urge you to make a habit of putting braces around single-line if-blocks:
if (graphType.equals("directed")) {
undirected = false;
}
On that same note I strongly recommend always putting braces around for-loops (or in general put braces where possible, not where necessary). This helps you avoid bugs when later modifying the code and it’s generally a good habit to get into.
Onwards to the traversal. You use an algorithm that works by “coloring” nodes as you visit them. The colors are different depending on who you ask, but it’s always three colors. You use these colors as Strings. It would make the code much less error-prone (typos in color-checks) if you had an enum of colors:
enum Colors {
WHITE, GRAY, BLACK
}
This would give you compile-time checking of constant names instead of some erroneous behaviour at runtime.
~editor’s note: at this point I scrolled through the rest of the code
I already noticed you’re using a Vertex-List as a representation of the graph. Interestingly you seem to intermingle the Vertex Nodes and the List’s “Edge-Nodes” into one Node class. For this algorithm, it might be easier to actually represent the graph differently.
Consider following Vertex class:
class Vertex {
String label;
Set<Vertex> outgoingEdges;
}
Using this could make creating your graph much simpler. You can create Vertex instances and for building the graph put them into a Map<String, Vertex> instead of looking them up by name in an Array.
If your graph is undirected you’d have to duplicate the outgoingEdge for both vertices. Add in a Color and the other attributes you need for traversal and you’re good to massively simplify your traversal algorithm through iterative application (for BFS and DFS) and recursive application (for DFS) of a simplistic visit method:
void dfsVisit(Vertex n) {
time++;
n.time_d = time;
n.color = Color.GRAY;
for (Vertex outgoing : n.outgoingEdges) {
if (outgoing.color == Color.WHITE) {
outgoing.p = n;
dfsVisit(outgoing);
}
}
n.color = Color.BLACK;
time = time+1;
n.time_f = time;
}
This avoids all the implciit baggage you carry around in the numbers (if we ignore the time thing)…