I had to add a few paragraphs before finishing this post. My wife called me to go up to have lunch. During the COVID-19 pandemic, during the workweek, I help my wife with some lunch items just like I do on weekends. Today I made open face toasts with avocado; simple and delicious.
First take a couple ripe avocados, cut them in half and remove the pits. Then peel them. Leave them alone until the toasts are ready (about 3 to 4 minutes).
Today I used four slices of brioche bread that we purchased at Trader Joe’s a week ago. If you are not familiar with brioche, it is fluffy and somewhat 
sweet. Our bread loaf has been used and is still sitting in the refrigerator.
I pulled out our panini press (a.k.a. Breville Smart Grill & Griddle) and set it to start warming up to 400 F. Any electric grill, waffle maker or plain pan can be used as a substitute for a panini press.
While the unit was warming up, I placed in the panini press four small pieces of butter, one at a time and covered them with a slice of the brioche bread. Closed the cover and let the unit reach 400 F. At that point I opened the cover and added on top of each piece of bread a small piece of butter. I then closed the cover and waited for about a minute. I opened the press and flipped the bread. I turned off the panini press and served, in two small plates, two toasts each.
We placed the half avocados over the toasts. With a fork we mashed the avocados. That is it. Open your mouth and take a bite (we both did). You could sprinkle some salt but we do not. If you get a chance and make the avocado toasts, please leave me a message with your thoughts.
The COVID-19 (also known as the Wuhan Virus) pandemic is all over the world. Interesting that there are some countries that are not reporting cases in the CDC world map or are not reporting new cases (i.e., China). Google also has a world map which reports in number of cases per million. I also like the site “COVID-19 Near Me” which only covers the USA but displays the percentage of the population infected. For example, New York State has 0.024% deaths based on its population while New York City has 0.214% deaths. Compare this to Minnesota with 0.001% and Dakota County with 0.000%. I live in the city of Apple Valley which is in Dakota County but in the entire Dakota County there have been only 2 deaths.
Please observe social distancing and do not leave home unless needed. My 
wife and I go shopping every other week (about twice a month). I know of people that have to be out and about at least once a day. I urge you to please consider the implications and ramifications to our neighbors, first responders, nurses and medical staff. We need to slow down the spread so our healthcare facilities are able to handle the large number of patients.
I have been experimenting with graphs and breath first searches. This post covers the state of the Java code that I wrote and rewrote multiple times while experimenting with BFS on graphs. I have one more post on the subject which should be coming up soon.
# **** **** C:\Users\johnc>cd workspace0 # **** **** C:\Users\johnc\workspace0>dir 04/02/2020 10:37 AM <DIR> . 04/02/2020 10:37 AM <DIR> .. 04/01/2020 08:57 AM <DIR> BST-Search 03/29/2020 08:30 AM <DIR> ORCost 03/10/2020 04:24 PM <DIR> SortOnFrequency # **** clone the repo **** C:\Users\johnc\workspace0>git clone https://github.com/JohnCanessa/GraphBFS.git Cloning into 'GraphBFS'... remote: Enumerating objects: 3, done. remote: Counting objects: 100% (3/3), done. remote: Compressing objects: 100% (2/2), done. remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0 Unpacking objects: 100% (3/3), 714 bytes | 6.00 KiB/s, done. # **** new folder created by git **** C:\Users\johnc\workspace0>dir 04/02/2020 11:11 AM <DIR> . 04/02/2020 11:11 AM <DIR> .. 04/01/2020 08:57 AM <DIR> BST-Search 04/02/2020 11:11 AM <DIR> GraphFBS <==== should be GraphBFS!!! 03/29/2020 08:30 AM <DIR> ORCost 03/10/2020 04:24 PM <DIR> SortOnFrequency # **** **** C:\Users\johnc\workspace0>cd GraphFBS # **** **** C:\Users\johnc\workspace0\GraphFBS>dir 04/02/2020 11:11 AM <DIR> . 04/02/2020 11:11 AM <DIR> .. 04/02/2020 11:11 AM 169 README.md # **** **** C:\Users\johnc\workspace0\GraphFBS>type README.md # GraphFBS This Java code implements the BFS algorithm in a graph. To get additional information regarding this code please visit my blog at: T.B.D. Enjoy!
I created a GitHub repository and incorrectly named it Graph FBS, sorry about the typo. I should change the name to Graph BFS. I then added the README.md file. I will edit the README.md file with the proper link after I complete this post on my WordPress site.
main <<< getVertices: 4 main <<< getEdges: 6 main <<< g: (v: 0 [a: 1 c: 10, a: 2 c: 11, a: 3 c: 12]) (v: 1 [a: 3 c: 15]) (v: 2 [a: 0 c: 13, a: 1 c: 14]) (v: 3 []) main <<< fromTo: 0 - 1: 1 cost: 10 orCost: 10 2 -> 1 cost: 25 orCost: 15 main <<< fromTo: 1 - 2: main <<< fromTo: 2 - 3: 0 -> 1 -> 3 cost: 38 orCost: 15 0 -> 3 cost: 25 orCost: 13 1 -> 3 cost: 29 orCost: 15 main <<< getVertices: 6 main <<< getEdges: 7 main <<< g: (v: 0 []) (v: 1 [a: 2 c: 6, a: 4 c: 1]) (v: 2 [a: 4 c: 2, a: 5 c: 2, a: 3 c: 5]) (v: 3 []) (v: 4 [a: 5 c: 1]) (v: 5 [a: 3 c: 5]) main <<< fromTo: 1 - 2: 2 cost: 6 orCost: 6 main <<< fromTo: 1 - 3: 2 -> 4 -> 5 -> 3 cost: 14 orCost: 7 2 -> 5 -> 3 cost: 13 orCost: 7 2 -> 3 cost: 11 orCost: 7 4 -> 5 -> 3 cost: 7 orCost: 5 main <<< fromTo: 1 - 4: 2 -> 4 cost: 8 orCost: 6 4 cost: 1 orCost: 1 main <<< fromTo: 1 - 5: 2 -> 4 -> 5 cost: 9 orCost: 7 2 -> 5 cost: 8 orCost: 6 4 -> 5 cost: 2 orCost: 1
The screen capture from the VSCode IDE appears to show the processing of two graphs. The first one has 4 vertices and 6 edges while the second 6 vertices and 7 edges.
It seems that we traverse the graphs from different nodes. Some resulting paths are empty. This should be the case if we are not able to get from one vertex to another.
We also display a cost and an orCost. I will briefly cover the reason for the orCost later in this post. I was just experimenting with it in preparation for a future post in which a HackerRank problem requires us to produce a path with the smallest possible orCost.
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
/**
*
*/
public class Solution {
// **** test file ****
static final String TEST_CASE_1 = "c:\\Temp\\input01.txt";
/**
* Test scaffolding
*
* @throws FileNotFoundException
*/
public static void main(String[] args) throws FileNotFoundException {
// **** instantiate a graph with the specified number of vertices ****
Graph g = new Graph(4);
// **** add edges to the graph ****
g.addEdge(0, 1, 10);
g.addEdge(0, 2, 11);
g.addEdge(0, 3, 12);
g.addEdge(2, 0, 13);
g.addEdge(2, 1, 14);
g.addEdge(1, 3, 15);
// ???? ????
System.out.println("main <<< getVertices: " + g.getVertices());
System.out.println("main <<< getEdges: " + g.getEdges());
System.out.println("main <<< g: " + g.toString());
// **** display the path between the specified vertices ****
String fromTo;
fromTo = "0 - 1";
System.out.println("main <<< fromTo: " + fromTo + ": ");
g.path(fromTo);
fromTo = "1 - 2";
System.out.println("main <<< fromTo: " + fromTo + ": ");
g.path(fromTo);
fromTo = "2 - 3";
System.out.println("main <<< fromTo: " + fromTo + ": ");
g.path(fromTo);
System.out.println();
// **** instantiate a graph with the specified number of vertices ****
g = new Graph(6);
// **** add edges to the graph ****
g.addEdge(1, 2, 6);
g.addEdge(1, 4, 1);
g.addEdge(2, 4, 2);
g.addEdge(2, 5, 2);
g.addEdge(2, 3, 5);
g.addEdge(4, 5, 1);
g.addEdge(5, 3, 5);
// ???? ????
System.out.println("main <<< getVertices: " + g.getVertices());
System.out.println("main <<< getEdges: " + g.getEdges());
System.out.println("main <<< g: " + g.toString());
// **** display the path between the specified vertices ****
fromTo = "1 - 2";
System.out.println("main <<< fromTo: " + fromTo + ": ");
g.path(fromTo);
fromTo = "1 - 3";
System.out.println("main <<< fromTo: " + fromTo + ": ");
g.path(fromTo);
fromTo = "1 - 4";
System.out.println("main <<< fromTo: " + fromTo + ": ");
g.path(fromTo);
fromTo = "1 - 5";
System.out.println("main <<< fromTo: " + fromTo + ": ");
g.path(fromTo);
System.out.println();
/*
// **** specify file and open it with the scanner ****
File file = new File(TEST_CASE_1);
Scanner sc = new Scanner(file);
// **** read first line from the file and extract # of vertices and edges ****
String[] nm = sc.nextLine().trim().split(" ");
int n = Integer.parseInt(nm[0]);
int m = Integer.parseInt(nm[1]);
// ???? ????
System.out.println("main <<< n: " + n + " m: " + m);
// **** instantiate a graph with the specified number of vertices ****
g = new Graph(n + 1);
// **** read the edges ****
for (int i = 0; i < m; i++) {
// **** read and parse the next line from the file ***
String[] uvc = sc.nextLine().trim().split(" ");
int u = Integer.parseInt(uvc[0]);
int v = Integer.parseInt(uvc[1]);
int c = Integer.parseInt(uvc[2]);
// **** add the edge to the graph ****
g.addEdge(u, v, c);
}
// **** read the source and destination vertices ****
String[] sd = sc.nextLine().trim().split(" ");
int s = Integer.parseInt(sd[0]);
int d = Integer.parseInt(sd[1]);
// ???? ????
System.out.println("main <<< s: " + s + " d: " + d);
// **** close scanner ****
sc.close();
// ???? ????
System.out.println("main <<< getVertices: " + g.getVertices());
System.out.println("main <<< getEdges: " + g.getEdges());
System.out.println("main <<< g: " + g.toString());
// **** display the path between the specified vertices ****
fromTo = s + " - " + d;
System.out.println("main <<< fromTo: " + fromTo + ": ");
g.path(fromTo);
*/
}
}
The test scaffolding allows us to declare a graph by specifying the number of vertices. In the first case our graph will have 4. We then proceed to add directed edges. Each edge has a source and a destination vertex. In addition, we can also make use of a cost to traverse the edge.
Now that we have a full graph, we can traverse it using a breadth first search (BFS) approach. There are two general approaches to traverse a tree and a graph. The first is (DFS) and the second is breadth first search (BFS). In this post we do not use DFS. In DFS the algorithm traverses one of the edges and keeps on going until it reaches a point in which it can no longer proceed. At that time it selects the next edge from the starting vertex or node and repeats. In the BFS the traversal is done by processing all the edges of a vertex first and then continuing to the next vertex. This is where they get their names. Depth goes vertical while breadth goes horizontal.
We use a string to define the source (from) and the destination (to) vertices. I used a string to simplify entering and displaying the data on the console. We ten call a method that computes and displays the path. In addition we could display the cost and orCost.
The process repeats. We create a new graph with 6 vertices. We add a set of 6 edges. We then try to get the paths between different vertices a pair at a time.
I left commented out a different scenario. In this we use a file holding large number of edges. It is easier to use a file than copying and pasting a small set of edges from a text document into the IDE console. I will not cover at this time the last scenario. I will leave it for a future post.
import java.util.ArrayList;
/**
* Class used to represent a graph.
*/
public class Graph {
// **** number of vertices in the graph ****
private int vertices;
// **** adjacency list ****
private ArrayList<Edge>[] adjList;
/**
* Constructor.
*/
public Graph(int vertices) {
// **** set the number of vertices ****
this.vertices = vertices;
// **** initialize the adjacency list ****
initAdjList();
}
/**
* Initialize adjacency list.
*/
@SuppressWarnings("unchecked")
private void initAdjList() {
// **** ****
adjList = new ArrayList[this.vertices];
// **** initialize the adjecency list ****
for (int i = 0; i < vertices; i++) {
adjList[i] = new ArrayList<Edge>();
}
}
/**
* Return the number of vertices in the graph.
*/
public int getVertices() {
return this.vertices;
}
/**
* Return number of edges in the graph.
*/
public int getEdges() {
// **** number of edges ****
int edges = 0;
// **** loop once per vertex****
for (int i = 0; i < vertices; i++) {
edges += adjList[i].size();
}
// **** return the number of edges in the graph ****
return edges;
}
/**
* Add edge between vertices u and v.
* NOTE: The cost (c) is currently not being used.
*/
public void addEdge(int u, int v, int c) {
// **** create new edge ****
Edge e = new Edge(v, c);
// **** add edge to vertex u ****
adjList[u].add(e);
}
/**
* Generate a string that represents this graph.
*/
public String toString() {
// **** ****
StringBuilder sb = new StringBuilder();
// **** populate string builder ****
for (int v = 0; v < this.vertices; v++) {
sb.append("(v: " + v + " " + adjList[v].toString() + ") ");
}
// **** return the required string ****
return sb.toString();
}
/**
* Generate and display the path(s) and cost from u to v.
*/
public void path(String fromTo) {
// **** ****
boolean[] visited = new boolean[vertices];
ArrayList<Integer> pathList = new ArrayList<Integer>();
// **** source and destination vertices ****
String[] sd = fromTo.split(" - ");
Integer s = Integer.parseInt(sd[0]);
Integer d = Integer.parseInt(sd[1]);
// **** add s to the path list ****
pathList.add(s);
// **** generate and display the path ****
path(s, d, visited, pathList);
}
/**
* Recursive method that generates and prints the path(s) and cost from u to v.
*/
public void path(Integer u, Integer d, boolean[] visited, ArrayList<Integer> pathList) {
// **** flag we have visited u ****
visited[u] = true;
// **** reached destination vertex (display the path) ****
if (u.equals(d)) {
// **** display the path between vertices ****
displayPath(pathList);
// **** flag we have not visited this vertex ****
visited[u] = false;
// **** ****
return;
}
// **** check all adjacent vertices ****
for (Edge e : adjList[u]) {
// **** adjacent vertex ****
int a = e.a;
// **** check if vertex has not been visited ****
if (!visited[a]) {
// **** add vertex to path list ****
pathList.add(a);
// **** recurse from this vertex ****
path(a, d, visited, pathList);
// **** remove vertex from path list ****
pathList.remove(pathList.indexOf(a));
}
}
// **** flag that we have not visited this vertex ****
visited[u] = false;
}
/**
* Display path and cost from path list.
*/
public void displayPath(ArrayList<Integer> pathList) {
// **** total cost ****
int cost = 0;
// **** OR cost ****
int orCost = 0;
// **** display first vertex ****
System.out.print(pathList.get(0) + " -> ");
// **** traverse the path ****
for (int i = 1; i < pathList.size(); i++) {
// **** ****
int u = pathList.get(i - 1);
int v = pathList.get(i);
// **** display path component between u and v ****
System.out.print(pathList.get(i));
if (i < pathList.size() - 1) System.out.print(" -> ");
// **** check adjacent vertices ****
for (Edge e : adjList[u]) {
// **** this is the vertex of integers ****
if (e.a == v) {
// **** update total cost from u to v ****
cost += e.c;
// **** update OR cost from u to v ****
orCost |= e.c;
// **** done with this vertex ****
break;
}
}
}
// **** display cost and orCost ****
System.out.println(" cost: " + cost + " orCost: " + orCost);
}
}
The Graph class is used to define our graph. We have number of vertices and an adjacency list. The adjacency list is a common approach to represent graphs. Sometimes representations use arrays, others hash maps, while others (such as this, uses an array list.
The initAdjList method initializes the graph without edges.
The getVertices method returns the number of vertices in the graph.
The getEdges method returns the number of edges in the graph. Note that we first need to add edges before the value returned by this method is different than zero.
The addEdge method is used to create an edge between vertices u and v. Note that we may or may not specify a value for the cost to traverse the edge. I left a note that we are not using costs in this post. That was my initial thought. As we have already seen in the output, the program displays the cost of paths.
Not much to say about the toString method.
The path method is the entry point for a recursive method used to generate and display paths between the specified u and v nodes.
We declare an array to track of the vertices that have been visited and an array list to track the visited nodes. The contents of this array list will be used to display the path from vertex u to vertex d.
The recursive path method starts by setting the proper visited flag to true.
We then check if the current vertex is the destination one. If so we display the complete path stored in the array list, flag that we have not visited this vertex and return.
In case this is not the destination vertex, we loop processing each adjacent vertex. If the vertex has not been visited, we add the vertex to the path and make a recursive call with the current adjacent vertex. When done we remove the vertex from the path list.
When all is set and done we flag the u vertex as not visited. We do so to allow other calls on different paths to visit the u vertex.
The displayPath method is used to display the full path from source to destination. We start by setting a couple values for the cost and orCost. Please note that the orCost will not be covered further in this post. The cost holds the sum of the costs to traverse the edges from source to destination.
We now traverse the path. We get the values for the first two vertices. We then check the adjacent vertices. We are looking for the v vertex. When we find it we get the cost and add it.
After we have traversed the array list we display the cost and the orCost.
/**
* Represents an edge between vertices.
*/
public class Edge {
// **** ****
int a;
int c;
/**
* Constructor.
*/
public Edge (int a, int c) {
this.a = a;
this.c = c;
}
/**
*
*/
@Override
public String toString() {
return "a: " + a + " c: " + c;
}
}
The Edge class is used to represent an adjacent vertex. We also keep track of the cost to traverse the edge.
The constructor is self explanatory. The same holds true for the toString method.
Microsoft Windows [Version 10.0.18363.720]
(c) 2019 Microsoft Corporation. All rights reserved.
# **** ****
C:\Users\johnc>cd workspace0
# **** ****
C:\Users\johnc\workspace0>dir
04/04/2020 07:52 AM <DIR> .
04/04/2020 07:52 AM <DIR> ..
04/01/2020 08:57 AM <DIR> BST-Search
04/05/2020 08:32 AM <DIR> GraphBFS
03/29/2020 08:30 AM <DIR> ORCost
03/10/2020 04:24 PM <DIR> SortOnFrequency
# **** ****
C:\Users\johnc\workspace0>cd GraphBFS
# **** ****
C:\Users\johnc\workspace0\GraphBFS>git status
On branch master
Your branch is up to date with 'origin/master'.
Untracked files:
(use "git add <file>..." to include in what will be committed)
Edge.java
Graph.java
Solution.java
nothing added to commit but untracked files present (use "git add" to track)
# **** add the 3 java files ****
C:\Users\johnc\workspace0\GraphBFS>git add Edge.java
C:\Users\johnc\workspace0\GraphBFS>git add Graph.java
C:\Users\johnc\workspace0\GraphBFS>git add Solution.java
# **** ****
C:\Users\johnc\workspace0\GraphBFS>git status
On branch master
Your branch is up to date with 'origin/master'.
Changes to be committed:
(use "git restore --staged <file>..." to unstage)
new file: Edge.java
new file: Graph.java
new file: Solution.java
# **** check that we are using the proper remote github repo ****
C:\Users\johnc\workspace0\GraphBFS>git remote -v
origin https://github.com/JohnCanessa/GraphFBS.git (fetch)
origin https://github.com/JohnCanessa/GraphFBS.git (push)
# **** ****
C:\Users\johnc\workspace0\GraphBFS>git commit -m "BFS using graphs"
[master c09cc05] BFS using graphs
3 files changed, 392 insertions(+)
create mode 100644 Edge.java
create mode 100644 Graph.java
create mode 100644 Solution.java
# **** ****
C:\Users\johnc\workspace0\GraphBFS>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
(use "git push" to publish your local commits)
nothing to commit, working tree clean
# **** ****
C:\Users\johnc\workspace0\GraphBFS>git push origin master
Enumerating objects: 6, done.
Counting objects: 100% (6/6), done.
Delta compression using up to 12 threads
Compressing objects: 100% (5/5), done.
Writing objects: 100% (5/5), 2.78 KiB | 2.78 MiB/s, done.
Total 5 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/GraphFBS.git
d2a9437..c09cc05 master -> master
# **** ****
C:\Users\johnc\workspace0\GraphBFS>git log
commit c09cc05f21be1b2ee176d444eee63e40772d750c (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date: Tue Apr 7 10:42:11 2020 -0500
BFS using graphs
commit d2a9437f3121c2c053ab405d74e03302b79d3693
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date: Thu Apr 2 11:10:38 2020 -0500
Create README.md
After all is said and done we put the three source files we have written under control of git. We commit and push the changes to our GitHub repository. When all is said and done we check the log. Seems all is well.
After I complete the post in WordPress and get a URI for it, will manually go back to GitHub and will update the README.md file.
!!! PLEASE NOTE !!! The name of the repository does not match the name of the post. I made a typo when entering the name of the GitHub repository. Sorry about that.
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 for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
One last thing, thanks to all 547 subscribers to my blog!!!
John
Twitter: @john_canessa