It is Sunday November 10, 2019 around 10:30 AM. As usual get up at 05:00 AM, prepare and have breakfast with my wife, shower, get dressed and go down to my home office for the first two-hour block of the day. I practice the Deep Work technique methodology by Cal Newport. I have been practicing the technique for years and it seems to work for me.
After the first block of the day I prepared tea and my wife and I sat down in the living room to chat. The high temperature yesterday was 44 F. The high for today is 30 and currently we are at 29. Taking in consideration wind, the wind chill is at 19 degrees. We were considering going out to Trader Joe’s to get some tea which we are running low, but we decided to have an early lunch and watch some movies this afternoon on Amazon Prime and Netflix.
I was browsing YouTube on my phone and found “Algorithms: Graph Search, 
DFS and BFS” video by HackerRank. The video features Gayle Laakmann McDowell. Because I am reading and solving problems from her book “Cracking the Coding Interview” I decided to watch and write similar code and experiment with it. You know what I think about experimenting.
The video is good. It provides a nice description for Depth First Search (DFS) and Breath First Search (BFS) on graphs. The techniques are quite similar to the ones used to traverse binary search trees (BST). If interested in my BST Search post in this blog, I cover DFS and BSF using a BST; it is a mouthful of acronyms!
I took the time to draw a graph similar to the one shown in the video. I used Microsoft Visio and saved the drawing in PNG (Portable Network Graphics) format so I could insert in this post.
In my code written in Java using the Eclipse IDE, I build a graph that attempts to replicate the drawing. Please note that nodes contain a single character. Typically when you use graphs, each node and edge is associated with a unique ID. Also, the edges may be directed or not. When an edge is not directed, the edge is represented by a line without arrows on the ends. An edge with two arrows also represents a bidirectional edge.
In our sample graph, edges are not directed. This implies that from any node if we find a path from a start node to a finish node, we should also have a path from the finish node back to the starting node.
In the graph I colored the G node in red to flag it as the starting node. The end node labeled H is colored green. The rest of the nodes in the graph are colored yellow. Note that in our graph we should be able to find a path from any two nodes, in particular G -> H and H -> G.
Following is the output for my implementation:
main <<< addNode: val: G adjacency: main <<< addNode: val: R adjacency: main <<< addNode: val: A adjacency: main <<< addNode: val: P adjacency: main <<< addNode: val: H adjacency: main <<< addNode: val: D adjacency: main <<< addNode: val: F adjacency: main <<< addNode: val: S adjacency: main <<< addNode: val: B adjacency: main <<< addNode: val: F adjacency: main <<< addNode: val: S adjacency: main <<< addEdge X-Y: false main <<< addEdge G-Y: false main <<< addEdge X-G: false main <<< addEdge G-R: true main <<< addEdge R-A: true main <<< addEdge A-P: true main <<< addEdge A-S: true main <<< addEdge P-H: true main <<< addEdge S-H: true main <<< addEdge G-B: true main <<< addEdge B-D: true main <<< addEdge B-F: true main <<< addEdge D-F: true main <<< addEdge F-S: true main <<< hasPathDFS X-Y: false main <<< hasPathDFS G-Y: false main <<< hasPathDFS X-G: false main <<< hasPathDFS G-H: true main <<< hasPathDFS H-G: false main <<< hasPathDFS G-S: true main <<< hasPathDFS S-G: false main <<< hasPathBFS X-Y: false main <<< hasPathBFS G-Y: false main <<< hasPathBFS X-G: false main <<< hasPathBFS G-H: true main <<< hasPathBFS H-G: false main <<< hasPathBFS G-S: true main <<< hasPathBFS S-G: false
We should be able to assume that we start by adding nodes to our graph. On purpose it seems that we attempted to add twice nodes with letters ‘F’ and ‘S’. I seems like the software did not complained.
We then add some edges to unknown nodes. Since this is not possible the addEdge() method seems to returned FALSE. We then move on to populate the edges that are illustrated in our diagram. The addEdge() method seems to work for them.
Next we attempt to find a path between non-existing nodes and the hasPathDFS() method as expected, fails returning FALSE. We then attempt to find a path from G -> H and we succeed. What is interesting is that the operation from H -> G fails. Apparently we did not implement a bidirectional graph.
/*
* Test scaffolding.
*/
public class Solution {
// **** main entry point ****
public static void main(String[] args) {
// **** ****
Node n = null;
String edge = "";
// **** instantiate graph ****
Graph g = new Graph();
// **** add nodes to our graph ****
n = g.addNode('G');
System.out.println("main <<< addNode: " + n.toString());
n = g.addNode('R');
System.out.println("main <<< addNode: " + n.toString());
n = g.addNode('A');
System.out.println("main <<< addNode: " + n.toString());
n = g.addNode('P');
System.out.println("main <<< addNode: " + n.toString());
n = g.addNode('H');
System.out.println("main <<< addNode: " + n.toString());
n = g.addNode('D');
System.out.println("main <<< addNode: " + n.toString());
n = g.addNode('F');
System.out.println("main <<< addNode: " + n.toString());
n = g.addNode('S');
System.out.println("main <<< addNode: " + n.toString());
n = g.addNode('B');
System.out.println("main <<< addNode: " + n.toString());
n = g.addNode('F');
System.out.println("main <<< addNode: " + n.toString());
n = g.addNode('S');
System.out.println("main <<< addNode: " + n.toString());
System.out.println();
// **** add edges to the graph ****
boolean added;
edge = "X-Y";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "G-Y";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "X-G";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
System.out.println();
edge = "G-R";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "R-A";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "A-P";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "A-S";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "P-H";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "S-H";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "G-B";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "B-D";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "B-F";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "D-F";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
edge = "F-S";
added = g.addEdge(edge);
System.out.println("main <<< addEdge " + edge + ": " + added);
System.out.println();
// **** DFS ****
boolean path;
String fromTo;
fromTo = "X-Y";
path = g.hasPathDFS(fromTo);
System.out.println("main <<< hasPathDFS " + fromTo + ": " + path);
fromTo = "G-Y";
path = g.hasPathDFS(fromTo);
System.out.println("main <<< hasPathDFS " + fromTo + ": " + path);
fromTo = "X-G";
path = g.hasPathDFS(fromTo);
System.out.println("main <<< hasPathDFS " + fromTo + ": " + path);
System.out.println();
// **** to ****
fromTo = "G-H";
path = g.hasPathDFS(fromTo);
System.out.println("main <<< hasPathDFS " + fromTo + ": " + path);
// **** back ****
fromTo = "H-G";
path = g.hasPathDFS(fromTo);
System.out.println("main <<< hasPathDFS " + fromTo + ": " + path);
System.out.println();
// **** to ****
fromTo = "G-S";
path = g.hasPathDFS(fromTo);
System.out.println("main <<< hasPathDFS " + fromTo + ": " + path);
// **** to ****
fromTo = "S-G";
path = g.hasPathDFS(fromTo);
System.out.println("main <<< hasPathDFS " + fromTo + ": " + path);
System.out.println();
// **** BFS ****
fromTo = "X-Y";
path = g.hasPathBFS(fromTo);
System.out.println("main <<< hasPathBFS " + fromTo + ": " + path);
fromTo = "G-Y";
path = g.hasPathBFS(fromTo);
System.out.println("main <<< hasPathBFS " + fromTo + ": " + path);
fromTo = "X-G";
path = g.hasPathBFS(fromTo);
System.out.println("main <<< hasPathBFS " + fromTo + ": " + path);
System.out.println();
// **** to ****
fromTo = "G-H";
path = g.hasPathBFS(fromTo);
System.out.println("main <<< hasPathBFS " + fromTo + ": " + path);
// **** back ****
fromTo = "H-G";
path = g.hasPathBFS(fromTo);
System.out.println("main <<< hasPathBFS " + fromTo + ": " + path);
System.out.println();
// **** ****
fromTo = "G-S";
path = g.hasPathBFS(fromTo);
System.out.println("main <<< hasPathBFS " + fromTo + ": " + path);
// **** to ****
fromTo = "S-G";
path = g.hasPathBFS(fromTo);
System.out.println("main <<< hasPathBFS " + fromTo + ": " + path);
}
}
Our test scaffolding implemented by the class Solution starts by instantiating a graph. We then add some nodes. After the nodes we add some edges. Feel free to check that the diagram and the code match. If I made a mistake, please leave me a note bellow.
We then move to check if a path exists between two nodes using DFS. Some work and some do not.
Finally we check if some nodes have a path using BFS.
Note that in both methods we are able to find a path from G -> H but not from H -> G. We must have an issue the way we add edges to the graph using the addEdge() method.
/*
*
*/
class Node {
// **** value for this node ****
public char val;
// **** list of adjacent (child) nodes to this node ****
LinkedList<Node> adjacent = new LinkedList<Node>();
// **** constructor ****
public Node(char val) {
this.val = val;
}
// **** ****
@Override
public String toString() {
// **** ****
StringBuilder sb = new StringBuilder();
// **** ****
sb.append("val: " + this.val + " adjacency: ");
// **** ****
for (Node n : this.adjacent) {
sb.append(n.val + " ");
}
// **** ****
return sb.toString();
}
}
The Node class is used to represent nodes in our graph. We have place for a character and edges from the node to other nodes. Edges are implemented with an adjacency list which is in turn implemented as a Linked List. If a node has an edge to another node, then we would make an entry into this list.
/*
*
*/
class Graph {
// **** ****
private HashMap<Character, Node> graphNodes = new HashMap<Character, Node>();
// **** add node to graph ****
public Node addNode(char val) {
// **** lookup the node in the graph ****
if (graphNodes.containsKey(val))
return graphNodes.get(val);
// **** instantiate a new node ****
Node node = new Node(val);
// **** add the node to the graph ****
graphNodes.put(val, node);
// **** return the node ****
return node;
}
// **** get the node from the graph ****
private Node getNode(char val) {
return graphNodes.get(val);
}
// **** add edge between nodes in the graph ****
public boolean addEdge(String edge) {
// **** split string ****
String[] arr = edge.split("-");
char src = arr[0].charAt(0);
char dst = arr[1].charAt(0);
// **** get the source node ****
Node s = getNode(src);
if (s == null)
return false;
// **** get the destination node ****
Node d = getNode(dst);
if (d == null)
return false;
// **** add edge from s to d ****
s.adjacent.add(d);
// // **** add edge from d to s ****
// d.adjacent.add(s);
// **** ****
return true;
}
// **** ****
public boolean hasPathDFS(String fromTo) {
// **** ****
String[] arr = fromTo.split("-");
char src = arr[0].charAt(0);
char dst = arr[1].charAt(0);
// **** ****
Node source = getNode(src);
if (source == null)
return false;
Node destination = getNode(dst);
if (destination == null)
return false;
// **** to avoid revisiting nodes and getting into an infinite loop ****
HashSet<Character> visited = new HashSet<Character>();
// **** recursive method ****
return hasPathDFS(source, destination, visited);
}
// **** DFS implementation (recursive and requires visited flag) ****
private boolean hasPathDFS(Node source, Node destination, HashSet<Character> visited) {
// **** check if this node has already been visited ****
if (visited.contains(source.val))
return false;
// **** flag this node has been visited ****
visited.add(source.val);
// **** check if we found a path ****
if (source == destination)
return true;
// **** check all children of this node ****
for (Node child : source.adjacent) {
if (hasPathDFS(child, destination, visited))
return true;
}
// **** no path was found ****
return false;
}
// **** ****
public boolean hasPathBFS(String fromTo) {
// **** ****
String[] arr = fromTo.split("-");
char src = arr[0].charAt(0);
char dst = arr[1].charAt(0);
// **** ****
Node source = getNode(src);
if (source == null)
return false;
Node destination = getNode(dst);
if (destination == null)
return false;
// **** ****
return hasPathBFS(source, destination);
}
// **** BFS implementation (uses queue and requires visited flag) ****
private boolean hasPathBFS(Node source, Node destination) {
// **** ****
LinkedList<Node> nextToVisit = new LinkedList<Node>();
// ???? to avoid revisiting nodes and getting into an infinite loop ????
HashSet<Character> visited = new HashSet<Character>();
// **** start with this node ****
nextToVisit.add(source);
// **** visit next nodes ****
while (!nextToVisit.isEmpty()) {
// **** get the node being visited ****
Node node = nextToVisit.pop();
// **** check if we are done ****
if (node == destination)
return true;
// **** check if we have visited this node ****
if (visited.contains(node.val))
continue;
// **** flag we have visited this node *****
visited.add(node.val);
// **** visit the children of this node ****
for (Node child : node.adjacent) {
nextToVisit.add(child);
}
}
// **** ****
return false;
}
}
The Graph class contains the bulk of our code. The graphNodes hash map holds the nodes for our graph. You can go down the code and see how the different methods work.
I would like to call your attention to the addEdge() method. After parsing the string indicating which nodes are connected by an edge, and determining the validity of the nodes, we create an edge from the source to the destination. The code for a node from the destination to the source is commented out. This is why our program fails checking the connectivity backwards.
// **** add edge between nodes in the graph ****
public boolean addEdge(String edge) {
// **** split string ****
String[] arr = edge.split("-");
char src = arr[0].charAt(0);
char dst = arr[1].charAt(0);
// **** get the source node ****
Node s = getNode(src);
if (s == null)
return false;
// **** get the destination node ****
Node d = getNode(dst);
if (d == null)
return false;
// **** add edge from s to d ****
s.adjacent.add(d);
// **** add edge from d to s ****
d.adjacent.add(s);
// **** ****
return true;
}
I just removed the comment in the addEdge() method.
main <<< addNode: val: G adjacency: main <<< addNode: val: R adjacency: main <<< addNode: val: A adjacency: main <<< addNode: val: P adjacency: main <<< addNode: val: H adjacency: main <<< addNode: val: D adjacency: main <<< addNode: val: F adjacency: main <<< addNode: val: S adjacency: main <<< addNode: val: B adjacency: main <<< addNode: val: F adjacency: main <<< addNode: val: S adjacency: main <<< addEdge X-Y: false main <<< addEdge G-Y: false main <<< addEdge X-G: false main <<< addEdge G-R: true main <<< addEdge R-A: true main <<< addEdge A-P: true main <<< addEdge A-S: true main <<< addEdge P-H: true main <<< addEdge S-H: true main <<< addEdge G-B: true main <<< addEdge B-D: true main <<< addEdge B-F: true main <<< addEdge D-F: true main <<< addEdge F-S: true main <<< hasPathDFS X-Y: false main <<< hasPathDFS G-Y: false main <<< hasPathDFS X-G: false main <<< hasPathDFS G-H: true main <<< hasPathDFS H-G: true main <<< hasPathDFS G-S: true main <<< hasPathDFS S-G: true main <<< hasPathBFS X-Y: false main <<< hasPathBFS G-Y: false main <<< hasPathBFS X-G: false main <<< hasPathBFS G-H: true main <<< hasPathBFS H-G: true main <<< hasPathBFS G-S: true main <<< hasPathBFS S-G: true
We can see that the issue is solved.
The reason that I brought this up is due to the fact that the addEdge() method has an issue in the video. The video does not run a full implementation or checks like was shown in this post. I did leave a comment on the video. I am wondering if it will get a response.
When developing code it is good to write tests and verify that our assumptions and implementations are correct. This is the essence of TDD (short to Test Driven Development) which I always follow.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of project for a product or service, please do not hesitate and leave me a note below. If you prefer, send a message to: john.canessa@gmail.com; all requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and increase your development toolset!
John
Follow me on Twitter: @john_canessa