Last Friday afternoon I stopped by to donate blood to the Red Cross. I do this twice a year. As usual, I made an appointment. Earlier that day filled the RapidPass, and had a copy of the ticket in my cell phone. The staff at the blood collection site was running behind. After over an hour wait I was called. It took a while to get the process started. The actual donation took no more than 10 minutes. I will be back on fall later this year. Hope the entire process speeds up :o)
I mentioned in the Connected Cells in a Grid post that I would go back and use a better representation of Graphs. I decided to start with sample code from the book Algorithms Fourth Edition by Robert Sedgewick and Kevin Wayne. Like their description of graphs which is covered in four chapters in the book. Of interest for this post is chapter 4.1 Undirected Graphs. Please be aware that their samples build on previous code. The description of the input data for the HackerRank challenge does not match the expected format for the code in the book :o(
The public repository (https://github.com/kevin-wayne/algs4) contains the Java source code for all the algorithms and client code in the text book. That is the official version—it is actively maintained and updated by the authors. The programs are organized in the package edu.princeton.cs.algs4. If one need the class files (and not the source code), one can use algs4.jar instead. Some time ago I downloaded the repository into a folder in my local machine (C:\Utils\algs4).
For this post I modified the algorithms to reduce (eliminate) dependence on classes in the book. You can see what I mean when you inspect the Graph class and compare it to the source code provided in the book. The latter uses a Bag class. I strongly recommend the book for any software developer that wishes to refresh and perhaps learn algorithms.
Enough said. Let’s take a look at the following screen capture from the console of the Eclipse IDE running several examples that I used in the previous post. Please note that before the run I added the data used in the previous post which is acceptable by the actual challenge.
4 4 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 6 4 0 1 1 2 2 3 3 4 main <<< graph: V: 6 E: 4 v(0): 1 v(1): 0 2 v(2): 1 3 v(3): 2 4 v(4): 3 v(5): main <<< connected cells: 5 2 2 1 1 0 1 3 3 0 1 0 2 1 2 main <<< graph: V: 3 E: 3 v(0): 1 2 v(1): 0 2 v(2): 0 1 main <<< connected cells: 3 3 3 0 1 0 0 1 0 1 1 1 5 4 0 1 1 2 1 3 1 4 main <<< graph: V: 5 E: 4 v(0): 1 v(1): 0 2 3 4 v(2): 1 v(3): 1 v(4): 1 main <<< connected cells: 5 4 4 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 1 8 6 0 1 0 2 0 3 1 3 3 4 4 5 main <<< graph: V: 8 E: 6 v(0): 1 2 3 v(1): 0 3 v(2): 0 v(3): 0 1 4 v(4): 3 5 v(5): 4 v(6): v(7): main <<< connected cells: 6
Each run in the updated code starts by providing the total number of vertices (the ones that were labeled true (1) in the actual challenge). The next entry is the number of edges. You can remove some but while I was testing I added new ones and the code behaved as expected. Finally the edges are listed. The first vertex is labeled zero (0). If you try to use vertices out of range the code throws an exception.
The Java 8 code for the test code follows:
import java.util.Scanner;
import canessa.john.graph.Graph;
import canessa.john.graph.dfs.DepthFirstSearch;
public class Solution {
/**
* Determine the size of the current region.
* Recursive method.
*/
static int region(int rows, int cols, boolean matrix[][], int r, int c) {
// **** ****
int size = 1;
matrix[r][c] = false;
// **** N ****
if ((r > 0) && matrix[r - 1][c]) {
size += region(rows, cols, matrix, r - 1, c);
}
// **** NE ****
if ((r > 0) && (c < cols - 1) && matrix[r - 1][c + 1]) {
size += region(rows, cols, matrix, r - 1, c + 1);
}
// **** E ****
if ((c < cols - 1) && matrix[r][c + 1]) {
size += region(rows, cols, matrix, r, c + 1);
}
// **** SE ****
if ((r < rows - 1) && (c < cols - 1) && matrix[r + 1][c + 1]) {
size += region(rows, cols, matrix, r + 1, c + 1);
}
// **** S ****
if ((r < rows - 1) && matrix[r + 1][c]) {
size += region(rows, cols, matrix, r + 1, c);
}
// **** SW ****
if ((r < rows - 1) && (c > 0) && matrix[r + 1][c - 1]) {
size += region(rows, cols, matrix, r + 1, c - 1);
}
// **** W ****
if ((c > 0) && matrix[r][c - 1]) {
size += region(rows, cols, matrix, r, c - 1);
}
// **** NW ****
if ((r > 0) && (c > 0) && matrix[r - 1][c - 1]) {
size += region(rows, cols, matrix, r - 1, c - 1);
}
// **** return the size ****
return size;
}
/**
* Determine the maximum size of all regions.
*/
static int largestRegion(int rows, int cols, boolean[][] matrix) {
int size = 0;
// **** loop once per cell in the matrix ****
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (matrix[r][c] == true) {
size = Math.max(size, region(rows, cols, matrix, r, c));
}
}
}
// **** return max size ****
return size;
}
/**
* Return the maximum number of connected vertices in the specified graph.
*/
static int maxConnectedVertices(Graph graph) {
int maxCount = 0;
// **** loop once per vertex in the graph ****
for (int v = 0; v < graph.V(); v++) {
// **** skip if vertex is not connected ****
if (graph.getAdj(v).isEmpty()) {
continue;
}
// **** ****
DepthFirstSearch dfs = new DepthFirstSearch(graph, v);
maxCount = Math.max(maxCount, dfs.count());
}
// **** ****
return maxCount;
}
/**
* Test code.
*/
public static void main(String[] args) {
Graph graph = null;
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// // **** instantiate a new graph and populate it ****
//
// try {
// graph = new Graph(sc);
// } catch (Exception ex) {
// System.err.println("main <<< " + ex.getMessage());
// System.exit(-1);
// }
// **** instantiate a new empty graph of specified size ****
int V = sc.nextInt();
graph = new Graph(V);
// **** populate the graph ****
int E = sc.nextInt();
for (int e = 0; e < E; e++) {
try {
int v = sc.nextInt();
int w = sc.nextInt();
graph.addEdge(v, w);
} catch (Exception ex) {
System.err.println("main <<< " + ex.getMessage());
System.exit(-1);
}
}
// **** close scanner ****
sc.close();
// **** display the graph ****
System.out.print("main <<< graph:\n" + graph.toString());
// **** determine and display the largest count of connected vertices in the graph ****
System.out.println("main <<< connected cells: " + maxConnectedVertices(graph));
}
}
Please note that I left from the previous implementation the region() function which is not used. Also, I left in (commented out) the shortest constructor that can be used to populate the graph. The commented out code produces the same results with less LOCs.
Following is the Graph.java code. It implements the Graph class. In the previous post the algorithm used a rectangular array of Boolean. Such implementation might run into memory allocation and processing issues when using large (10^6 * 10^6) sparse arrays. The current implementation should work fine with them.
package canessa.john.graph;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;
public class Graph {
// **** members ****
private final int V;
private int E;
private ArrayList<LinkedList<Integer>> adj;
/**
* Constructor
* Instantiate an empty graph with V vertices.
*/
public Graph(int V) {
this.V = V;
this.E = 0;
this.adj = new ArrayList<LinkedList<Integer>>();
for (int v = 0; v < this.V; v++) {
this.adj.add(new LinkedList<Integer>());
}
}
/**
* Constructor
* Instantiate and load a graph.
*/
public Graph(Scanner sc) {
this(sc.nextInt());
int edges = sc.nextInt();
for (int e = 0; e < edges; e++) {
int v = sc.nextInt();
if ((v < 0) || (v > this.V)) {
throw new IllegalArgumentException("Graph <<< invalid v: " + v + " this.V: " + this.V);
}
int w = sc.nextInt();
if ((w < 0) || (w > this.V)) {
throw new IllegalArgumentException("Graph <<< invalid w: " + w + " this.V: " + this.V);
}
addEdge(v, w);
}
}
/**
* Add an edge from v to w and from w to v.
*/
public void addEdge(int v, int w) {
// **** perform some sanity checks ****
if ((v < 0) || (v > this.V)) {
throw new IllegalArgumentException("addEdge <<< invalid v: " + v + " this.V: " + this.V);
}
if ((w < 0) || (w > this.V)) {
throw new IllegalArgumentException("addEdge <<< invalid w: " + w + " this.V: " + this.V);
}
// **** add both edges ****
this.adj.get(v).add(w);
this.adj.get(w).add(v);
this.E++;
}
/**
* Number of vertices in graph.
*/
public int V() {
return this.V;
}
/**
* Number of edges in graph.
*/
public int E() {
return this.E;
}
/**
* Return a string representation of the graph.
*/
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("V: " + this.V + "\n");
sb.append("E: " + this.E + "\n");
// **** loop once per vertex ****
for (int v = 0; v < this.V; v++) {
sb.append("v(" + v + "): ");
// **** loop once per edge ****
ListIterator<Integer> it = this.adj.get(v).listIterator();
while (it.hasNext()) {
sb.append(it.next() + " ");
}
sb.append("\n");
}
// **** ****
return sb.toString();
}
/**
*
*/
public LinkedList<Integer> getAdj(int v) {
return this.adj.get(v);
}
}
As suggested in the book, an implementation for algorithms used for specific tasks is accomplished by the following code:
package canessa.john.graph.dfs;
import canessa.john.graph.Graph;
public class DepthFirstSearch {
// **** members ****
private int count;
private boolean marked[];
/**
* Constructor
*/
public DepthFirstSearch(Graph graph, int s) {
this.count = 0;
marked = new boolean[graph.V()];
dfs(graph, s);
}
/**
* depth first search recursive method.
*/
private void dfs(Graph graph, int v) {
this.marked[v] = true;
this.count++;
for (int w : graph.getAdj(v)) {
if (!this.marked(w)) {
dfs(graph, w);
}
}
}
/**
* Check if the specified vertex is marked.
*/
public boolean marked(int w) {
return this.marked[w];
}
/**
* Returns the count of connected vertices.
*/
public int count() {
return this.count;
}
}
At this point I could implement one more pass. I will see if I give it a shot in the future. Have other things that I would like to do before.
If you have comments or questions regarding this or any other post in this blog, please do not hesitate and send me a message. Will reply as soon as possible and will not use your name unless you explicitly allow me to do so.
Enjoy;
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa